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

From: jsiek_at_[hidden]
Date: 2000-08-29 19:54:16

Jens Maurer writes:
 >  - 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.

Yes, more complicated types such as a struct or std::list can be used
as the plugin value type. However, you will probably want to access it
via an LvaluePropertyAccessor (5.2.4) using the at() function.

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

I'm starting to lose you here... did my above statement answer your question?

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

True, but that may actually be more confusing to use because the user
would have to remember to add the const in situations like this:

template <class Graph>
void foo(const Graph& g) {
#if JENS_SUGGESTION
  typename vertex_property_accessor<const Graph, color_tag>::type
    color = get_color_property(g, color_tag());
#elif OLD_WAY
  vertex_property_accessor<Graph, color_tag>::const_type
    color = get_color_property(g, color_tag());
#endif
}

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

This has been nagging at me too. get_vertex_property_accessor() is
pretty long, but I think it may be necessary.

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

I've never been sold on the idea of algorithm iterators.

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

Good point, the current visitors are really only applicable to
algorithms in the graph search family (BFS, DFS, Dijkstra, Prim), but
this is not explained in the docs. Perhaps changing the name of the
concept to GraphSearchVisitor would be helpful. We haven't really
thought about what visitors should look like for the other algorithms,
and you're right in that the visitor for each algorithm may be quite
different.

Cheers,

Jeremy