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.