**Subject:** [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs

**From:** Boost C++ Libraries (*noreply_at_[hidden]*)

**Date:** 2012-02-17 19:13:01

**Next message:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Previous message:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6572: typo in boost unit test framework documentation"**Next in thread:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Reply:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Reply:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Reply:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Reply:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Reply:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"

#6573: BGL: boost::isomorphism routine fails with large graphs

----------------------------------------------+-----------------------------

Reporter: Andras Pap <andraspap@â€¦> | Owner: jewillco

Type: Bugs | Status: new

Milestone: To Be Determined | Component: graph

Version: Boost 1.48.0 | Severity: Problem

Keywords: |

----------------------------------------------+-----------------------------

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.

-- Ticket URL: <https://svn.boost.org/trac/boost/ticket/6573> Boost C++ Libraries <http://www.boost.org/> Boost provides free peer-reviewed portable C++ source libraries.

**Next message:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Previous message:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6572: typo in boost unit test framework documentation"**Next in thread:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Reply:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Reply:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Reply:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Reply:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"**Reply:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #6573: BGL: boost::isomorphism routine fails with large graphs"

*
This archive was generated by hypermail 2.1.7
: 2017-02-16 18:50:09 UTC
*