[Boost-bugs] [Boost C++ Libraries] #5633: BGL isomorphism documentation improvements

Subject: [Boost-bugs] [Boost C++ Libraries] #5633: BGL isomorphism documentation improvements
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-06-23 22:13:09

#5633: BGL isomorphism documentation improvements
--------------------------------------------------+-------------------------
 Reporter:  Evan Driscoll <driscoll@…>            |       Owner:  asutton
     Type:  Bugs                                  |      Status:  new    
Milestone:  To Be Determined                      |   Component:  graph  
  Version:  Boost 1.46.1                          |    Severity:  Problem
 Keywords:                                        |  
--------------------------------------------------+-------------------------
 Some of the documentation for isomorphism is somewhere between confusing
 and outright wrong. (I'm not sure what type & severity to use so I left it
 on default.)

 * In the literate description of the algorithm
 (http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/isomorphism-

 impl.pdf), starting at the bottom of page 3 in the list of the three
 cases, I'm guessing `i` and `j` are supposed to be `u` and `v` instead.
 (Or the preceeding paragraph could be changed to say `(i,j)` instead of
 `(u,v)`.)

 * On the actual documentation page
 (http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/isomorphism.html) I
 think the description of the vertex invariants should be reworked
 completely. For starters, it's confusing. (I can elaborate on what I find
 confusing about it if desired, but I ramble too much so I'll leave that
 off.) Second, since the interface changed in 1.35 to have two separate
 invariant parameters, I think it's a bit wrong. In particular, it says ''A
 mapping i from vertices to integers such that if there is some isomorphism
 that maps v onto v' then i(v) == i(v'),'' but assuming I read the algo
 description right, there are two separate maps, where `v` can map to `v'`
 if `vertex_invariant1(v,g1) == vertex_invarant2(v',g2)`. There's also just
 a straight-up typo in `vertex_invariant2`.

 Anyway, here's what I suggest as a rewrite, inspired by a very helpful
 email from Aaron Windsor on the boost-users list:

 IN: vertex_invariant1(!VertexInvariant1 x) \\
 IN: vertex_invariant2(!VertexInvariant2 y)
     Mappings from vertices to integers which restrict which vertices may
 be considered isomorphic.
     If a candidate isomorphism maps `v` to `v'` but `x(v,g1) != y(v',g2)`,
 that candidate is rejected.
     This mapping can be used to etiher speed up the search (as is done by
 the default value, which
     requires that the degrees of `v` and `v'` are equal) on to impose
 extra conditions on the result. The type of each !VertexInvariant must be
 a !BinaryFunction where the first argument is a vertex descriptor, the
 second argument is a graph, and the result type is an integer.

 (Also, please say what you mean by "an integer". Is it an `int`
 specifically, is it any integer type, is it anything convertible to an
 `int`, anything convertible to any integer type, or what?)

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/5633>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.