Re: [Boost-bugs] [Boost C++ Libraries] #5881: BGL isomorphism: off-by-one error in isomorphism.hpp

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