Opened 6 years ago
Closed 6 years ago
#5881 closed Bugs (fixed)
BGL isomorphism: off-by-one error in isomorphism.hpp
Reported by: | Owned by: | Jeremiah Willcock | |
---|---|---|---|
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 (1)
Change History (8)
comment:1 follow-up: 2 Changed 6 years ago by
comment:2 Changed 6 years ago by
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 thinkisomorphism
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 6 years ago by
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 6 years ago by
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 Changed 6 years ago by
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 custommax_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 6 years ago by
I think you will need to create a test case, or at least put your entire call to isomorphism
.
comment:6 Changed 6 years ago by
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 6 years ago by
Resolution: | → fixed |
---|---|
Status: | new → closed |
This code appears to be correct using the definition of
max_invariant
in the documentation. Is the test case incorrect, or do you thinkisomorphism
itself is incorrect?