Boost C++ Libraries: Ticket #5881: BGL isomorphism: off-by-one error in isomorphism.hpp

Jeremiah Willcock — Fri, 09 Sep 2011 15:36:20 GMT

This code appears to be correct using the definition of max_invariant in the documentation. Is the test case incorrect, or do you think isomorphism itself is incorrect?

Sat, 10 Sep 2011 10:56:14 GMT

Replying to jewillco:

This code appears to be correct using the definition of max_invariant in the documentation. Is the test case incorrect, or do you think isomorphism itself is incorrect?

You can test it by changing the indexing of the multiplicity vector to .at() and with a simple two node graph:

digraph G {
0;
1;
0->1 ;
1->1 ;
}

And with code like this:

154           std::vector<size_type> multiplicity(max_invariant, 0);
155           BGL_FORALL_VERTICES_T(v, G1, Graph1) {
156             std::cout << "v: " << v << ", " << "invariant(v): " << invariant1(v)
157                       << ", max_invariant: " << max_invariant << std::endl;
158             ++multiplicity.at(invariant1(v));
159           }

The output for me is:

v: 0, invariant(v): 3, max_invariant: 5
v: 1, invariant(v): 5, max_invariant: 5
terminate called without an active exception
Aborted

attachment set

Sat, 10 Sep 2011 11:24:49 GMT

attachment → gdb_efence_where.log

Log of gdb where command, when a program is compiled with efence. Indexing multiplicty vector causes segfault at /usr/include/boost/graph/isomorphism.hpp:156

Jeremiah Willcock — Sat, 10 Sep 2011 17:48:08 GMT

I ran a variant of the Boost.Graph isomorphism test with your graph and the replacement with .at() done, and nothing failed. This was with the trunk version of Boost. Is your code passing in custom invariant maps or a custom max_invariant value?

Sun, 11 Sep 2011 07:33:13 GMT

Replying to jewillco:

I ran a variant of the Boost.Graph isomorphism test with your graph and the replacement with .at() done, and nothing failed. This was with the trunk version of Boost. Is your code passing in custom invariant maps or a custom max_invariant value?

Nope, I'm just calling the isomorphism algorithm like in some examples:

isomorphism(g1, g2, isomorphism_map(..))

So the problem is probably in how I define the Graph type or initialize it. Here's the Graph type I use:

// Define internal vertex properties
typedef boost::property<boost::vertex_color_t, boost::default_color_type,
        boost::property<boost::vertex_index_t, int,
        boost::property<boost::vertex_degree_t, int,
        boost::property<boost::vertex_in_degree_t, int,
        boost::property<boost::vertex_out_degree_t, int> > > > > VertexProperties;
// Define used edge properties                                                                                 
typedef boost::property<boost::edge_color_t, boost::default_color_type,
        boost::property<boost::edge_index_t, int> > EdgeProperties;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS,
                              VertexProperties, EdgeProperties> Graph;

If above doesn't help I'll try to construct a simple test case when I have time. Also I'm using 1.47.0, haven't yet tested with trunk.

Jeremiah Willcock — Mon, 12 Sep 2011 15:07:31 GMT

I think you will need to create a test case, or at least put your entire call to isomorphism.

bastianra@… — Fri, 28 Oct 2011 15:58:51 GMT

I am experiencing the same issue. To me it seems the problem lies in the implementation of degree_vertex_invariant (starting at line 299 in trunk):

    size_type operator()(vertex_t v) const {
      return (m_max_vertex_in_degree + 1) * out_degree(v, m_g)
        + get(m_in_degree_map, v);
    }
    // The largest possible vertex invariant number
    size_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const {
      return (m_max_vertex_in_degree + 2) * m_max_vertex_out_degree + 1;
    }

consider a vertex with in_degree==10 and out_degree==1, and assume both are the maximum values. operator() will return (10+1)*1+10, i.e. 21, however the value of max is (10+2)*1+1 i.e. 13.

replacing max with

    size_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const {
      return (m_max_vertex_in_degree + 1) * m_max_vertex_out_degree + m_max_vertex_in_degree + 1;
    }

resolved the issue (tested only in 1_47_0 with a few of my own graphs, not tested in trunk).

status changed; resolution set

Jeremiah Willcock — Sat, 29 Oct 2011 06:11:05 GMT

status new → closed
resolution → fixed

(In [75165]) Fixed degree_vertex_invariant::max; fixes #5881