Modify

Opened 6 years ago

Closed 6 years ago

#6242 closed Bugs (fixed)

isomorphism doesn't reset mapping

Reported by: dgleich@… Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.48.0 Severity: Problem
Keywords: Cc:

Description

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)

Attachments (2)

isobug.cc (2.8 KB) - added by dgleich@… 6 years ago.
isomorphism_fixed.hpp (17.8 KB) - added by dgleich@… 6 years ago.

Download all attachments as: .zip

Change History (3)

Changed 6 years ago by dgleich@…

Attachment: isobug.cc added

Changed 6 years ago by dgleich@…

Attachment: isomorphism_fixed.hpp added

comment:1 Changed 6 years ago by Jeremiah Willcock

Resolution: fixed
Status: newclosed

(In [78023]) Added new code from #6242; fixes #6242

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Jeremiah Willcock.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.