Re: [boost] [Review] Boost Graphs Library (GGCL)

From: Jens Maurer (Jens.Maurer_at_[hidden])
Date: 2000-08-29 17:57:32

Some more comments...

Still more to come (hopefully with more code inspection) tomorrow.

General
-------

 - I like the plugin concept for internal properties (docs 4.1.2).
It would be cool to be able to specify more complex types for the
"T" plugin template parameter, for example a "struct" or list type.
Imagine solving the all-pairs shortest path problem by running
Dijkstra's algorithm several times on the same graph.   For each
run, you provide a new start vertex and a property accessor which
indexes a different element in the "distance" array of the vertexes.
The edge weight is fixed and can be re-used.  (You could even run
these in parallel in different threads if you provide separate
temporary storage.)    For this to work, I would have to provide
appropriate property accessor function (put/get), but this seems
less syntactically convoluted and more flexible than nesting several
levels of plugin templates.  For the "struct" case, some template
helpers using pointer-to-members as value parameters can help a lot
here.  Can this be done?

 - The vertex_property_accessor<> has ::type and ::const_type
members.  The ::const_type member seems superfluous.  If the
first template argument is "const Graph", it's obviously a
graph which cannot be changed (thus, a read-only accessor),
otherwise it's a read-write accessor.

 - The names get_vertex_property() and get_edge_property() sound
like the value of the property is retrieved there.  However, only
the accessor (i.e. the meta-level) is retrieved.  What about
vertex_property_accessor() and edge_property_accessor()?  Too long?

 - I notice that Dietmar's original idea of "algorithm iterators"
has been abandoned and replaced with visitors. 

 - I think that the member function interface for a visitor is
inherently algorithm-specific.  You can aim for a classification in
different STL-like "concepts", but a unique UserVisitor requirements
seem too simplistic to me.  For example, kruskal_minimum_spanning_tree
doesn't even allow for user-defined callbacks, although I would
certainly like to be able to add some nice graph animation facility
which shows me how the algorithm works.

Documentation
-------------

4.1.2: "arbitrary number of properties can be attached to the same
graph": probably add a reference to the template nesting
restrictions of the user's compiler.  How many template nesting
levels are eaten per plugin level?

4.1.2: "mapS", "vecS" etc. seem strange: Are they explained anywhere?

4.1.2: distance_type and weight_type are coming out of nowhere when
using vertex/edge_property_accessor<...>.  Should that be *_tag ?

4.1.2: There are several levels of indirection in the property
accessor interface.  For the first-time reader, it's difficult
to cut through the maze.  A few introductory remarks regarding
the intended dimension of flexibility may be in order.  Put
differently, why is the given property interface so nice?

4.1.2, at the end: "propety" -> "property" (in the last example)

4.2.2: The example should say that it assumes that the graph is
non-empty.

4.2.3 has some of the discussion (in particular, the introduction)
of property accessors I'm msising in 4.1.2.  Also, 4.2.3 repeats
some of the stuff from 4.1.2.

4.3.1: It's a bit late to explain vecS at this point. 

4.3.1: In the example program, "typedef Graph::vertex_descriptor"
should not be used, there's a graph_traits<> instead.  At least that's
what all the other sections of the documentation say.

4.3.2: There is no need to typedef OutputIterator; I would just
use the helper function "front_inserter" in the call to
topological_sort.

4.3.3, first code snippet: Other sections of the documentation seem
to prefer edge_property_accessor<..., weight_tag> and get_edge_property().
There seems to be a different way to get an edge weight property accessor
as well.  If so, I find that confusing and would like to stick with
the general thing.  The specific stuff is redundant and should be removed
from the library.

5.3.1: Notation: typo "u is an objects ..."

Jens Maurer