Re: FW: [boost] directed graph template library

From: David Bien (davidbien_at_[hidden])
Date: 2000-04-19 19:12:28

--- In boost_at_[hidden], Gary Powell <Gary.Powell_at_s...>  wrote:
>  Hi David,
> 
> > If anyone is interested in this, please reply. 
> > 
> I'm interested! The lack of a good graph template is a big hole in 
the std.
> (IMO) Have you looked at the code at http://infosun.uni-
passau.de/GTL ?
Yes but their's is not a true template library - it provides opaque 
graph objects, node objects, edge objects. The only overridable 
object ( someone correct me if i am wrong ) is the graph object - you 
override a bunch of virtual handlers - interesting but not really 
along the same paradigm as STL. It is a static library - not a 
template library - it just uses the STL templates internally. You 
could associate data structures with the nodes and links cuz they 
have unique ids, but then you'd have to look them up.
Also, they are attemping to emulate LEDA - or at least be somewhat of 
a replacement for it. They provide a TON of functionality that I do 
not provide ( in some cases, perhaps ( i do not know ) i could not 
provide with the current data structures ). In particular I do not 
have a breadth first search ( to be quite honest, i do not even know 
how to perform a breadth first traversal of a graph :-).
I was just attempting to provide, in a efficient manner, the small 
amount of functionality that I knew how to provide, in a flexible 
template format. I was planning on using the graph ( and did ) in a 
lexical analyzer generator ( and perhaps ( work in progress ) in a 
parser generator.
My design goals:
a) minimum of memory objects - 1 per graph object
b) no "flags" or "colors" in nodes or links - this limits multi-
threading - and leads to a bunch of bit flags with obtuse names
c) efficient, non-throwing destructor
d) a bunch of other things I won't go into here :-)
anyway - I like mine better (LOL) - certainly it is a sparser 
implementation - and has been shown to be ( through extensive 
debugging on very large random graphs ) throw-state-safe - which is 
particularly nice for I/O
Also raw I/O I provide is particularly efficient - tracing through a 
depth first traversal of the graph as the input/output proceeds.
Plus - I have written and I own my code completely - which makes it 
easier to give away :-)

bien