Modify

Opened 6 years ago

Closed 5 years ago

#6242 closed Bugs (fixed)

isomorphism doesn't reset mapping

Reported by: dgleich@… Owned by: jewillco
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@…

Changed 6 years ago by dgleich@…

comment:1 Changed 5 years ago by jewillco

  • Resolution set to fixed
  • Status changed from new to closed

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

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain jewillco.
The resolution will be deleted. Next status will be 'reopened'.
Author


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

 
Note: See TracTickets for help on using tickets.