Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!ames!apple!brutus.cs.uiuc.edu!wuarchive!wugate!uunet!odi!indirect!jack
From: jack@odi.com (Jack Orenstein)
Newsgroups: comp.lang.c++
Subject: Re: How do you build iterators for graphs?
Summary: How to do multiple iterations over a single collection
Keywords: iterators
Message-ID: <402@odi.ODI.COM>
Date: 27 Jul 89 15:43:20 GMT
References: <11336@brunix.UUCP>
Sender: news@odi.com
Lines: 73

In article <11336@brunix.UUCP>, jps@cs.brown.edu (John Shewchuk) writes:
> 
> 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.

This kind of problem arises whenever there are multiple iterators over
a single collection of objects. Some state has to be recorded for each
iteration.  It is tempting to put this state information in the object
being traversed, the graph in this case (a bit in each node), but it
has the drawback noted - that only one iteration is possible. The same
problem arises in iterating over something as simple as a vector in
which the state of an iteration is recorded in a pointer or subscript
associated with the vector.

A general solution is to record the state information in the iterator
object, as noted by jps. This can be done without the space and time
overhead of hashing. Instead, store multiple mark bits per node, and
have the iterator store information indicating which mark bit to use.
The trick is that the same bit (i.e. in the same relative position) is
used in each node.  Different simultaneous iterations will use
different mark bits.

More specifically, allocate multiple bits per node, either statically
or dynamically.  For simplicity, assume that each node has N
statically allocated mark bits, permitting up to N iterations. The
graph object, which encompasses all the nodes, records active
iterations, and rejects requests for new iterations if there are
already N iterations active. When an iteration is started, an integer
between 0 and N-1 is returned which serves to identify the iteration.
This integer is stored in the iterator object.  When iteration i
visits a node x, the ith mark bit of x is set.  At the end of
iteration i, the graph must be notified so that it can clear bit i in
each node and "reuse" iteration i to fulfill a new request.

This is more efficient than the hash table solution. The iterator
looks the same externally. Internally, there is one additional piece
of information communicated between the graph and the iterator - the
iteration identifier.



Jack Orenstein
Object Design, Inc.