Boost C++ Libraries: Ticket #6573: BGL: boost::isomorphism routine fails with large graphs

attachment set

Fri, 17 Feb 2012 19:13:40 GMT

attachment → SimpleGraphTest.cpp

attachment set

Fri, 17 Feb 2012 19:13:55 GMT

attachment → Makefile.NT40

attachment set

Fri, 17 Feb 2012 19:14:11 GMT

attachment → Makefile.linux

status changed

Jeremiah Willcock — Fri, 17 Feb 2012 19:42:55 GMT

status new → assigned

I can reproduce the problem with your test code; it seems to be a too-deep recursion when the graph gets large. I'll try to fix it, but it looks complicated to do and I probably won't be able to get to it for a few days.

Fri, 24 Feb 2012 13:42:57 GMT

Thank you very much for your immediate response. I would be happy to look into this issue if you could give me some pointers to the possible source of the problem or a hint for a possible solution/workaround.

Jeremiah Willcock — Fri, 24 Feb 2012 14:35:01 GMT

Replying to Andras Pap <andraspap@…>:

Thank you very much for your immediate response. I would be happy to look into this issue if you could give me some pointers to the possible source of the problem or a hint for a possible solution/workaround.

The problem is isomorphism_algo::match in <boost/graph/isomorphism.hpp>. That function contains a recursion-based DFS that will overflow the stack for large graphs. It should be using the BGL DFS algorithm or an explicit stack that will not cause the system stack to overflow.

status changed; resolution set

Jeremiah Willcock — Sat, 03 Mar 2012 20:02:30 GMT

status assigned → closed
resolution → fixed

(In [77185]) Changed to trampolined implementation of match() to avoid stack overflows, now passes test case in #6573 with 10000 sides; fixes #6573

Mon, 05 Mar 2012 22:01:34 GMT

Thank you very much for the fix, it works great.