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