Boost C++ Libraries: Ticket #12614: Boost graph vf2 isomorphism algo runs for ever for this test case https://svn.boost.org/trac10/ticket/12614 <p> Boost graph vf2 isomorphism algo runs for ever for this test case Steps to reproduce: </p> <ol><li>Unzip the attached file, you should see three files </li><li>Add the cpp file to your build system </li><li>Compile and execute. </li></ol><hr /> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/12614 Trac 1.4.3 Praveen Vs <praveen_v-s@…> Mon, 21 Nov 2016 08:22:11 GMT attachment set https://svn.boost.org/trac10/ticket/12614 https://svn.boost.org/trac10/ticket/12614 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">vf2Test.7z</span> </li> </ul> Ticket Flavio De Lorenzi <fdlorenzi@…> Wed, 23 Nov 2016 14:10:41 GMT <link>https://svn.boost.org/trac10/ticket/12614#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/12614#comment:1</guid> <description> <p> Hi,<br /> I tried to run your test, but <code>gtest/gtest.h</code> 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?<br /> Regards,<br /> Flavio </p> </description> <category>Ticket</category> </item> <item> <author>Praveen Vs <praveen_v-s@…></author> <pubDate>Wed, 23 Nov 2016 16:10:55 GMT</pubDate> <title>attachment set https://svn.boost.org/trac10/ticket/12614 https://svn.boost.org/trac10/ticket/12614 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">vf2Test_no_gtest.7z</span> </li> </ul> <p> No gtest dependency code </p> Ticket Praveen Vs <praveen_v-s@…> Wed, 23 Nov 2016 16:13:36 GMT <link>https://svn.boost.org/trac10/ticket/12614#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/12614#comment:2</guid> <description> <p> 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 </p> </description> <category>Ticket</category> </item> </channel> </rss>