Euler tour problem

[Piet den Dulk]

Dear Programmers,

I want to write the euler tour in java. The rules of the euler tour is to
cross every bridge once and finish at the node where you started. You can
represent the bridges and nodes as a graph.

I want to store that graph with a certain datastructure in my program but I
don't know wich datastructure I have to use. So when you draw the bridges
and the nodes the items have to be stored in that datastructure. I'm only
familiar with the following datastructures: Linked Lists, Binary Trees,
General Trees, Stracks and Queues. But I don't see a graph in any of these
structures. Can anyone tell me what datastructure is needed to store a graph
like this one.

best regards,
Piet den Dulk

 

[Michael Borgwardt]

Dear Programmers,

I want to write the euler tour in java. The rules of the euler tour is to
cross every bridge once and finish at the node where you started. You can
represent the bridges and nodes as a graph.

I want to store that graph with a certain datastructure in my program but I
don't know wich datastructure I have to use. So when you draw the bridges
and the nodes the items have to be stored in that datastructure. I'm only
familiar with the following datastructures: Linked Lists, Binary Trees,
General Trees, Stracks and Queues. But I don't see a graph in any of these
structures. Can anyone tell me what datastructure is needed to store a graph
like this one.

The most common ways to represent graphs are:

- Connection matrix: boolean array of size NxN, where N is number of nodes.
entry (x,y) is set if there is an edge between nodes x and y.
Wastes a lot of space, but very quick for checking existence of edges
between given nodes.

- Edge list: a list of 2-tuples, if tuple (x,y) is present, there is an edge
between nodes x and y. If you have unconnected nodes, you need a separate
list of nodes. The most space-efficient representation, but slow for lookups.

- Connectivity list: for each node, you have a list of all the nodes which are
connected to it by an edge. This is still pretty space-efficient and nearly
as fast for lookups as the matrix (possibly faster when doing a traversal
where you always iterate over the list of nodes connected to the current
one anyway.

You'll almost certainly want to use the connectivity list.

 

[Piet den Dulk]

For the Connectivity List, I suppose I have to use a Linked list for each
Node. I know how to implement a linked list so that won't be a problem. But
do I have to keep all the nodes in a Linked list too? Because everytime a
new node is added to de GUI it has to be stored somewhere, so would it be a
good idea to store it in a list too? So then you have a list with nodes and
then each node has a list of it's own with the connected nodes. And then Am
I still be able to use backtracking for solving the puzzle?

Piet den Dulk

 

[Michael Borgwardt]

For the Connectivity List, I suppose I have to use a Linked list for each
Node. I know how to implement a linked list so that won't be a problem.

First, there's of course already a linked list implemented in the API,
second there's also ArrayList which is almost always better.

But
do I have to keep all the nodes in a Linked list too?

in some sort of data structure, yes. A Map may be a good idea, as well as
for the connectivity lists.

then each node has a list of it's own with the connected nodes. And then Am
I still be able to use backtracking for solving the puzzle?

For the backtracking, you'll probably want to store the steps you've done so
far in a stack and the paths you've already tried in a map or something.
Work the details out yourself.

 

[Speck]

I found a chapter on graphs in Robert Lafore's 'Data Structures and
Algorithms in Java' (ISBN 0-672-32453-9) which specifically mentions Euler's
bridges as does a similar chapter in 'Mastering Algorithms in Perl'
(ISBN1-56592-398-7), and Robert Sedgewick's 'Algorithms in Java' (ISBN
0-201-36120-5). Most discuss the required algorithm in depth.

Speck

 

[Jos A. Horsmeier]

I want to write the euler tour in java. The rules of the euler tour is to
cross every bridge once and finish at the node where you started. You can
represent the bridges and nodes as a graph.

I want to store that graph with a certain datastructure in my program but I
don't know wich datastructure I have to use. So when you draw the bridges
and the nodes the items have to be stored in that datastructure. I'm only
familiar with the following datastructures: Linked Lists, Binary Trees,
General Trees, Stracks and Queues. But I don't see a graph in any of these
structures. Can anyone tell me what datastructure is needed to store a graph
like this one.

How about this for starters --

public class Node implements Comparable {
// node identification
private String nodeName;

// nodes that can be reached from this node
private Set dest = new HashSet();

// node specific data here
...

// ctor
public Node(String nodeName) {
this.nodeName= nodeName;
}

// compare two nodes
public int compareTo(Object node) {
if (!node instanceof Node)
throw new ClassCastException(node);
return nodeName.compareTo(node.nodeName);
}

public boolean equals(Object node) {
return compareTo(node == 0;
}

// connect two nodes
public boolean connect(Node node) {

// already a destination?
if (dest.contains(node))
return false;

// add it to the destination list
dest.add(node);
// notify the destination
node.connect(this);

return true;
}
}

This was from the top of my head, so be gentle with me.
kind regards,

Jos

 

[Piet den Dulk]

Dear Programmers,

Thank you for you help. I've improved my program. I hold a java.util.vector
with al the Islands, in every Island I hold a Linked list with all the
connected Islands. I only have to solve the puzzle with backtracking now. I
was thinking of removing the connection between two Islands once it passed a
bridge then I call a recursive method and gave the new list as a parameter
to the recursive method. After the recursion I set the connection between
the Islans back. Later on this week when I've more time I shall try to
accomplish this puzzle. I shall also try to use the comparable methods from
Jos Horsmeier who was so gentle to list some code.

best regards,
Piet den Dulk