GGCL graphs library initial review comments

From: David Abrahams (abrahams_at_[hidden])
Date: 2000-08-28 22:39:30

Documentation comments:

typo on p. 15:

The impact of this technique is a reduction in the STL's code size from
O(MN)
to O(M +N), where M is the number of algorothms
                                          ^

The organization is a bit strange. I don't see how to merge this into my
boost
installation, exactly. Do you intend to keep the ggcl directory separate
from
boost? Could you please post instructions describing how to set it up?
Assume I
have an existing project which uses boost and I want to take advantage of
GGCL
in that project.

I notice you have included my associative_vector and vector_set headers. I
am
flattered! Does GGCL depend on these? These are works in progress, though
I've
been using them myself as is. John Potter has been working on completing the
"grand vision".

The example shown in 1.2.1 doesn't match the code in
examples/quick_tour.cpp,
though the documentation claims that it does.

The lack of namespace qualifications in quick_tour.cpp makes some of the
code
hard to read. For example, when I see id_tag I wonder whether it's a local
variable, type, something from boost:: or something from ggcl::.

Also, the lack of comments, abbreviated names, and overall formatting of
exercise_vertex::operator() makes it highly opaque. Here's my attempt at
cleanup:

template <class Graph> struct exercise_vertex
{
  exercise_vertex(Graph& g_)
      : g(g_) { }

  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

  void operator()(Vertex v) const
  {
    using namespace ggcl;
    typedef typename vertex_property_accessor<Graph,id_tag>::type
vertex_accessor;

    vertex_accessor vertex_id = get_vertex_property(g,id_tag());
    std::cout << "vertex: " << vertex_id[v] << std::endl;

    // Write the outgoing edges
    std::cout << "\tout-edges: ";
    typename graph_traits<Graph>::out_edge_iterator out_i, out_end;
    typename graph_traits<Graph>::edge_descriptor e;
    for (tie(out_i,out_end) = out_edges(v,g);
         out_i != out_end;
         ++out_i)
    {
      e = *out_i;
      Vertex src = source(e,g), targ = target(e,g);
      std::cout << "(" << vertex_id[src] << "," << vertex_id[targ] << ") ";
    }
    std::cout << std::endl;

    // Write the incoming edges
    std::cout << "\tin-edges: ";
    typename graph_traits<Graph>::in_edge_iterator in_i, in_end;
    for (tie(in_i,in_end) = in_edges(v,g); in_i != in_end; ++in_i)
    {
      e = *in_i;
      Vertex src = source(e,g), targ = target(e,g);
      std::cout << "(" << vertex_id[src] << "," << vertex_id[targ] << ") ";
    }
    std::cout << std::endl;

    // Write out all adjacent vertices
    std::cout << "\tadjacent vertices: ";
    typename graph_traits<Graph>::adjacency_iterator ai, ai_end;
    for (tie(ai,ai_end) = adj(v,g); ai != ai_end; ++ai)
      std::cout << vertex_id[*ai] <<  " ";
    std::cout << std::endl;
  }
  Graph& g;
};

Is the name adj() actually a name in ggcl::? Can't we call it
adjcent_nodes() or
something more descriptive? adj() could easily be "adjective" or "adjust".
Names
like bidir_adj_list, while short, end up making code read like a hash of
abbreviations. I would rather see bidirectional_adjacency_list.

In what sense is a bidir_adj_list a list?

I know there was a long discussion about this, but why are you using
operator[]
for property accessors? It seems like operator() wouild be more natural.

By the way, the code in the .pdf file is considerably easier to read.

in 1.2.2 "Accessing the Vertex Set" you give another code snippet, which I
finally understand to be a different "slice" of the same main program you
were
presenting before. It would be clearer if you made that more explicit.

In 1.2.5 "Adding Some Color to your Graph",  it says:

   Internally stored properties are created by specifying plug-in arguments
in
   the template parameters of the graph class.

It's becoming a bit unclear at this point whether the documentation applies
to
only the predefined graph types supplied by GGCL. Would it be worthwhile to
make
the distinction of when the docs are applicable to external graph types more
explicit?

        typedef weight_plugin<int> weightp;
        typedef adjacency_list< listS, vecS, directedS,
                                no_vertex_plugin, weightp > Graph;
        typedef std::pair<int,int> E;

These cryptic short names start popping up in the sample code right around
now,
with no explanation:

        listS, vecS, directedS...

There is also no explanation given for no_vertex_plugin.

In this brand-new example (?) I note the following line:

   Vertex s = *(vertices(G).first); // get the first vertex

with no prior declaration of Vertex.

In 1.2.6, "Extending Algorithms with Visitors", your presentation of
predecessor_visitor would be clearer if the template parameter were called
GetPredecessor. Calling it Predecessor leaves open the interpretation that
it is
the type of the predecessor rather than that of the propery-accessor.
Calling
the data member _p *really* leaves a lot to be desired in the clarity
department. How about _get_predecessor, in your naming convention?

template <class Predecessor>
class predecessor_visitor : public null_visitor
{
public:
  predecessor_visitor(Predecessor p) : _p(p) { }
  ...
protected:
  Predecessor _p;
};

... more to come...

-Dave