Boost logo

Boost :

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- ?
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 :-)


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