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

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

  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. 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:
    440
    Arnaud Berger
    May 23, 2005
  2. Replies:
    3
    Views:
    387
    shakah
    Jun 23, 2005
  3. gavnosis
    Replies:
    0
    Views:
    525
    gavnosis
    Aug 2, 2003
  4. Sebastian Bassi
    Replies:
    5
    Views:
    604
    Sebastian Bassi
    Jul 20, 2005
  5. Sebastian Bassi
    Replies:
    0
    Views:
    410
    Sebastian Bassi
    Jul 20, 2005
Loading...

Share This Page