Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!brunix!jps
From: jps@cs.brown.edu (John Shewchuk)
Newsgroups: comp.lang.c++
Subject: How do you build iterators for graphs?
Keywords: iterators
Message-ID: <11336@brunix.UUCP>
Date: 26 Jul 89 21:01:36 GMT
Sender: news@brunix.UUCP
Reply-To: jps@cs.brown.edu (John Shewchuk)
Organization: Brown Computer Science
Lines: 41


Assume you have a data structure that contains a graph of the form:


   +---+ 
   | A | <- Root
   +---+
     |\
     | \
     |  \
     |  +---+
     |  | B |
     |  +---+
     |  /
     | /
   +---+
   | C |
   +---+

and you want to do a depth first traversal.  If you have visited A and
C and are now visiting B, then you need to know if you seen C before.
Normally, you would associate a 'mark' with each node to indicate
whether the node was visited- simply examine C to see if the marked
bit is set.  Unfortunately, this means only one iterator can be
traversing the graph at a time.  To fix this you can create a friend
class (called graph_iterator or something) that stores the marks and
the current position.

A problem arises when storing the marks- you must make an association
between the nodes and the mark.  I do not see any inexpensive way to
do this.  Hashing takes too much time and space and because the key to
a node is an address, this rules out the obvious direct storage
techniques.

Is there a way to do this that uses unit space and unit access time?
Any suggestions for alternatives?


Thanks.

John Shewchuk                                                jps@cs.brown.edu