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

From: Gary Powell (Gary.Powell_at_[hidden])
Date: 2000-08-29 13:39:14

I don't know my graph theory very well so I'm limiting my comments to
code/style/library construction. Use if you care. >> /nul/dev whatever else.

--------------

Code suggestions:

  implement operator++(int) in terms of operator++(),
i.e.

class  array_binary_tree_node::iterator {

   iterator operator++(int) { iterator t; ++(*this); return t; }

}
As an idiom it means to me, no difference except the return type. For future
maintenance its easier, all the work is done in the other operator fn.

------
As a personal preference drop the "inline" for functions defined within the
class scope. The less useless text the easier to read.

-----

Do you really need to define operator!= if its really just !(operator==) ?
Somehow I thought the two comparison operators required were "==" and "<",
if you do decide to provide both != and ==, define one in terms of the other
if in fact that is the case.

______
bellman_ford.h
  bellman_ford_shortest_paths takes a non const reference to a EdgeGraph g,
but I don't see where it is modified. This makes the nested loop, look
unnecessary.

for(Size k = 0;k < N; ++k)
{
  // looks like k is never used.
  for(tie(i,end) = edges(g); i != end; ++i) { // do i, and end change for
iterations of k?
     if (relax(*i, g, w, d)) // g isn't modified here.
       visit.process(*i, g); }  // is g modified here?
}

// but wait, its "d" that is modified by relax, through the operator[]().
yet d isn't expected to be an array. Yet "Distance d" is passed as a "copy"
to _relax, is it or is it not modified? The way the type is passed to the
fns is very confusing.

// pardon my hashing of the format.

Please use non const pointers for things that get modified, and const
references for things that don't. It makes the code much easier to
understand.

Please use operator()() instead operator[](), unless you are mimicking an
array. Again its easier to read.

-------------------
class bfs_visitor, (and others) has data members base and color as
protected, yet the class is not used anywhere as a base class. IMO make
class  data private unless there is really good reason. "protected" just
screams at me, THIS CLASS IS A BASE CLASS INTENDED for inheritence.

------------
class distance_visitor

  template<class Vertex>
  void start(Vertex s) {
   d[u] = 0; }

shouldn't "s" be a Vertex const & ? My compiler, MSVC, whatever its faults
does the optimization from int const& to "int" as opposed to int *. If
Vertex was an int, and if Vertex is some other user defined type, the const
& is usually better than the copy constructor.

(There are other fns with the same problem.)

---------------------
in dynamic_graph.h
shouldn't "add_vertex" and its fellows use a form of auto_ptr<> for holding
the pointer returned by "new"? I thought I just read a  Herb Sutter puzzle
in his book "Exceptional C++" on this, and it seemed reasonable. Not that I
prefer auto_ptr<> vs some other smart pointer, but rather by forcing the
caller of add_vertex control of the pointer, memory is less likely to leak.

  // bad code:
  add_vertex(....); // pointer is returned from new but not assigned. Memory
Leak!

---------
classes like "plugin" which have default constructors, and/or constructors
which take only one argument should be labeled "explicit" unless you really
mean for automatic type conversion to be done by the compiler. (It doesn't
look like you did here.)

---------------
sgb_*_iterators are missing operator++(int), for no apparent reason. Might
as well include them, or add an comment as to why they are missing.

--------------
It would be nice if "print_* " fns took an ostream &, instead of only
printing to std::cout. Then I could dump the output to a file.

---------------
You have comments about "Not VC++ portable" I didn't try, but did you intend
for this library to run on VC++? I figured the partial specializations you
use would prohibit this, in which case, why not remove these comments and
replace the code with the "std" stuff? (i.e. std::advance() )

---------------

For "weighted_edge_visitor" why not combine those constructors with some
default values for cmp, and binOp. If you call "process" without having set
them, its going to be ugly.

--------------

graph2Tree::parent_pa() const returns a copy of _p, couldn't it return a
const reference?

---------------
dynamic_graph has data member m_edge_plugins public, why isn't it private?
Better yet, is it ever used? My editor only found this one occurrence.

---------------

Allocators: if you use them, you are hosed, as everywhere (See internals of
mutable_queue) you assume that the default allocator is what you want.

----------------

That's all the time I've got for this.

Otherwise a great library!

  -gary-