From: Cromwell Enage (sponage_at_[hidden])
Date: 2004-03-31 15:54:18
On reflection, I've decided to cross-list my reply.
> If one accepts the axiom that "a picture is worth a
> thousand words," then it naturally follows that
> discussion of graphs is always overly prolix.
I recently had a chat with a fellow programmer and
attempted to summarize, in semi-layman terms, how the
core algorithms of my multi-state-mazes library work.
They're pretty simple, but I couldn't do it without
paper and pencil.
> Sadly, the same reasoning is also applicable to
> the code of graph libraries.
If a "code-visualizing compiler IDE" existed that
would give us "code pictures" (plus conform to the new
C++ standard, not ICE, and so on), I'm pretty sure
more of us would be using it for all programming
projects, not just graph applications. :)
But seriously, with graph theory containing several
different problem domains (search, network, AI, etc.),
a graph library attempting to be generic enough for
use in all of them is necessarily complex.
> Boost.Graph seems to expose and require an
> unnecessarily large amount of complexity,
If by "exposure" you mean lots of source code, I'll
take that complexity any day of the week and twice on
The library does have a rather steep learning curve,
especially if you're somewhat unfamiliar with graph
theory and/or template programming.
> Whereas libraries like Spirit go to great lengths
> to make hard things easy, BGL seems to try only to
> make hard things possible.
I haven't looked at the Spirit library yet, so I can't
tell you how easy it may be to use it. Perhaps
getting your hands on a copy of the Boost Graph
Library book will help (I don't have one, so I'm not
> The amount of scaffolding required
> to use BGL for even the simplest of projects
> often dwarfs the code size of a naive,
> yet functional, special-purpose implementation.
Special-purpose implementation of a graph library? Or
BGL aims to be as generic as the STL, but whereas each
STL container deals with essentially one type of
element, a graph needs to contain two types: a vertex
type and an edge type. Furthermore, while most STL
algorithms confine themselves to handling just those
STL container elements, most graph algorithms also
need the properties of vertices and/or edges as input.
BGL delegates some of the responsibility of property
storage to the Boost Property Map Library. I'm just
glad the developers kept the complexity down to its
> While I understand that the BGL is deeply entrenched
> in boost culture, certain academic circles, and even
> publications, I nonetheless suggest that BGL lacks
> the ease of use necessary for widespread adoption.
Having dwelt in the academic circle known as the
University of Central Florida, and thus familiar with
the theoretical uses of a graph library (plus I've
studied some game development apps on the side), I'd
like to learn more about how the Real World would want
to use BGL.
> Even knowing that ease-of-use is not a criterion
> for acceptance into boost, looking at what is
> required of the client to use the BGL always leaves
> me feeling perplexed. Is there any particular
> that a simplified interface is not made available?
Again, I don't know a simple graph problem that
requires a simplified graph interface.
> Perhaps a container adapter could be packaged with
> the library allowing a compromise of functionality
> and flexibility for simplicity?
I thought the boost::vector_as_graph class template
served that purpose. Wrap it around a
std::vector<EdgeList>, with EdgeList =
std::list<unsigned int> (or an edge list container of
your choice, so long as the value type is usable as an
index in the vector), and you should be good to go.
> If a graphing problem is trivial, shouldn't BGL
> provide a trivial solution? Why are the simplest
> useful examples several hundred lines of code?
The examples don't seem that big and hard to
understand. Of course, quite a few of them have
#ifdefs that I could do without since I don't use the
compilers in question, but I can live with them.
> I apologize for all of my vague criticisms - my
> intention is not to flame but rather to test the
Your criticisms seem healthy, and I hope my responses
> It is difficult for me to assess whether the
> simplicity I yearn for isn't present for stylistic
> reasons or whether it would rather necessitate a
> sacrifice of flexibility, functionality or
> implementation clarity. Nor is it clear to me to
> what extent these criteria can be compromised to
> promote clarity of client code. For what it is
> worth, the kind of ease-of-use I'm imagining might
> look like:
g << "vertex" << make_pair("vertex",
g.add_edge("brother", "sister", "sibling");
related = true;
> Could someone please elucidate on why it is
> impossible/impractical/unnecessary/whatever for a
> graph library to have such an interface?
I believe the potential for ambiguity would hinder
this syntax the most. In this case, you'd have to
overload operator<< to input both edges and vertices,
and what if some_node_type turned out to be std::pair?
You couldn't pass in make_pair(vertex,vertex) as an
edge then. The same goes for g.find(); is it supposed
to find a vertex, an edge, or both?
Also, it seems you want to be able to use non-built-in
or custom types as vertex IDs. You'll have to build
your own custom-type-to-vertex map and bind it to the
graph; BGL won't do it for you, to retain its
Incidentally, BGL favors free functions over member
functions. The rationale for that can be found in the
> Should I accept that the BGL is not the magic bullet
> graph library and move on, or can this kind of
> simplicity be somehow found within?
Yeah, no magic bullets here. It depends on the
problem you are trying to solve.
Do you Yahoo!?
Yahoo! Finance Tax Center - File online. File on time.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk