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

From: David Abrahams (abrahams_at_[hidden])
Date: 2000-08-29 00:53:22

In 1.2.6 you write:

   The job of recording the predecessors is quite simple. When Dijkstra's
   algorithm adds an edge to the shortest-paths tree we just record the
   source vertex as the parent of the target vertex. Here we use the put()
   function associated with the property accessor to record the
   predecessor. The category of the visitor tells the algorithm when to
   invoke the process() method. In this case we only want to be notified
   about edges in the shortest-paths tree so we specify tree_edge_tag.

        template <class Predecessor>
        class predecessor_visitor
        {
          ...
          typedef tree_edge_tag category;

          template <class Edge, class Graph>
          void process(Edge e, Graph& g) {
            put(_p, target(e, g), source(e, g));
          }
          ...
        };

Even looking at the associated code, this passage is very confusing. Most of
it centers around the put() function:

 1. In what way is it "associated with the property accessor"? If
    overloading is the mechanism at work here, you need to tell us so.

 2. What the heck is it doing? After some careful thought, I can guess that
it
    is setting the predecessor property of the node specified by the
    expression "target(e, g)" to be the result of "source(e, g)".

 3. I also speculate that the category of a visitor acts as a filter which
    determines when it is invoked, and there must be some very special
    categories which are specific to particular algorithms and kinds of
    graph traversal (?)

 4. I know that a visitor normally has a bunch of different functions, but
    I'd like to know why we're implementing the one called "process" as
    opposed to any of the others at this point.

On the basis of my speculation, I suggest some radical name changes:

 1. Rename "property accessor" to "property tag", "property reference", or
    probably best of all, simply "property". I know there were long
    discussions about this in the past, but consider: the way the usage
    above looks, the property accessor isn't really doing any accessing at
    all. Instead, it is the put() function which accesses the property.

 2. Rename "put()" to "set()". The code above seems to be setting the
    predecessor property of the target node.

 3. Rename "category" to "filter" (or something). At least if I've
    understood your categories properly, they don't mirror categories as
we've seen
    them for iterators and containers (describing capabilities).

 4. Rename "tree_edge_tag" to something which better describes its function,
    like "minimum_cost_path_filter".

You continue:

   As a finishing touch we create a helper function to make it more
   convenient to create predecessor visitors. All GGCL visitors have a
   helper function like this.

           template <class Predecessor>
           predecessor_visitor<Predecessor>
           visit_predecessor(Predecessor p) {
              return predecessor_visitor<Predecessor>(p);
           }

So, does this function "visit a predecessor", or make an object which does
so? If I've understood things, the answer is no. Instead, I think it makes
an object which sets the "predecessor in a shortest path" property. So it
should be called something like "label_shortest_path".

...onward...