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

Subject: [Boost-commit] svn:boost r77185 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2012-03-03 15:02:28

Author: jewillco
Date: 2012-03-03 15:02:27 EST (Sat, 03 Mar 2012)
New Revision: 77185
URL: http://svn.boost.org/trac/boost/changeset/77185

Log:
Changed to trampolined implementation of match() to avoid stack overflows, now passes test case in #6573 with 10000 sides; fixes #6573
Text files modified: 
   trunk/boost/graph/isomorphism.hpp |   135 ++++++++++++++++++++++++++++----------- 
   1 files changed, 95 insertions(+), 40 deletions(-)

Modified: trunk/boost/graph/isomorphism.hpp
==============================================================================
--- trunk/boost/graph/isomorphism.hpp	(original)
+++ trunk/boost/graph/isomorphism.hpp	2012-03-03 15:02:27 EST (Sat, 03 Mar 2012)
@@ -11,6 +11,7 @@
 #include <iterator>
 #include <algorithm>
 #include <boost/config.hpp>
+#include <boost/smart_ptr.hpp>
 #include <boost/graph/depth_first_search.hpp>
 #include <boost/utility.hpp>
 #include <boost/detail/algorithm.hpp>
@@ -195,69 +196,123 @@
       }
     
     private:
+      struct match_continuation {
+        enum {pos_G2_vertex_loop, pos_fi_adj_loop, pos_dfs_num} position;
+        typedef typename graph_traits<Graph2>::vertex_iterator vertex_iterator;
+        std::pair<vertex_iterator, vertex_iterator> G2_verts;
+        typedef typename graph_traits<Graph2>::adjacency_iterator adjacency_iterator;
+        std::pair<adjacency_iterator, adjacency_iterator> fi_adj;
+        edge_iter iter;
+        int dfs_num_k;
+      };
+
       bool match(edge_iter iter, int dfs_num_k)
       {
+        std::vector<match_continuation> k;
+        typedef typename graph_traits<Graph2>::vertex_iterator vertex_iterator;
+        std::pair<vertex_iterator, vertex_iterator> G2_verts(vertices(G2));
+        typedef typename graph_traits<Graph2>::adjacency_iterator adjacency_iterator;
+        std::pair<adjacency_iterator, adjacency_iterator> fi_adj;
+        vertex1_t i, j;
+
+        recur:
         if (iter != ordered_edges.end()) {
-          vertex1_t i = source(*iter, G1), j = target(*iter, G2);
+          i = source(*iter, G1);
+          j = target(*iter, G2);
           if (dfs_num[i] > dfs_num_k) {
-            vertex1_t kp1 = dfs_vertices[dfs_num_k + 1];
-            BGL_FORALL_VERTICES_T(u, G2, Graph2) {
-              if (invariant1(kp1) == invariant2(u) && in_S[u] == false) {
-                f[kp1] = u;
-                in_S[u] = true;
-                num_edges_on_k = 0;
-                
-                if (match(iter, dfs_num_k + 1))
-#if 0
-                    // dwa 2003/7/11 -- this *HAS* to be a bug!
-                    ;
-#endif 
-                    return true;
+            G2_verts = vertices(G2);
+            while (G2_verts.first != G2_verts.second) {
+              {
+                vertex2_t u = *G2_verts.first;
+                vertex1_t kp1 = dfs_vertices[dfs_num_k + 1];
+                if (invariant1(kp1) == invariant2(u) && in_S[u] == false) {
+                  {
+                    f[kp1] = u;
+                    in_S[u] = true;
+                    num_edges_on_k = 0;
                     
-                in_S[u] = false;
+                    match_continuation new_k;
+                    new_k.position = match_continuation::pos_G2_vertex_loop;
+                    new_k.G2_verts = G2_verts;
+                    new_k.iter = iter;
+                    new_k.dfs_num_k = dfs_num_k;
+                    k.push_back(new_k);
+                    ++dfs_num_k;
+                    goto recur;
+                  }
+                }
               }
+G2_loop_k:    ++G2_verts.first;
             }
                
           }
           else if (dfs_num[j] > dfs_num_k) {
-            vertex1_t k = dfs_vertices[dfs_num_k];
-            num_edges_on_k -= 
-              count_if(adjacent_vertices(f[k], G2), make_indirect_pmap(in_S));
-                
-            for (int jj = 0; jj < dfs_num_k; ++jj) {
-              vertex1_t j = dfs_vertices[jj];
-              num_edges_on_k -= count(adjacent_vertices(f[j], G2), f[k]);
+            {
+              vertex1_t vk = dfs_vertices[dfs_num_k];
+              num_edges_on_k -= 
+                count_if(adjacent_vertices(f[vk], G2), make_indirect_pmap(in_S));
+                  
+              for (int jj = 0; jj < dfs_num_k; ++jj) {
+                vertex1_t j = dfs_vertices[jj];
+                num_edges_on_k -= count(adjacent_vertices(f[j], G2), f[vk]);
+              }
             }
                 
             if (num_edges_on_k != 0)
-              return false;
-            BGL_FORALL_ADJ_T(f[i], v, G2, Graph2)
-              if (invariant2(v) == invariant1(j) && in_S[v] == false) {
-                f[j] = v;
-                in_S[v] = true;
-                num_edges_on_k = 1;
-                BOOST_USING_STD_MAX();
-                int next_k = max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num_k, max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num[i], dfs_num[j]));
-                if (match(boost::next(iter), next_k))
-                  return true;
-                in_S[v] = false;
+              goto return_point_false;
+            fi_adj = adjacent_vertices(f[i], G2);
+            while (fi_adj.first != fi_adj.second) {
+              {
+                vertex2_t v = *fi_adj.first;
+                if (invariant2(v) == invariant1(j) && in_S[v] == false) {
+                  f[j] = v;
+                  in_S[v] = true;
+                  num_edges_on_k = 1;
+                  BOOST_USING_STD_MAX();
+                  int next_k = max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num_k, max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num[i], dfs_num[j]));
+                  match_continuation new_k;
+                  new_k.position = match_continuation::pos_fi_adj_loop;
+                  new_k.fi_adj = fi_adj;
+                  new_k.iter = iter;
+                  new_k.dfs_num_k = dfs_num_k;
+                  ++iter;
+                  dfs_num_k = next_k;
+                  k.push_back(new_k);
+                  goto recur;
+                }
               }
-                
-                
+fi_adj_loop_k:++fi_adj.first;
+            }
           }
           else {
             if (container_contains(adjacent_vertices(f[i], G2), f[j])) {
               ++num_edges_on_k;
-              if (match(boost::next(iter), dfs_num_k))
-                return true;
+              match_continuation new_k;
+              new_k.position = match_continuation::pos_dfs_num;
+              k.push_back(new_k);
+              ++iter;
+              goto recur;
             }
                 
           }
         } else 
-          return true;
-        return false;
-      }
+          goto return_point_true;
+        goto return_point_false;
     
+        {
+          return_point_true: return true;
+
+          return_point_false:
+          if (k.empty()) return false;
+          const match_continuation& this_k = k.back();
+          switch (this_k.position) {
+            case match_continuation::pos_G2_vertex_loop: {G2_verts = this_k.G2_verts; iter = this_k.iter; dfs_num_k = this_k.dfs_num_k; k.pop_back(); in_S[*G2_verts.first] = false; i = source(*iter, G1); j = target(*iter, G2); goto G2_loop_k;}
+            case match_continuation::pos_fi_adj_loop: {fi_adj = this_k.fi_adj; iter = this_k.iter; dfs_num_k = this_k.dfs_num_k; k.pop_back(); in_S[*fi_adj.first] = false; i = source(*iter, G1); j = target(*iter, G2); goto fi_adj_loop_k;}
+            case match_continuation::pos_dfs_num: {k.pop_back(); goto return_point_false;}
+            default: assert (!"Bad position"); abort();
+          }
+        }
+      }
     };