cyclic pointers (was Re: Multiple Inheritance in Ada 9X/Pointers?)

[agate!darkstar!karplus@ames.arc.nasa.gov (Kevin Karplus)]

Someone (sorry, I don't have the name in front of me) asked for
examples where cyclic pointer structures were necessary for efficiency.

I have an application that may qualify.
I have a system for minimizing multi-level logic circuits, doing
technology mapping, and similar logic CAD work.
In this system, logic functions are represented as nodes on a
directed, acyclic graph.  Some of the operations create (or find)
other nodes in the graph equivalent to a particular node.  For one of
the algorithms, it is very useful to iterate over all nodes equivalent
to an arbitrary node (choosing the best of several equivalent ones,
for example).  There are many different way that two nodes can have
been found to be equivalent, and I needed a uniform way of storing
this information.  I have thousands (hundred of thousands perhaps) of
nodes, and widely varying numbers of nodes that may be equivalent, and
I needed to keep the storage cost for the equivalence information
to a minimum.

What I ended up with was an "equivalence ring"---a circularly linked
list connecting all equivalent nodes.  When two nodes are found to be
equivalent, their rings are merged, after first checking that they
aren't already on the same ring.  Note that this strucutre is
inefficient for checking equivalence (union-find structures are much
better), but is quite good for iterating over all equivalent nodes,
and costs only one pointer per node.

I submit this as a candidate for a problem in which circular linking
is a reasonable, efficient solution.  I'd be glad to hear of a better
data structure for the problem. (Send email to karplus@ce.ucsc.edu, I
don't read the comp.lang groups often enough to catch replies.)

Incidentally, if anyone is interested, I have just released an alpha
verion of this system.  It is called ITEM and the source is available by
anonymous FTP from ftp.cse.ucsc.edu.  It is 39,000 lines of c++ (gnu's
g++ to be more precise).  For all the programmers on the project
(mainly Soeren Soe and me, but also some undergrads) it is the first
significant program in C++, and so it may suffer in places from bad
habits brought over from C.

The equivalence ring structure I mentioned is in the "ite" class, in
ite/ite.h and ite/EquvalenceRing.cc.

Kevin Karplus