Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r68979 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2011-02-17 18:00:21


Author: jewillco
Date: 2011-02-17 18:00:20 EST (Thu, 17 Feb 2011)
New Revision: 68979
URL: http://svn.boost.org/trac/boost/changeset/68979

Log:
Fixed buffer overflow from parallel edges in isomorphism(); fixes #5175
Text files modified:
   trunk/boost/graph/isomorphism.hpp | 18 +++++++++++++++---
   1 files changed, 15 insertions(+), 3 deletions(-)

Modified: trunk/boost/graph/isomorphism.hpp
==============================================================================
--- trunk/boost/graph/isomorphism.hpp (original)
+++ trunk/boost/graph/isomorphism.hpp 2011-02-17 18:00:20 EST (Thu, 17 Feb 2011)
@@ -284,18 +284,30 @@
     typedef size_type result_type;
 
     degree_vertex_invariant(const InDegreeMap& in_degree_map, const Graph& g)
- : m_in_degree_map(in_degree_map), m_g(g) { }
+ : m_in_degree_map(in_degree_map),
+ m_max_vertex_in_degree(0),
+ m_max_vertex_out_degree(0),
+ m_g(g) {
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ m_max_vertex_in_degree =
+ (std::max)(m_max_vertex_in_degree, get(m_in_degree_map, v));
+ m_max_vertex_out_degree =
+ (std::max)(m_max_vertex_out_degree, out_degree(v, g));
+ }
+ }
 
     size_type operator()(vertex_t v) const {
- return (num_vertices(m_g) + 1) * out_degree(v, m_g)
+ 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 num_vertices(m_g) * num_vertices(m_g) + num_vertices(m_g);
+ return (m_max_vertex_in_degree + 2) * m_max_vertex_out_degree + 1;
     }
   private:
     InDegreeMap m_in_degree_map;
+ size_type m_max_vertex_in_degree;
+ size_type m_max_vertex_out_degree;
     const Graph& m_g;
   };
 


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk