Velocity Reviews > Java > Euler tour problem

# Euler tour problem

Piet den Dulk
Guest
Posts: n/a

 10-24-2003
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
Guest
Posts: n/a

 10-24-2003
Piet den Dulk wrote:
> 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
Guest
Posts: n/a

 10-24-2003
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" <(E-Mail Removed)> schreef in bericht
news:bnb19n\$vcqgk\$(E-Mail Removed)-berlin.de...
> Piet den Dulk wrote:
> > 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.
>

Michael Borgwardt
Guest
Posts: n/a

 10-24-2003
Piet den Dulk wrote:
> 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
Guest
Posts: n/a

 10-25-2003
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

"Piet den Dulk" <(E-Mail Removed)> wrote in message
news:3f9901ae\$0\$441\$(E-Mail Removed)...
> 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
>
>

Jos A. Horsmeier
Guest
Posts: n/a

 10-26-2003
"Piet den Dulk" <(E-Mail Removed)> wrote in message news:3f9901ae\$0\$441\$(E-Mail Removed)...
> 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.

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) {

if (dest.contains(node))
return false;

// add it to the destination list
// 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
Guest
Posts: n/a

 10-27-2003
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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post tourinnepal Python 0 01-30-2010 09:53 AM vsoler Python 24 11-11-2009 02:30 AM process Python 4 10-09-2008 05:39 PM tphyahoo Ruby 6 08-08-2008 08:15 PM Protoman C++ 10 12-27-2006 11:57 PM