Subject: Re: [Boost-bugs] [Boost C++ Libraries] #5881: BGL isomorphism: off-by-one error in isomorphism.hpp
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-10-28 15:58:51
#5881: BGL isomorphism: off-by-one error in isomorphism.hpp
---------------------------------------------+------------------------------
Reporter: Esa Määttä <esa.maatta@â¦> | Owner: jewillco
Type: Bugs | Status: new
Milestone: To Be Determined | Component: graph
Version: Boost 1.47.0 | Severity: Problem
Resolution: | Keywords:
---------------------------------------------+------------------------------
Comment (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)'''.
-- Ticket URL: <https://svn.boost.org/trac/boost/ticket/5881#comment:6> Boost C++ Libraries <http://www.boost.org/> Boost provides free peer-reviewed portable C++ source libraries.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:07 UTC