id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
6242,isomorphism doesn't reset mapping,dgleich@…,Jeremiah Willcock,"It seems there is a problem with the isomorphism function not resetting data from the IsoMapping variable between function calls and certain types of graphs.  

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.

Manually resetting the IsoMapping 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.  

Here is call to compile and an explanation of the problem:

g++ --version
g++ (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5

Illustration of the problem
---------------------------

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.

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)

Fix for problem
---------------

I've attached a potential fix that simply resets the mapping data at the start of the test_isomorphism function.

This shows the correct output (although the labels on the cases are no longer true :-))

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)


",Bugs,closed,To Be Determined,graph,Boost 1.48.0,Problem,fixed,,