https://svn.boost.org/trac10/ticket/6242 <p> It seems there is a problem with the isomorphism function not resetting data from the <a class="missing wiki">IsoMapping</a> variable between function calls and certain types of graphs. </p> <p> I discovered this with my own implementation of a CSR graph (for the Matlab BGL wrapper), but I could reproduce the same behavior with types already in the BGL. (I was unable to reproduce this bug with the adjacency_list class.) I attach a test case below that shows the problem. </p> <p> Manually resetting the <a class="missing wiki">IsoMapping</a> data between function calls appears to fix the issue, although I must confess, this seems a bit kludgey, and may point at a deeper issue with the isomorphism algorithm. </p> <p> Here is call to compile and an explanation of the problem: </p> <p> g++ --version g++ (<a class="missing wiki">Ubuntu/Linaro</a> 4.4.4-14ubuntu5) 4.4.5 </p> <p> Illustration of the problem </p> <hr /> <p> I have two nearly-isomorphic graphs (they are isospectral, but non-isomorphic), G and H. If I call isomorphism(G,H) initially, it succeeds and tells me they are non isomorphic. Then, I call isomorphism(G,G), and then call isomorphism(G,H) again. The 3rd call incorrectly reports they are isomorphic! This persists if I repeat the call; but returns to the correct answer if I manually reset the mapping data between vertices. </p> <p> g++ isobug.cc -I/home/dgleich/dev/lib/boost_1_48_0 -g; ./a.out isomorphism(G,H): Correct initial output on different pair! Not isomorphic (correct) isomorphism(G,G): Correct initial output on exact pair! Isomorphic (correct) isomorphism(G,H): INCORRECT output on the same first pair Isomorphic (incorrect) isomorphism(G,H): Persists after a function call... Isomorphic (incorrect) isomorphism(G,H): Correct again after reset map Not isomorphic (correct) </p> <p> Fix for problem </p> <hr /> <p> I've attached a potential fix that simply resets the mapping data at the start of the test_isomorphism function. </p> <p> This shows the correct output (although the labels on the cases are no longer true :-)) </p> <p> g++ isobug.cc -I/home/dgleich/dev/lib/boost_1_48_0 -g -DMYISO; ./a.out isomorphism(G,H): Correct initial output on different pair! Not isomorphic (correct) isomorphism(G,G): Correct initial output on exact pair! Isomorphic (correct) isomorphism(G,H): INCORRECT output on the same first pair Not isomorphic (correct) isomorphism(G,H): Persists after a function call... Not isomorphic (correct) isomorphism(G,H): Correct again after reset map Not isomorphic (correct) </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/6242 Trac 1.4.3 dgleich@… Thu, 08 Dec 2011 22:35:52 GMT https://svn.boost.org/trac10/ticket/6242 https://svn.boost.org/trac10/ticket/6242 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">isobug.cc</span> </li> </ul> Ticket dgleich@… Thu, 08 Dec 2011 22:36:50 GMT https://svn.boost.org/trac10/ticket/6242 https://svn.boost.org/trac10/ticket/6242 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">isomorphism_fixed.hpp</span> </li> </ul> Ticket Jeremiah Willcock Mon, 16 Apr 2012 17:55:09 GMT https://svn.boost.org/trac10/ticket/6242#comment:1 https://svn.boost.org/trac10/ticket/6242#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/78023" title="Added new code from #6242; fixes #6242">[78023]</a>) Added new code from <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/6242" title="#6242: Bugs: isomorphism doesn't reset mapping (closed: fixed)">#6242</a>; fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/6242" title="#6242: Bugs: isomorphism doesn't reset mapping (closed: fixed)">#6242</a> </p> Ticket