Euler tour problem

Discussion in 'Java' started by Piet den Dulk, Oct 24, 2003.

  1. 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
     
    Piet den Dulk, Oct 24, 2003
    #1
    1. Advertising

  2. 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, Oct 24, 2003
    #2
    1. Advertising

  3. 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" <> schreef in bericht
    news:bnb19n$vcqgk$-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.
    >
     
    Piet den Dulk, Oct 24, 2003
    #3
  4. 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.
     
    Michael Borgwardt, Oct 24, 2003
    #4
  5. Piet den Dulk

    Speck Guest

    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" <> wrote in message
    news:3f9901ae$0$441$...
    > 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
    >
    >
     
    Speck, Oct 26, 2003
    #5
  6. "Piet den Dulk" <> wrote in message news:3f9901ae$0$441$...
    > 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
     
    Jos A. Horsmeier, Oct 26, 2003
    #6
  7. 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
     
    Piet den Dulk, Oct 27, 2003
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. process

    Pr. Euler 18, recursion problem

    process, Oct 6, 2008, in forum: Python
    Replies:
    4
    Views:
    389
    Lie Ryan
    Oct 9, 2008
  2. vsoler
    Replies:
    24
    Views:
    889
    Steven D'Aprano
    Nov 11, 2009
  3. tourinnepal
    Replies:
    0
    Views:
    292
    tourinnepal
    Jan 30, 2010
  4. Robin Rytich
    Replies:
    0
    Views:
    719
    Robin Rytich
    Mar 10, 2010
  5. Gabriel Genellina

    Knight's tour Warndorff's algorithm problem

    Gabriel Genellina, Mar 10, 2010, in forum: Python
    Replies:
    4
    Views:
    1,146
    Terry Reedy
    Mar 11, 2010
Loading...

Share This Page