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

From: Johnny Yune (prosonance_at_[hidden])
Date: 2004-04-02 20:00:37

"Cromwell Enage" <sponage_at_[hidden]> wrote: 
(much snipping throughout)
> > 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.  :)

Yes, I should’ve mentioned in my original post that I
am unaware of another c++ graph library as powerful
and flexible as BGL.  It seems peerless at present.  I
was worried that my queries would be abrasive and am
pleased to get such well-written responses.  

> The library does have a rather steep learning curve,
> especially if you're somewhat unfamiliar with graph
> theory and/or template programming.

Perhaps my unrest is an extension of my naivety.  We
seem to be in agreement about BGL’s complexity,
though.  I guess the question is whether or not that
complexity is absolutely necessary.
 
> > 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?

Special-purpose implementation of the graph related
functions that would otherwise have been provided by a
graph library.

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

Unquestionably.  

>  BGL delegates some of the responsibility of
property
> storage to the Boost Property Map Library.  

My confusion is as to why managing those properties
are left to the client instead of the underlying
container.  In the case of properties that are
intrinsic to the (user-defined) object being stored in
the graph, I feel like they should be accessed as
attributes of the object and “connected” to algorithms
by generally trivial functors. What advantage is had
by forcing the client to manage a property map of
properties to vertices when they could instead provide
a functor to reveal the same information?  What about
the cases where the needed properties are only
relevant to the underlying graph structure and the
algorithm, like indices?  Wouldn’t it be more elegant
to have graph container manage those properties than
the client?  

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

I can’t speak for the “Real World” at large, but I can
give you an example of the kinds of problems I would
typically use a graph library for.  When evaluating
new programming languages (and often just for fun), I
download problem sets from old top-coder and ACM
programming contests.  In almost every set of
problems, there is at least one challenge which would
benefit from a standard library graph extension. 
Usually, they center on things like building
conversion equations from a series of ratios, walking
a family tree, choosing a good path, scheduling
planes, etc – the kind of stuff in an undergrad
discreet math class.  These problems will almost solve
themselves in certain programming languages, but in
C++, they require a bit more work (as you know). 
Doing a few of these problem sets always drives home,
to me, the fact that C++ really needs standard
facilities for graphs and regular expressions.  

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

Simplicity is rarely a requirement as such.  Perhaps
it is just ignorance on my part, but riddle me this: 
I can describe a graph in visgraph’s format in a very
small number of simple statements, render it, hand it
to a person and ask them to answer questions like “is
there any path from A to Z?”  What fundamental
functionality would this kind of simplicity preclude
if applied to BGL?
 
> > 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.

This may be an option, although it doesn’t really seem
to offer the generational leap in simplicity that I
would like.  Maybe I am simply needing one more layer
of abstraction?  Perhaps, I need something that
removes the seemingly awkward distinction between the
“thing you want to store in the graph” and “the
attributes of the thing you want to store in the graph
but are not a part of the thing and are instead part
of this other thing.”  Confusing, isn’t it?

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

For reference, this is from the Kevin Bacon example:
typedef property_map < typedef adjacency_list < vecS,
vecS, undirectedS, property < vertex_name_t,
    std::string >, property < edge_name_t, std::string
> >, vertex_name_t >::type actor_name_map_t;

I, personally, would find it much more natural to
define an actor type with appropriate members than to
manage such declerations.  While my views are probably
shaped by my limited understanding of the stylistic
model, that is one UGLY typedef.  It doesn’t really
come trippingly off the tongue, does it?  The amount
of scaffolding required for BGL use is generally large
and complex enough that I would find myself writing
wrappers for the BGL so that I could use it without
constant need for a reference manual.  That would
generally be a bad situation for me (more work), for
other developers (unfamiliar framework dependency),
and for end-users (greater risk of bugs via unproven
code).
 
> > 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.

Thanks ever so much.  I guess that all I have to worry
about now is making a fool of myself.

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

You are absolutely correct.  I should’ve been more
careful in presentation.  Using operator<< in this
case was probably a poor choice, anyway.  Using add_*
would’ve conveyed more information.

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

I believe that would be ambiguous only if a vertex was
somehow illegally defined to be a pair of vertices. 
Regardless, g.add_edge(x,x,x) is just as simple to
type.
 
> The same goes for g.find(); is it supposed
> to find a vertex, an edge, or both?

find would’ve been much more descriptive written as 
std::find(g.dfs_begin(“brother”), g.dfs_end(),
“sister”) or some such.  These are just ideas, of
course, not proven interfaces.  And my illustration
wasn’t really intended so much as an example of syntax
as an example of what I considered to be a “friendly”
api.

> Also, it seems you want to be able to use
non-built-in
> or custom types as vertex IDs.  

Actually, I would prefer to use non-built-in types as
the vertex.  If additional meta-data is needed for
internal maintenance, then I don’t generally want to
be bothered/privileged with it as a client.

> You'll have to build
> your own custom-type-to-vertex map and bind it to
the
> graph;

It seems like that would be better left to the
framework.  

> BGL won't do it for you, to retain its
> genericity.

It seems like adding another layer of abstraction
should decrease coupling instead of adding it.  I
don’t really see how specifying that I want a graph of
file dependencies, for example, is any less generic
than saying that I want a graph of property maps where
the id is a filename.

Regards,
prs

__________________________________
Do you Yahoo!?
Yahoo! Small Business $15K Web Design Giveaway 
http://promotions.yahoo.com/design_giveaway/