Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!ames!rex!ginosko!uunet!mcvax!kth!draken!tut!tukki!sakkinen
From: sakkinen@tukki.jyu.fi (Markku Sakkinen)
Newsgroups: comp.lang.c++
Subject: Re: How do you build iterators for graphs?
Keywords: iterators
Message-ID: <1056@tukki.jyu.fi>
Date: 27 Jul 89 12:04:51 GMT
References: <11336@brunix.UUCP>
Reply-To: markku@jytko.jyu.fi (Markku Sakkinen)
          SAKKINEN@FINJYU.bitnet (alternative)
Organization: University of Jyvaskyla, Finland
Lines: 60

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:
>
>[ Picture: root A, vertices A-B, A-C, B-C ]
Apparently _directed_ graphs are meant (but it does not make a big difference).

>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?

The question is not in the most appropriate group,
since the actual problem does not pertain to any programming language.
The solution may however be neatest to implement in a language with
good data abstraction facilities (but that includes CLU, Ada, Modula-2, ...).

The key point: you want several iterators to traverse the graph
at the same time. This certainly implies that the graph (structure,
if not the contents of the nodes) must be constant, at least as long
as there are active iterators. Hence a very simple solution suggests itself:
1. Do one traversal that constructs the linearised list of nodes
   (or in C++ better the vector of their addresses).
2. Each iterator must then only traverse the linear list.

If you want to update the graph structure sometimes (when there are no
iterators in the midst of it), you could consider e.g. the following:
Put into each graph object also a pointer to the corresponding linear list.
If updates are expected to happen often, you can use a lazy evaluation
tactic by constructing the linear list only when the first iteration
(after an update) is requested.

With some effort, you can do the above completely "behind the scenes"
w.r.t. the users of graphs and iterators. Essentially the same principle
of two (or more) alternative underlying representations of an abstract
datatype has often been suggested for complex numbers: have both the
ordinary and the polar representation, use the more expedient one for
each operation, and convert when necessary. As a difference from that case,
in the current problem we need only one-way conversions (from graph
to linear).

Markku Sakkinen
Department of Computer Science
University of Jyvaskyla (a's with umlauts)
Seminaarinkatu 15
SF-40100 Jyvaskyla (umlauts again)
Finland