Boost logo

Boost :

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


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


* 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

Background: I'm interested in planar graphs because they are the subspecies
of graph used to represent topology when doing digital geography. See

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

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


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


* 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

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

* 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 {
     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)
     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

* 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 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!



Boost list run by bdawes at, gregod at, cpdaniel at, john at