What datastructure to use to store nodes/locations I've visited

Discussion in 'Java' started by 6tc1@qlink.queensu.ca, Jun 22, 2005.

  1. Guest

    Hi all, I'm doing something similar to a graph traversal. And in this
    instance this graph type structure could have cycles. I want to ensure
    I don't revisit old nodes and was wondering if anyone could think of an
    efficient way to store nodes/locations/names that have already been
    visited.

    I was thinking about using a Vector - but that would be very
    inefficient as the number of nodes/locations/names got to the
    thousands.

    Should I just use a Hashtable and then use an empty string or something
    for the value. In other words - if the following were the list of
    locations/nodes I've visited:
    "a"
    "b"
    "cd"
    "dg"
    "de"
    "d"

    then would it make sense to do the following:
    Hashtable hashtable = new Hashtable();
    hashtable.put("a", "");
    hashtable.put("b", "");

    and so on?

    Then when I want to determine whether I've already visited the node
    named "b", I would just say:
    if (hashtable.get("b") != null){
    }

    Thanks,
    Novice
     
    , Jun 22, 2005
    #1
    1. Advertising

  2. Jon Harrop Guest

    wrote:

    > Hi all, I'm doing something similar to a graph traversal. And in this
    > instance this graph type structure could have cycles. I want to ensure
    > I don't revisit old nodes and was wondering if anyone could think of an
    > efficient way to store nodes/locations/names that have already been
    > visited.
    >
    > I was thinking about using a Vector - but that would be very
    > inefficient as the number of nodes/locations/names got to the
    > thousands.


    If you can label every node with a unique integer 1..N then you can just use
    an bool array where "visited" tells you if node "i" has been visited
    already.

    I used the slower approach of a balanced binary tree in my maze generating
    program because I was asked to use a purely functional style:

    http://www.ffconsultancy.com/free/maze/

    If you can only give "names" to each node then a hash table would be a good
    bet.

    --
    Dr Jon D Harrop, Flying Frog Consultancy
    http://www.ffconsultancy.com
     
    Jon Harrop, Jun 22, 2005
    #2
    1. Advertising

  3. Eric Sosman Guest

    wrote:
    > Hi all, I'm doing something similar to a graph traversal. And in this
    > instance this graph type structure could have cycles. I want to ensure
    > I don't revisit old nodes and was wondering if anyone could think of an
    > efficient way to store nodes/locations/names that have already been
    > visited.


    Can you put "been here already" markers on the nodes
    themselves?

    --
     
    Eric Sosman, Jun 22, 2005
    #3
  4. shakah Guest

    wrote:
    > Hi all, I'm doing something similar to a graph traversal. And in this
    > instance this graph type structure could have cycles. I want to ensure
    > I don't revisit old nodes and was wondering if anyone could think of an
    > efficient way to store nodes/locations/names that have already been
    > visited.
    >
    > I was thinking about using a Vector - but that would be very
    > inefficient as the number of nodes/locations/names got to the
    > thousands.
    >
    > Should I just use a Hashtable and then use an empty string or something
    > for the value. In other words - if the following were the list of
    > locations/nodes I've visited:
    > "a"
    > "b"
    > "cd"
    > "dg"
    > "de"
    > "d"
    >
    > then would it make sense to do the following:
    > Hashtable hashtable = new Hashtable();
    > hashtable.put("a", "");
    > hashtable.put("b", "");
    >
    > and so on?
    >
    > Then when I want to determine whether I've already visited the node
    > named "b", I would just say:
    > if (hashtable.get("b") != null){
    > }
    >
    > Thanks,
    > Novice


    You could use a HashSet instead of a Hashtable (or HashMap), gets rid
    of the nonsensical value. Regardless, your test could use contains()
    instead of get(), e.g.:

    if(hashtable.contains("b")) {
    }
     
    shakah, Jun 23, 2005
    #4
    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. asd
    Replies:
    3
    Views:
    439
    Arnaud Berger
    May 23, 2005
  2. Replies:
    3
    Views:
    487
    Thomas Weidenfeller
    Jun 23, 2005
  3. gavnosis
    Replies:
    0
    Views:
    522
    gavnosis
    Aug 2, 2003
  4. Timo Nentwig

    selecting nodes between other nodes

    Timo Nentwig, Jun 16, 2004, in forum: XML
    Replies:
    1
    Views:
    405
    Patrick TJ McPhee
    Jun 17, 2004
  5. Johnny Ooi

    Looking A Nodes From Within Nodes

    Johnny Ooi, Nov 13, 2004, in forum: XML
    Replies:
    10
    Views:
    656
    Johnny Ooi
    Nov 14, 2004
Loading...

Share This Page