[boost] directed graph template library

From: jsiek_at_[hidden]
Date: 2000-04-19 18:19:06

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. Perhaps the material
in your graph code could help us expand the interface.

My group at Notre Dame is working on updating our graph library, GGCL
to this new interface, which we will be releasing soon. Its current
license (not-free for commercial) prevents it from becoming a "boost"
library, though we are considering a change in that regard. A question
for you license experts here (I really don't understand licenses):
does the Artistic License fit into the boost requirements?

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.

Cheers,

Jeremy Siek

David Bien writes:
 > Over the past year or so I have written a directed graph template.
 > 
 > template < class t_TyNodeEl, class t_TyLinkEl, class t_TyAllocator,
 >            class t_TyGraphTraits = _graph_traits_map< ... > >
 > class _graph;
 > 
 > If anyone is interested in this, please reply. It would take a 
 > reasonable ( but not unreasonable ) amount of work to publish this
 > library with documentation, etc., but I wouldn't mind too much.
 > 
 > Some properties:
 > - true cyclical directed graph ( can be used as acyclic )
 > - templatized by node element, link element, allocator, graph traits
 > - one memory object per node
 > - one memory object per link
 > - total memory objects in a graph, g with N nodes, L links =
 >   1 ( for g ) + N + L
 > - written in ANSI C++, compiles on intel4.0 and gcc2.95.2.
 > - const-correct ( at least that's the idea :-)
 > - micro-engineered ( so you don't have to :-)
 > - O(N+L) non-throwing destructor(assuming element's dtors don't throw)
 > - library is throw-state-safe i.e. a throw preserves originally state
 >    whereever possible / semantically desirable.
 > - copy in O( N + L + MlogM + KlogK )(approximate) where M is number
 >    of multi-parented ( childrened ) children ( parents ) and K is the
 >    number of links that leave those nodes in the opposite direction 
 >    of the current copy direction. Since we don't have coloring built
 >    into the graph elements, we sometimes need to look up touched
 >    nodes/links. We only need to keep the lookups around for a given
 >    region of the graph - until the depth first search in the current
 >    direction is over - thus the number is generally less than given
 >    above - for multi-regioned graphs.
 >    Copy of graph that is tree is O(N+L).
 >    Copy is templatized by output graph type - allowing copy to create
 >    a different graph type than the original, i.e. a graph of doubles
 >    can be created from a graph of ints ( nodes and/or links ).
 > - support for "closed directed" copy - to allow copying of a portion
 >    of the graph. Same code and same order as above. Guarantee that
 >    only nodes and links that will be in resultant graph will get
 >    copied.
 > - serialization to/from stream support, currently support ostreams
 >    and OLE streams through templatized wrapper. Order of
 >    serialization is similar to copy. Note that, since the graph is
 >    serialized in depth-first order, lookup is minimized on save/load.
 >    Saving/loading a graph that is a tree is O(N+L).
 > - support for human readable dump ( depth first order ).
 > - support for many types of iterators:
 >   = graph iterator - iterates the entire graph in depth first order -
 >      either forward/backward and also supports "closed directed"
 >      iteration - to iterate a closed region of the graph.
 >   = selection iterator - iterates a the graph according to a selection
 >      function object ( templatized by ). Currently only selective link
 >      iteration is supported(it is all i needed to do some other work).
 >   = node iterator - maintains identity of a single node, allows
 >      movement from that node. ( safe version supported )
 >   = link position iterator - maintains a position in a parent/child
 >      adjacency list. ( safe version supported )
 >   = link identity iterator - maintains the identity of a link(safe sp)
 >   = graph path iterator - maintains a path in a graph. I have a safe
 >      version for this as well, but it is incomplete - to be done -
 >      it is a bit tougher than the others :-).
 >   = I/O iterators - I/O is performed using throw-state-safe iterators.
 >      This allows I/O to proceed correctly, regardless of low-memory
 >      situations, etc. The exception can be handled i.e. allow the
 >      user to free disk space or close applications, and the I/O
 >      operation can complete successfully.
 > - templatization by graph traits allows selective modification of
 >    implementation classes. Since implementation classes are not
 >    ( in almost all cases ) defined inside of _graph - but rather
 >    within a hierarchical graph traits type repository, implementations
 >    of various graph objects can be selective overridden. Thus, for
 >    instance, if one wanted to provide a "color" for both links and
 >    nodes that was known by the implementation, and then provide a
 >    graph copy that utilized this color ( a non-multi-thread approach )
 >    this can be done with (relative) ease.
 >    It also provides a simple template for the general purpose user,
 >    but with tremendous flexibility for the expert who is engineering
 >    a fast and/or specialized implementation.
 > - "safe" iterators ( not to imply thread safety - though this was the
 >     initial goal ) provide a means of "watching" a node, link, or
 >     link position ( or eventually a path, maybe ) within the graph.
 >     If the node goes away, then the graph object in the iterator is
 >     nullified. This could be made thread safe. A notification system
 >     could also easily be added through this mechanism.
 > - All implementations ( except for copy - TBD ) have been written so
 >     that the meat of the implementation goes into a non-templatized
 >     base class - that calls pointer-to-member functions defined by
 >     its parent class ( i.e. to do type specific stuff )
 >     This keeps the added code size for additional graph types at
 >     a minimum.
 > 
 > David Bien
 > 
 > 
 > 
 > ------------------------------------------------------------------------
 > Join Garden.com's affiliate program and enjoy numerous benefits. 
 > To learn more click here:
 > http://click.egroups.com/1/2753/2/_/9351/_/956175851/
 > ------------------------------------------------------------------------
 > 
 > 
 >