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

From: Beman Dawes (beman_at_[hidden])
Date: 2000-08-29 11:37:42

General
=======

* GGCL is wonderful!  I look forward to seeing it included in boost!

* These comments are based on reading the documentation; I neither 
inspected nor tested any of the code.

Substantial
===========

*  No mention of planar graphs.  The most substantial issue I see is the 
complete lack of any mention of planar graphs.  Tree gets its own concept, 
so why is Planar ignored?

[It's OK if GGCL can't handle planar graphs today, but the docs should say 
so, and say what plans are for the future. If GGCL can handle planar graphs 
already, then explanations of the how's and why's are needed, with 
examples.]

Background: I'm interested in planar graphs because they are the subspecies 
of graph used to represent topology when doing digital geography.  See 
http://www.census.gov/geo/www/tiger/index.html.

The topology involved is concerned with 0-cells, 1-cells, and 
2-cells.  These correspond to vertices, edges, and the polygons bounded by 
vertices and edges.  The computer representation is a planar graph.  A US 
nationwide street map, for example, is a planar graph with over 40 million 
edges.

Typical operations include:

   * Is the graph planar?
   * "Walk around the block" and similar open and closed neighborhood 
traversals. Note that edge traversals need to resolve to particular ends 
and sides (see below), not just to the edge as a whole.
   * Given a point, find the nearest vertex, edge, or bounded polygon. 
Again, edges are viewed as having left and right sides.
   * Given a line segment, find intersecting vertices, edges, or bounded 
polygons.
   * Given a polygon, find intersecting whatever...
   * Various minimum bounding rectangle and clipping problems.

Note that many typical operations are very difficult to program unless:
   * Iteration over the edges attached to a vertex is ordered (typically by 
the theta function, applied to the first shape point for the edge coming 
off the vertex).
   * Properties attached to edges are oriented.  In other words, an edge is 
seen as having "from" and "to" ends, and "left" and "right" sides.
   * Dynamic (heap) data structures are used. Search operations require 
2-dimensional spatial search algorithms.  That is somewhat outside the 
graph concepts, but it is critical that the graph concepts don't do 
anything (like move vertices unexpectedly) to impede the search mechanisms.

</planar>

*  Undirected graphs need more explanation.  Are edges treated as in-edges, 
out-edges, or both? Are any concepts invalid for undirected graphs, or do 
all apply?  If the docs answer these questions, I didn't find those 
answers. It seems like undirected graphs are important enough to merit a 
major example, like the (wonderfully clear!) File Dependency Example for 
directed graphs.

* Vertex and Edge concepts? In a prior review, Jens Maurer commented and 
Jeremy Siek replied:

 > >  - Table 5.1: I cannot see why a VertexListGraph refines 
AdjacencyGraph.
 > > In my opinion, iterating though some graph's vertex set is completely
 > > orthogonal to any adjacency properties.
 >
 >The reason I had for that is that a vertex set without any adjacency
 >properties is no longer really a graph, it's nothing more than a set.
 >Also, I don't know of any graph algorithm that iterates though the
 >vertices without also looking at out-edges.

Many digital geography applications (building a spatial search index, for 
example) need to iterate over vertices, in effect. Probably not too serious 
a problem (and I know of commercial systems that do it this way) if they 
have to iterate over edges to retrieve the vertices.  Let's see, looking at 
the Vertex and Edge concepts... Hmm... Well, EdgListGraph has source() and 
target(), so that covers the functionality, but I wonder why there aren't 
separate concepts for Vertex and Edge?

* Size?  Did I miss ways to obtain the number of vertices and edges in a 
graph?  What concept?

* Is it really sufficient for only Bidirectional Graph to provide 
in_edges()?  Or did I miss it in other concepts?  Part of the concern 
depends on how undirected graphs are handled.

* Are planar algorithms the only cases where the ordering of edge iteration 
around a vertex is important?

* Are planar algorithms the only cases where the orientation 
(source,target,left,right) of edges and edge properties is important?

* 5.2 Property Accessor's return-by-value from get().  That is fine where a 
small number of properties is involved.  But for some applications there 
will be a considerably larger number.  Of course, a pointer could be 
stored, but that gets messy.  How about an additional get_ref() function 
(or maybe get_const_ref() in some concepts) which returns a 
reference?  That makes using structs ever so much easier, without impacting 
the return by value needs of other apps. (I wasn't following the discussion 
last winter about property accessors; perhaps this has already been 
discussed.)

Minor
=====

