https://svn.boost.org/trac10/ticket/5633 <p> Some of the documentation for isomorphism is somewhere between confusing and outright wrong. (I'm not sure what type &amp; severity to use so I left it on default.) </p> <ul><li>In the literate description of the algorithm (<a href="http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/isomorphism-impl.pdf">http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/isomorphism-impl.pdf</a>), starting at the bottom of page 3 in the list of the three cases, I'm guessing <code>i</code> and <code>j</code> are supposed to be <code>u</code> and <code>v</code> instead. (Or the preceeding paragraph could be changed to say <code>(i,j)</code> instead of <code>(u,v)</code>.) </li></ul><ul><li>On the actual documentation page (<a href="http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/isomorphism.html">http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/isomorphism.html</a>) 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 <em>A mapping i from vertices to integers such that if there is some isomorphism that maps v onto v' then i(v) == i(v'),</em> but assuming I read the algo description right, there are two separate maps, where <code>v</code> can map to <code>v'</code> if <code>vertex_invariant1(v,g1) == vertex_invarant2(v',g2)</code>. There's also just a straight-up typo in <code>vertex_invariant2</code>. </li></ul><p> Anyway, here's what I suggest as a rewrite, inspired by a very helpful email from Aaron Windsor on the boost-users list: </p> <p> IN: vertex_invariant1(!VertexInvariant1 x) <br /> IN: vertex_invariant2(!VertexInvariant2 y) </p> <blockquote> <p> Mappings from vertices to integers which restrict which vertices may be considered isomorphic. If a candidate isomorphism maps <code>v</code> to <code>v'</code> but <code>x(v,g1) != y(v',g2)</code>, 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 <code>v</code> and <code>v'</code> 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. </p> </blockquote> <p> (Also, please say what you mean by "an integer". Is it an <code>int</code> specifically, is it any integer type, is it anything convertible to an <code>int</code>, anything convertible to any integer type, or what?) </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/5633 Trac 1.4.3 Evan Driscoll <driscoll@…> Thu, 23 Jun 2011 22:32:50 GMT https://svn.boost.org/trac10/ticket/5633#comment:3 https://svn.boost.org/trac10/ticket/5633#comment:3 <ul> <li><strong>owner</strong> changed from <span class="trac-author">Andrew Sutton</span> to <span class="trac-author">Jeremiah Willcock</span> </li> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> </ul> Ticket Jeremiah Willcock Fri, 29 Jul 2011 01:12:59 GMT https://svn.boost.org/trac10/ticket/5633#comment:6 https://svn.boost.org/trac10/ticket/5633#comment:6 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">wontfix</span> </li> </ul> <p> I tried to recompile the PDF file (the <code>(u, v) -&gt; (i, j)</code> thing is already fixed in the source file, for example), and was not able to get it to work (I do have <code>jweb</code> and <code>lgrind</code>, but I think other things are broken). I'm therefore closing the PDF issues as wontfix. </p> Ticket