Opened 6 years ago

Last modified 6 years ago

#12614 new Bugs

Boost graph vf2 isomorphism algo runs for ever for this test case

Reported by: Praveen Vs <praveen_v-s@…> Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.53.0 Severity: Problem
Keywords: vf2 hang algorithm Cc:

Description

Boost graph vf2 isomorphism algo runs for ever for this test case Steps to reproduce:

  1. Unzip the attached file, you should see three files
  2. Add the cpp file to your build system
  3. Compile and execute.

Attachments (2)

vf2Test.7z​ (16.4 KB ) - added by Praveen Vs <praveen_v-s@…> 6 years ago.
vf2Test_no_gtest.7z​ (16.4 KB ) - added by Praveen Vs <praveen_v-s@…> 6 years ago.
No gtest dependency code

Download all attachments as: .zip

Change History (4)

by Praveen Vs <praveen_v-s@…>, 6 years ago

Attachment: vf2Test.7z​ added

comment:1 by Flavio De Lorenzi <fdlorenzi@…>, 6 years ago

Hi,
I tried to run your test, but gtest/gtest.h is missing. Also, your graphs have |V|=437 vertices. The worst-case time complexity is proportional to |V|!. Might this be the reason it did not (yet) finish?
Regards,
Flavio

by Praveen Vs <praveen_v-s@…>, 6 years ago

Attachment: vf2Test_no_gtest.7z​ added

No gtest dependency code

comment:2 by Praveen Vs <praveen_v-s@…>, 6 years ago

Hi Flavio, Thanks for your comment. Graphs larger than that works fine with acceptable run time. I think it has something to do with the type of graphs. The algorithm keeps backtracking to same vertices after some state. (I have attached a version of test case that doesn't use gtest now) -praveen

Note: See TracTickets for help on using tickets.