Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!ames!bionet!apple!sun-barr!cs.utexas.edu!milano!cadillac!vaughan@mcc.com
From: vaughan@mcc.com (Paul Vaughan)
Newsgroups: comp.lang.c++
Subject: Re: How do you build iterators for graphs?
Keywords: iterators
Message-ID: <1947@cadillac.CAD.MCC.COM>
Date: 27 Jul 89 15:51:32 GMT
References: <11336@brunix.UUCP>
Sender: news@cadillac.CAD.MCC.COM
Reply-To: vaughan@mcc.com (Paul Vaughan)
Organization: MCC VLSI CAD Program
Lines: 46
In-reply-to: jps@cs.brown.edu (John Shewchuk)

Your problem is the classic "How do you associate new properties with
an existing data structure?" problem.  If the number of active
iterators is fixed and small, you might try just adding an array of
marks and allocating an index when a new iterator fires up.  If the
number of iterators is typically small, but varies for significant
periods of time, you might use dynamically allocated linked lists to
record the marks--searching down the list before each visit.  Any sort
of table will do the trick, sorted, hashed, linear, whatever.  
	One interesting case is where the graph is mostly hierarchical
and the inverse pointers are stored.  Here, it pays to check to see if
there is more than one inverse (parent) pointer before doing the
reconvergence check.  If not, you couldn't have been there before.  
	If your graph doesn't change very often but you do lots of
traversals, you might consider making an array of pointers by
traversing the graph once and storing the linear order in which you
traversed it in the array.  Then subsequent traversals need only march
down the array, and iterators become simple integers.
	In LISP, I implemented a macro for graph traversal that
compiled a function based on the options the user specified.  It could
handle any combination of depth, breadth, preoperations,
postoperations, mostly hierarchical, and searches (instead of
traverals).  The default reconvergence check used hash tables, but by
passing in appropriate functions, mark bits or other tables could be
used.  The macro accepted a reconvergence table object, an accessor
for the table and a modifier for the table.  The most common idiom was
to gensym a unique symbol, pass it in as the table, have the modifier
be a function that set a mark slot in the current node to be the
symbol (the modifier was called with the table and the current node as
arguments) and the accessor simply compared the table with the mark
slot of the current node.  The macro was arranged so that it didn't
involve any overhead for any of the features that weren't used.
Conceptually, if the various functions (children, parents,
reconvergence-table-accessor, reconvergence-table-modifier) were
inline functions there need not be any function call overhead, but
LISP doesn't really let you do that (and the compiler I was using
didn't do it for me).
	I've gone into some detail about the LISP macro I used because
I think it represents a form of code reuse that is almost impossible
to acheive in any other language.  I'd be interested if someone could
create such a facility for c++.  Graphs are one of the most
fundamental and widely used data structures, so such a thing would be
appropriate for a library.  Perhaps an extension to the gnu genclass
facility would be the easiest way to do it in c++.

 Paul Vaughan, MCC CAD Program | ARPA: vaughan@mcc.com | Phone: [512] 338-3639
 Box 200195, Austin, TX 78720  | UUCP: ...!cs.utexas.edu!milano!cadillac!vaughan