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

From: Valentin Bonnard (Bonnard.V_at_[hidden])
Date: 2000-09-03 12:56:06

I have review the documentation but nor the code.

I have written down all the comments I have, so you'll find below 
silly typos mixed with design issues.

General comments
----------------

DESIGN

  Your general design (Graph is a concept instead of a class, Visitor is a 
  concept instead of an interface (base class with virtual funcs), using 
  external property not wired into the graph), that is, doing exactly the 
  contrary of SGL (???).
  
  Using non member functions almost everywhere is a bit strange compared to 
  the STL style, but it isn't wrong.

DESIGN: Generaly useful

  Some components in GGCL are useful outside the domain of graphs.
  
  Properties should be used with all classes which contain 
  elements, in particular with Containers. They should be 
  visible and accessible to people who don't need graphs.
  
  The definition of properties in clean in that it makes no 
  mention of graph concepts.
  
  MultiPassInputIterator fall in the same category of general 
  concepts.

LATEX

  Biblio references haven't been compiled !
  
  I think tha tyou are using \texttt for C++ code instead of \verb, 
  so LaTeX thinks it's normal text and that line breaking is allowed 
  inside a C++ identifier. But \verb breaks in almost every context 
  except a normal paragraph. \texttt inside a box should avoid both 
  problems. I often a macro \code for this purpose.

5.1 Graph Structure Concepts
----------------------------

MISSING

  In Figure 5.1
  
  I don't know if it intentionnal, but MutableGraph doesn't appear 
  on the... concept directed graph.

5.1.13 MultiPassInputIterator
-----------------------------

DOCUMENT LAYOUT

  MultiPassInputIterator shouldn't be in the graph section.
  
DESIGN (long, sorry)

  I think that introducing MultiPassInputIterator isn't the right 
  solution. Do you also want to define MultiPassBidirectionnalIterator 
  and MultiPassRandomAccessIterator ? I don't, definitly. It only 
  confuses the issue.
  
  The problem lies into the existing hierarchy of iterators, which 
  mixes movabillity, modifiabillity and lvalue-ness, and these are 
  clearly independant.
  
  The terms Forward, Bidirectionnal and RandomAccess are about 
  movabillity and shouldn't be used to mean anything else.
  
  In a completly orthogonal way, iterators can be immutable, mutable, 
  or neither.
  
  Lvalueness of iterators is also orthogonal with immutabillity.
  
  With these clean concepts, your MultiPassInputIterator is just 
  called a ForwardIterator.
  
  Other translations are:
  
  std::ForwardIterator -> ForwardIterator & LvalueIterator
  std::BidirectionnalIterator -> BidirectionnalIterator & LvalueIterator
  std::RandomAccessIterator -> RandomAccessIterator & LvalueIterator

  Note that in practice the only operation not allowed on my 
  ForwardIterator which is allowed on std::ForwardIterator is 
  &*it. I think that &* is rarely needed in generic code.

5.3.1 Visitor
-------------

DESIGN

  Why do some call-backs get a Graph argument, while others don't ?
  
  All could get a Graph argument; those not interrested could just 
  ignore it.

NAMING

  I don't like the names Visitor and UserVisitor; it sounds like UserVisitor 
  is for the luser^Wend-user, and Visitor for the implementor !
  
  What about ControlingVisitor/PassiveVisitor ? (You get the idea: 
  I'd like the names to express the fact that a UserVisitor is under 
  the control of a superior being (the algorithm), while Visitor 
  is free to choose its destiny (well, allmost).)

TYPO

  > grpah

  graph ?

NAMING

  > The type Distance must be a model of ReadWritePropertyAccessor.

  Then call it DistanceProperty. Distance sounds like a STL: an integer, 
  basically. Here, the value type of Distance is an integer [-like type], 
  not Distance itself, as I understand it.

7.10 reverse cuthill mckee ordering
-----------------------------------

TYPO

  > 7.10.1 psuedo peripheral pair

  pseudo peripheral pair ?

8.1 adjacency list
------------------

  In the example:

  > adjacency_list<> G(N);
  
  The template arguments are missing.

11.3 mutable queue
------------------

TYPO

  mutable_queue<IndexedType, Container, class Compare, ID>
                                        ^^^^^

  Indicate the type of all template arguments or of none.

TYPO

  This adaptor provides a special kind of priority queue (implemented on a heap)
  that has and update operation.
           ^^^
           an

11.4 Distjoint Sets
-------------------

DOCUMENTATION

  Rank,Parent,FindCompress

  The semantic of these template parameters aren't clear to me 
  (only the syntax restrictions are).

TYPO

  p 157:
  > x and y.

  what does it means ?

DESIGN

  The representative element of a set should have a different type 
  (say RepresentativeElement) than the element type 
  to avoid calling link instead of union_set. 

  Adjust the type of all members to take or return a 
  RepresentativeElement.

  RepresentativeElement should be convertible to the 
  element type, since it is indead one of the elements.

QUESTION (not important)

  Does \alpha (the inverse Hackerman function) 
  grows slower than any rec. computable function ?

MISSING

  Do disjoint_sets have assignment operator defined ? 
  If so, just say they are Assignable. If not, explain 
  why.

11.4.3 representative with path halving
and
11.4.4 representative with full path compression

MISSING

  not really well documented !

-- 
Valentin Bonnard