[boost-users] Re: [boost] [BGL] forced client complexity

From: Cromwell Enage (sponage_at_[hidden])
Date: 2004-03-31 15:54:18

prs,

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,
> though.

If by "exposure" you mean lots of source code, I'll
take that complexity any day of the week and twice on
Sundays.  :)

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
certain).

> 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
the project?

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
current level.

> 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
reason
> 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
> waters.

Your criticisms seem healthy, and I hope my responses
are helpful.

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

#include <less_than_10_graph_headers>
...
digraph<some_node_type,some_edge_context_type> g;
g << "vertex" << make_pair("vertex",
"implicit_vertex");
g.add_edge("brother", "sister", "sibling");
if(g.find(make_pair("brother", "sister")))
            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
genericity.

Incidentally, BGL favors free functions over member
functions.  The rationale for that can be found in the
FAQ <http://www.boost.org/libs/graph/doc/faq.html>.

> 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.

                              Cromwell Enage

__________________________________
Do you Yahoo!?
Yahoo! Finance Tax Center - File online. File on time.
http://taxes.yahoo.com/filing.html