Ticket #5881 (closed Bugs: fixed)
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
Change History
comment:2 in reply to: ↑ 1 Changed 5 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 5 years ago by Esa Määttä <esa.maatta@…>
- attachment gdb_efence_where.log added
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 5 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 5 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 5 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 5 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).
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?