id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
5633,BGL isomorphism documentation improvements,Evan Driscoll <driscoll@…>,Jeremiah Willcock,"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?)",Bugs,closed,To Be Determined,graph,Boost 1.46.1,Problem,wontfix,,