[Boost-bugs] [Boost C++ Libraries] #6242: isomorphism doesn't reset mapping

Subject: [Boost-bugs] [Boost C++ Libraries] #6242: isomorphism doesn't reset mapping
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-12-08 22:35:14

#6242: isomorphism doesn't reset mapping
--------------------------------+-------------------------------------------
 Reporter:  dgleich@…           |       Owner:  jewillco
     Type:  Bugs                |      Status:  new     
Milestone:  To Be Determined    |   Component:  graph   
  Version:  Boost 1.48.0        |    Severity:  Problem 
 Keywords:                      |  
--------------------------------+-------------------------------------------
 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)

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