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();
+ }
+ }
+ }
};