Boost logo

Boost :

From: David Bien (davidbien_at_[hidden])
Date: 2000-04-19 20:33:29

--- In boost_at_[hidden], jsiek_at_l... wrote:
> Hi David,
> Yes, I think there is definitely interest in this. In fact, some of
> here (mostly myself and Dietmar Kuhl, with comments from many other
> boosters) have already put a bunch of thought into defining what the
> interface should look like for graphs. You can view the results of
> that in the boost vault, in the graph directory. In many ways this
> interface is incomplete and needs to be expanded.
I checked this out. I wouldn't mind renaming various types and
interfaces to corresond to those defined ( though it seems I have
some that are not defined there, at least yet ).

> The old version of GGCL can be read about and downloaded from:
> the OOPSLA paper gives a good overview of the library design.
I checked this out too. It is very extensive and looks to be very
well written and designed - but unless I missed something this is a
undirected graph implementation - with data structures supporting
fast access of attributes about such a graph.
Mine is a directed graph implementation entirely. I have no matrices
of nodes, edges, etc. I allow multiple links between the same nodes,
and between nodes and themselves. The links themselves are present in
two hand-coded linked lists, doubly-linked to allow removal with just
a pointer to one ( i.e. without knowing the graph to which that link
belongs ). There are no back pointers to the parent graph in any of
the associated data structures ( i.e. links, nodes, iterators ). I
took the approach of the STL containers in this regard - if you
misuse an STL iterator ( i.e. with the wrong container ) no assertion
will fire - you will see the results at runtime :-).
What this also allows is easy transfer of nodes and link between same
typed graphs. Also it allows the user of the graph to maintain as
many unconnected graphs in the same graph space, although the graph
only knows of one node as the root of the graph. This is very useful -
 for instance in constructing a set of NFA subgraphs to form the
eventual NFA graph for a regular expression.

David Bien

Boost list run by bdawes at, gregod at, cpdaniel at, john at