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

From: Jens Maurer (Jens.Maurer_at_[hidden])
Date: 2000-08-30 09:13:34

Part three of my comments.

I'm still not through :-(

General
-------

 - adj(v,g) is a bit short for a non-obvious non-member function name.

 - An AdjacencyGraph does not add further semantic requirements over
an IncidenceGraph, because I can write a general iterator adapter which
applies the target() function to all values of an out_edge_iterator,
thus emulating an adjacency_iterator and the adj() function.  This
should be noted in the documentation, and an appropriate adapter could
be added to the library in the future.

 - The library introduces some non-member functions to remain extensible.
An extension scenario would be that a user implements his own graph
data type implementing e.g. AdjacenyMatrix.  Then I can call edge(u,v,g)
on an object g of that graph type from anywhere and Koenig lookup will
find the correct function.  What happens if some other subsystem wants
to be extensible as well and defines a non-member edge() function with
a different meaning?  Hm... Either the function signature disambiguates,
or there's a problem.  I must think about this separately, and it's not
a specific problem with GGCL.

 - Thinking a bit more about the plugin idea, it looks like this is
a generally useful concept for other non-linear data structures, not
just for graphs.  The nested plugins are only one option for the
representation of the internal properties.  Looking at MutableGraph,
this change could be as simple as renaming G::edge_plugin_type to
G::edge_internal_properties_type (same with vertex_*) and renaming the
"Plugin" template parameters to "EdgeProperties" or so for the graph
class templates.  Oh, and the defaults such as referring to "weight_tag",
which are plugin-centric, have to be removed from the algorithms.

 - MutableGraph, remove_edge(g,u,v) is possibly the wrong interface,
because it looks like it requires random access to the edge connecting
u and v (much like edge(u,v,g) of AdjacencyMatrix) to be efficient.
I would prefer remove_edge(g,e), where e is an edge_descriptor.

 - MutableGraph seems a bit coarse a concept to me.  I can easily
imagine algorithms which need to add and remove edges only and don't
touch the vertices.  Why should my specialized graph data structure have
to bend backwards to provide vertex removal just because the algorithm
description couldn't express its limited requirements and required
"MutableGraph" instead?  This makes for even more concepts, but they can
stand one besides the other without any "refines" hierarchy (except that
they all refine Graph).  Algorithms would have a list of concepts
as requirements, for example "AdjacencyGraph, EdgeAddableGraph,
EdgeRemovableGraph".

 - UserVisitor: The tag idea with distinct types for the categories
has been stretched a bit too much here.  Basically, you want to specify
a bit-mask when the call-back should be invoked.  Why can't we have
an in-class "static const" member (or enum for broken compilers)?

 - Visitor chaining via std::make_pair() is cool.

 - breadth_first_search has a separate independent template parameter
"Vertex" for the type of the start vertex "s".  Isn't this required to
be (convertible to) graph_traits<VertexListGraph>::vertex_descriptor
always?  I suggest removing this particular freedom.  Same with
best_first_search, dijkstra_shortest_paths, prim_minimum_spanning_tree
Example:
template<class VertexListGraph>
void dijkstra_shortest_paths(VertexListGraph& G,
   typename graph_traits<VertexListGraph>::vertex_descriptor v);

 - breadth_first_search and depth_first_search are different in that
the latter creates a forest, not a single tree.  That's surprising
to me at first glance.  However, that's probably how it's most
useful.

 - bellman_ford_shortest_paths has a template parameter Size for the
number of vertices.  This should be graph_traits<...>::size_type
(if that doesn't exist, add it).  See the Vertex discussion above.

 - For the adjacency_list, the selectors are the wrong design, because
they limit the choice of base containers to a fixed set.  Use
template template parameters instead, that's what they're there for.
Plus, that's the first real use of template template parameters I
can see :-)

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

5.1.8, first line: "the" missing before "Graph".

5.1.9: Does MutableGraph refine anything?  If not, say so.

5.1.9: num_vertices() is used in the postcondition, but this is
not a requirement of any of the graph concepts.  num_edges() is
possibly useful as well.

5.1.10, third lind: "identity "-> "identify"

5.2, footnote 1: You've got two options how to write funny German
words with umlauts in them (such as Dietmar's name):
Best: Use a proper charset (ISO 8859-1) and spell Kühl (with
u umlaut).  If your local charset is limited and cannot represent
"u umlaut", then replace the ü (u umlaut) with "ue", i.e. Kuehl.
Writing "Küehl" (with u umlaut and e) is wrong.  (Dietmar, I hope you
don't mind serving as an example. :-) )

5.2.1: get(pa,k):  The return type should be
property_traits<PA>::value_type, strictly speaking.

5.2.2: WritablePropertyAccessor says that it must be
CopyConstructible, but ReadablePropertyAccessor doesn't say that.
This is inconsistent.  It's redundant anyway, because there is a
general requirement on page 87, after the bold "lvalue".

5.2.4: at() has the return type property_traits<PA>::value_type&,
strictly speaking.

5.3.2, page 78, example: UserVisitors are supposed to return "void"
from their process method.

5.3.2, page 78: Once more "vecS" and "directedS" without explanation.
num_vertices has never been a requirement for any graph type.

5.3.2, figures 5.2 and 5.3: Mark that the search started at vertex 0.

6.3, figure 6.1: nice wave diagram

6.3: Objects of what type should be managed in the buffer?  Imagine
my providing a std::stack<T> for Buffer, what should T be? int?
double?  graph_traits<G>::vertex_descriptor?

6.4.1: The description says nothing about what the function
actually *does*, it just ruminates on purpose, responsibility
and implementation.

6.5, "If init_graph is true then best_first_search() will invoke
the initialize_graph() function which will initialize the color,
distance, and weight properties."  Is that a requirement for the
Visitor I provided?  Or do you craft your own, fresh visitor which
does initialize color, distance, weight?  If so, why is Weight
only a ReadablePropertyAccessor?  Please clarify.

7.1: Literature references seem to be bogus.

7.1, last two sentence before "Definitions": "color" seems to be a
required property as well.

7.1, example: More of listS, vecS, directedS

7.2: The documentation shows the source code, but what's the
relax() function?  If you don't want to explain that, just
remove the source code.  It's never shown for other descriptions.

7.3: The source code of the implementation should not be the first
thing in the description.   The declaration is enough to grok. :-)

7.3: There are no explanations what the DistanceMatrix is good for,
what its requirements are etc. Additionally, I cannot see how I
can configure Dijkstra's algorithm used here to use a binary heap
or a fibonacci heap, as promised in the description.
A "requirements on types" section would be nice, too.

Code
----
 - Yes, I'm also for removing the redundant "inline" from member
functions defined in-class.
Jens Maurer