Re: [boost] directed graph template library

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 
us
> 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:
> www.lsc.nd.edu/research/ggcl
> 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