[Boost-commit] svn:boost r68979 - trunk/boost/graph

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;
   };