BGL isomorphism: off-by-one error in isomorphism.hpp

[Esa Määttä <esa.maatta@…>]

While in test_isomorphism() when creating a multiplicity vector, the vector is possibly indexed with max_invariant while it's max index is max_invariant-1.

The code in question is:

154           std::vector<size_type> multiplicity(max_invariant, 0);
155           BGL_FORALL_VERTICES_T(v, G1, Graph1)
156             ++multiplicity[invariant1(v)];

Simple fix for this is to change the line 154 to:

154           std::vector<size_type> multiplicity(max_invariant+1, 0);

[Jeremiah Willcock]

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?

[Esa Määttä <esa.maatta@…>]

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

[Esa Määttä <esa.maatta@…>]

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]

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?

[Esa Määttä <esa.maatta@…>]

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]

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

[bastianra@…]

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).

[Jeremiah Willcock]

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