Modify

Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#6573 closed Bugs (fixed)

BGL: boost::isomorphism routine fails with large graphs

Reported by: Andras Pap <andraspap@…> Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.48.0 Severity: Problem
Keywords: Cc:

Description

I am not sure maybe this is a "known" limitation of the isomorphism routine. My test graphs are graphs of wire frames of polyhedra. (Vertices of a polyhedron are the vertices of the graph, edges of the polyhedron are the edges of the graph.) The test graphs are generated from simple "faceted cylinders", i.e. the top and the bottom of the polyhedron (a slab/column) are polygons with the same number of sides (3,4,5...) and the same number of facets between the top and the bottom polygons. So if the number of sides is 3 then the number of vertices is 6 and the number of edges is 9 (6,9), if the number of sides is 4 then the number of vertices/edges is (8,12), for a polyhedron with 'n' number of sides the number of vertices/edges are (2n,3n).

With large number of sides the isomorphism routine between two identical graphs fails with what is in the debugger looks like an infinite recursion. The number of sides where it fails varies from platform/architecture and compiler. For example on Windows with MSVC8 the first failure happens when the number of sides is 58 in 64bit/debug 138 in 64bit/optimize 140 in 32bit/debug and at 495 in 32bit/optimize. (Results with Intel compiler 11.1 are even poorer, it crashes with smaller sizes already.) On RHEL4 (32bit/gcc4.1.2) it crashed when the number of sides reached 4096, on RHEL5 (64bit/gcc4.1.2) it crashed at 8192 (didn't attempt to find the smallest number of sides where it still succeeds for that configuration).

I am attaching the Makefile-s that I am using on Windows and Linux, the problem is also reproducible with a standard Visual Studio project, in addition to the default setup only the include path to boost needs to be set.

Any help/hint is appreciated. Thank you.

Attachments (3)

SimpleGraphTest.cpp (2.9 KB) - added by Andras Pap <andraspap@…> 5 years ago.
Makefile.NT40 (2.6 KB) - added by Andras Pap <andraspap@…> 5 years ago.
Makefile.linux (2.3 KB) - added by Andras Pap <andraspap@…> 5 years ago.

Download all attachments as: .zip

Change History (8)

Changed 5 years ago by Andras Pap <andraspap@…>

Attachment: SimpleGraphTest.cpp added

Changed 5 years ago by Andras Pap <andraspap@…>

Attachment: Makefile.NT40 added

Changed 5 years ago by Andras Pap <andraspap@…>

Attachment: Makefile.linux added

comment:1 Changed 5 years ago by Jeremiah Willcock

Status: newassigned

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.

comment:2 Changed 5 years ago by 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.

comment:3 in reply to:  2 Changed 5 years ago by Jeremiah Willcock

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.

comment:4 Changed 5 years ago by Jeremiah Willcock

Resolution: fixed
Status: assignedclosed

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

comment:5 Changed 5 years ago by Andras Pap <andraspap@…>

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

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.