Modify

Ticket #5881 (closed Bugs: fixed)

Opened 3 years ago

Last modified 2 years ago

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

Reported by: Esa Määttä <esa.maatta@…> Owned by: jewillco
Milestone: To Be Determined Component: graph
Version: Boost 1.47.0 Severity: Problem
Keywords: Cc:

Description

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

Attachments

gdb_efence_where.log Download (13.3 KB) - added by Esa Määttä <esa.maatta@…> 3 years ago.
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

Change History

comment:1 follow-up: ↓ 2 Changed 3 years ago by 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?

comment:2 in reply to: ↑ 1 Changed 3 years ago by 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

Changed 3 years ago by 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

comment:3 follow-up: ↓ 4 Changed 3 years ago by 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?

comment:4 in reply to: ↑ 3 Changed 3 years ago by 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.

comment:5 Changed 3 years ago by jewillco

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

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

comment:7 Changed 2 years ago by jewillco

  • Status changed from new to closed
  • Resolution set to fixed

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

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.