* Wouldn't hurt to run a spelling checker;-) for example "suppoorted" on 
page xiii.

* 1.1 The lead paragraph in 1.1 doesn't pack nearly as much punch as the 
lead paragraph in 5.1.  Consider moving 5.1 paragraph 1 to be the 1.1 lead.

* 1.1.1 The first use of "Function object" should be linked to a 
description of that concept, just as the first use of "iterator" is linked 
to a description.

* Need to explain the relationship between ggcl and boost headers, and ggcl 
and boost namespaces.  [Later: I see from Jeremy's response to Jen's review 
comments that the ggcl headers and namespaces become all boost 
headers/namespaces.  That will be much less confusing.]

* Code snippets would be easier to read if there weren't so much 
qualification.

Whatever the doc's namespace qualification policy is, it should be applied 
consistently.  Currently qualification often varies from snippet to 
snippet, or even within snippets, and that is difficult to read.

How about the introductory material saying something like:

   "Code snippets are used for illustration. To keep code snippets easy to 
read, it is assumed required headers have already been included, together 
with these using statements:

     using namespace boost;
     using std::cout;
     using std::endl;

   In actual code it is often good practice to use explicit namespace 
qualification instead, to avoid obscure ambiguities."

* I'd like to compile and run some of the snippets as encountered.  Is the 
actual code available?  If so mention in docs.

* Page 3, para 1. "A plugin specify the parameterized type ..." should be 
"specifies".

* 1.2.4 "Out-Edges, In-Edges, and Edge Descriptors" unclear for undirected 
graphs. Is there a plain edge iterator or do you use in or out or what?

* 1.2.5 Treating internal and external properties uniformly is really a 
nice feature!

* 4.1.2 Either there are two cut-and-paste errors in the example code on 
page 47, or I'm badly misunderstanding something.

   template <class Graph, class PropertyTag>
   struct vertex_property_accessor {
     typedef ... type;
     typedef ... const_type;
   };
   template <class Graph, class PropertyTag>
   struct vertex_property_accessor {
          ^^^^^^^^^^^^^^^^^^^^^^^^
          edge_property_accessor?
     typedef ... type;
     typedef ... const_type;
   };

   typename boost::graph_traits<Graph>::vertex_iterator v, v_end;
   for(boost::tie(v,v_end) = vertices(g); v != v_end; ++v)
     cout << "d[" << *v << "] = " << get(d,*v) << endl;

   typename graph_traits<Graph>::edge_iterator e, e_end;
   for(boost::tie(e,e_end) = vertices(g); e != e_end; ++e)
                             ^^^^^^^^
                             edges?
     cout << "w[" << *e << "] = " << get(w,*e) << endl;

* 4.3.4 Have Color and color been defined?  If so there should be a 
reference; if not they should be.

   bool has_cycle = false;
   cycle_detector<Color> vis(color, has_cycle);
                  ^^^^^      ^^^^^
   depth_first_search(g, vis);
   cout << "The graph has a cycle? " << has_cycle << endl;

* Is page 58 supposed to be blank?

* Figure 5.1 shows some concepts, but not others.  Where do the concepts 
5.1.9 (MutableGraph) and up fit in.

* Table 5.1 is positioned in the middle of 5.1.1.  Should be in section 5.1 
after figure 5.1.

* Table 5.1 is missing concepts; VertexAndEdgeListGraph, for 
example.  Hum... Everything from 9.1.9 and up is missing.

* 5.1.7 VertexAndEdgeListGraph doesn't seem to provide anything.  Is this 
just because it just refines two other concepts? Could be clearer. See next 
item.

* Several concepts (MutableGraph for example) don't have "Refines" 
paragraphs.  Should say "none" if none.

* 5.2 The use of "readable" to describe "read-only", and "writeable" to 
describe "write-only" functionality will probably cause endless trouble.

Either change the name to match the functionality, or change the 
functionality to match the name.

* Page 73 footnote: Dietmar's last name is spelled wrong!  I've made the 
same mistake in the past:-(  Apparently if the "u" with umlat (sp?) is 
used, then there is no "e".  Otherwise, it is "ue".  Hum... Same problem on 
page xiii.  Better do a global fix!

* 11.5 Describes "tie" as defined in boost/utility.hpp.  It's not currently 
there; this needs to be resolved.

* The www.boost.org URL should be given somewhere. The document will 
probably circulate outside the boost context, so the references to boost 
won't make sense without an explanation or URL.

Good work!

--Beman