Data structure 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. Advertisements

  2. 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.

    ....

    java.util.HashSet

    Patricia
     
    Patricia Shanahan, Jun 22, 2005
    #2
    1. Advertisements

  3. "Patricia Shanahan" <> wrote in message
    news:Jrjue.7589$...
    > 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.

    > ...
    >
    > java.util.HashSet
    >
    > Patricia


    Well, at the risk of pointing out the obvious, why not ue a 'visited' flag
    in the actual nodes and check for these during traversal.

    Remon
     
    Remon van Vliet, Jun 22, 2005
    #3
  4. Remon van Vliet wrote:
    > Well, at the risk of pointing out the obvious, why not ue a 'visited' flag
    > in the actual nodes and check for these during traversal.


    It only works in limited circumstances. E.g. it doesn't work in any
    setup where you have concurrent (overlapping ) traversals of the graph
    going on.

    It also requires an extra step to clear all flags prior to traversal if
    you do more than one traversal. Which means you better have all your
    nodes arranged in some other data structure, like a list, too. Otherwise
    you end up in the situation where you would have to do a traversal to
    clear the flags to prepare for a traversal. However, the
    preparation-traversal can't work if you need the flags for loop
    detection during traversal.

    /Thomas


    --
    The comp.lang.java.gui FAQ:
    ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq
     
    Thomas Weidenfeller, Jun 23, 2005
    #4
    1. Advertisements

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:
    629
    Arnaud Berger
    May 23, 2005
  2. Replies:
    3
    Views:
    488
    shakah
    Jun 23, 2005
  3. gavnosis
    Replies:
    0
    Views:
    684
    gavnosis
    Aug 2, 2003
  4. Timo Nentwig

    selecting nodes between other nodes

    Timo Nentwig, Jun 16, 2004, in forum: XML
    Replies:
    1
    Views:
    560
    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:
    901
    Johnny Ooi
    Nov 14, 2004
  6. Replies:
    2
    Views:
    534
  7. Xamle Eng

    Why treat text nodes as nodes?

    Xamle Eng, May 13, 2005, in forum: XML
    Replies:
    8
    Views:
    680
    Fredrik Lundh
    May 28, 2005
  8. Sebastian Bassi
    Replies:
    5
    Views:
    743
    Sebastian Bassi
    Jul 20, 2005
Loading...