williamr@2: // Copyright (C) 2001 Jeremy Siek, Douglas Gregor, Brian Osman williamr@2: // williamr@2: // Distributed under the Boost Software License, Version 1.0. (See williamr@2: // accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: #ifndef BOOST_GRAPH_ISOMORPHISM_HPP williamr@2: #define BOOST_GRAPH_ISOMORPHISM_HPP williamr@2: williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include // for make_indirect_pmap williamr@2: williamr@2: #ifndef BOOST_GRAPH_ITERATION_MACROS_HPP williamr@2: #define BOOST_ISO_INCLUDED_ITER_MACROS // local macro, see bottom of file williamr@2: #include williamr@2: #endif williamr@2: williamr@2: namespace boost { williamr@2: williamr@2: namespace detail { williamr@2: williamr@2: template williamr@2: class isomorphism_algo williamr@2: { williamr@2: typedef typename graph_traits::vertex_descriptor vertex1_t; williamr@2: typedef typename graph_traits::vertex_descriptor vertex2_t; williamr@2: typedef typename graph_traits::edge_descriptor edge1_t; williamr@2: typedef typename graph_traits::vertices_size_type size_type; williamr@2: typedef typename Invariant1::result_type invar1_value; williamr@2: typedef typename Invariant2::result_type invar2_value; williamr@2: williamr@2: const Graph1& G1; williamr@2: const Graph2& G2; williamr@2: IsoMapping f; williamr@2: Invariant1 invariant1; williamr@2: Invariant2 invariant2; williamr@2: std::size_t max_invariant; williamr@2: IndexMap1 index_map1; williamr@2: IndexMap2 index_map2; williamr@2: williamr@2: std::vector dfs_vertices; williamr@2: typedef typename std::vector::iterator vertex_iter; williamr@2: std::vector dfs_num_vec; williamr@2: typedef safe_iterator_property_map::iterator, williamr@2: IndexMap1 williamr@2: #ifdef BOOST_NO_STD_ITERATOR_TRAITS williamr@2: , int, int& williamr@2: #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ williamr@2: > DFSNumMap; williamr@2: DFSNumMap dfs_num; williamr@2: std::vector ordered_edges; williamr@2: typedef typename std::vector::iterator edge_iter; williamr@2: williamr@2: std::vector in_S_vec; williamr@2: typedef safe_iterator_property_map::iterator, williamr@2: IndexMap2 williamr@2: #ifdef BOOST_NO_STD_ITERATOR_TRAITS williamr@2: , char, char& williamr@2: #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ williamr@2: > InSMap; williamr@2: InSMap in_S; williamr@2: williamr@2: int num_edges_on_k; williamr@2: williamr@2: friend struct compare_multiplicity; williamr@2: struct compare_multiplicity williamr@2: { williamr@2: compare_multiplicity(Invariant1 invariant1, size_type* multiplicity) williamr@2: : invariant1(invariant1), multiplicity(multiplicity) { } williamr@2: bool operator()(const vertex1_t& x, const vertex1_t& y) const { williamr@2: return multiplicity[invariant1(x)] < multiplicity[invariant1(y)]; williamr@2: } williamr@2: Invariant1 invariant1; williamr@2: size_type* multiplicity; williamr@2: }; williamr@2: williamr@2: struct record_dfs_order : default_dfs_visitor williamr@2: { williamr@2: record_dfs_order(std::vector& v, std::vector& e) williamr@2: : vertices(v), edges(e) { } williamr@2: williamr@2: void discover_vertex(vertex1_t v, const Graph1&) const { williamr@2: vertices.push_back(v); williamr@2: } williamr@2: void examine_edge(edge1_t e, const Graph1& G1) const { williamr@2: edges.push_back(e); williamr@2: } williamr@2: std::vector& vertices; williamr@2: std::vector& edges; williamr@2: }; williamr@2: williamr@2: struct edge_cmp { williamr@2: edge_cmp(const Graph1& G1, DFSNumMap dfs_num) williamr@2: : G1(G1), dfs_num(dfs_num) { } williamr@2: bool operator()(const edge1_t& e1, const edge1_t& e2) const { williamr@2: using namespace std; williamr@2: int u1 = dfs_num[source(e1,G1)], v1 = dfs_num[target(e1,G1)]; williamr@2: int u2 = dfs_num[source(e2,G1)], v2 = dfs_num[target(e2,G1)]; williamr@2: int m1 = (max)(u1, v1); williamr@2: int m2 = (max)(u2, v2); williamr@2: // lexicographical comparison williamr@2: return std::make_pair(m1, std::make_pair(u1, v1)) williamr@2: < std::make_pair(m2, std::make_pair(u2, v2)); williamr@2: } williamr@2: const Graph1& G1; williamr@2: DFSNumMap dfs_num; williamr@2: }; williamr@2: williamr@2: public: williamr@2: isomorphism_algo(const Graph1& G1, const Graph2& G2, IsoMapping f, williamr@2: Invariant1 invariant1, Invariant2 invariant2, std::size_t max_invariant, williamr@2: IndexMap1 index_map1, IndexMap2 index_map2) williamr@2: : G1(G1), G2(G2), f(f), invariant1(invariant1), invariant2(invariant2), williamr@2: max_invariant(max_invariant), williamr@2: index_map1(index_map1), index_map2(index_map2) williamr@2: { williamr@2: in_S_vec.resize(num_vertices(G1)); williamr@2: in_S = make_safe_iterator_property_map williamr@2: (in_S_vec.begin(), in_S_vec.size(), index_map2 williamr@2: #ifdef BOOST_NO_STD_ITERATOR_TRAITS williamr@2: , in_S_vec.front() williamr@2: #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ williamr@2: ); williamr@2: } williamr@2: williamr@2: bool test_isomorphism() williamr@2: { williamr@2: { williamr@2: std::vector invar1_array; williamr@2: BGL_FORALL_VERTICES_T(v, G1, Graph1) williamr@2: invar1_array.push_back(invariant1(v)); williamr@2: sort(invar1_array); williamr@2: williamr@2: std::vector invar2_array; williamr@2: BGL_FORALL_VERTICES_T(v, G2, Graph2) williamr@2: invar2_array.push_back(invariant2(v)); williamr@2: sort(invar2_array); williamr@2: if (! equal(invar1_array, invar2_array)) williamr@2: return false; williamr@2: } williamr@2: williamr@2: std::vector V_mult; williamr@2: BGL_FORALL_VERTICES_T(v, G1, Graph1) williamr@2: V_mult.push_back(v); williamr@2: { williamr@2: std::vector multiplicity(max_invariant, 0); williamr@2: BGL_FORALL_VERTICES_T(v, G1, Graph1) williamr@2: ++multiplicity[invariant1(v)]; williamr@2: sort(V_mult, compare_multiplicity(invariant1, &multiplicity[0])); williamr@2: } williamr@2: williamr@2: std::vector color_vec(num_vertices(G1)); williamr@2: safe_iterator_property_map::iterator, williamr@2: IndexMap1 williamr@2: #ifdef BOOST_NO_STD_ITERATOR_TRAITS williamr@2: , default_color_type, default_color_type& williamr@2: #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ williamr@2: > williamr@2: color_map(color_vec.begin(), color_vec.size(), index_map1); williamr@2: record_dfs_order dfs_visitor(dfs_vertices, ordered_edges); williamr@2: typedef color_traits Color; williamr@2: for (vertex_iter u = V_mult.begin(); u != V_mult.end(); ++u) { williamr@2: if (color_map[*u] == Color::white()) { williamr@2: dfs_visitor.start_vertex(*u, G1); williamr@2: depth_first_visit(G1, *u, dfs_visitor, color_map); williamr@2: } williamr@2: } williamr@2: // Create the dfs_num array and dfs_num_map williamr@2: dfs_num_vec.resize(num_vertices(G1)); williamr@2: dfs_num = make_safe_iterator_property_map(dfs_num_vec.begin(), williamr@2: dfs_num_vec.size(), williamr@2: index_map1 williamr@2: #ifdef BOOST_NO_STD_ITERATOR_TRAITS williamr@2: , dfs_num_vec.front() williamr@2: #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ williamr@2: ); williamr@2: size_type n = 0; williamr@2: for (vertex_iter v = dfs_vertices.begin(); v != dfs_vertices.end(); ++v) williamr@2: dfs_num[*v] = n++; williamr@2: williamr@2: sort(ordered_edges, edge_cmp(G1, dfs_num)); williamr@2: williamr@2: williamr@2: int dfs_num_k = -1; williamr@2: return this->match(ordered_edges.begin(), dfs_num_k); williamr@2: } williamr@2: williamr@2: private: williamr@2: bool match(edge_iter iter, int dfs_num_k) williamr@2: { williamr@2: if (iter != ordered_edges.end()) { williamr@2: vertex1_t i = source(*iter, G1), j = target(*iter, G2); williamr@2: if (dfs_num[i] > dfs_num_k) { williamr@2: vertex1_t kp1 = dfs_vertices[dfs_num_k + 1]; williamr@2: BGL_FORALL_VERTICES_T(u, G2, Graph2) { williamr@2: if (invariant1(kp1) == invariant2(u) && in_S[u] == false) { williamr@2: f[kp1] = u; williamr@2: in_S[u] = true; williamr@2: num_edges_on_k = 0; williamr@2: williamr@2: if (match(iter, dfs_num_k + 1)) williamr@2: #if 0 williamr@2: // dwa 2003/7/11 -- this *HAS* to be a bug! williamr@2: ; williamr@2: #endif williamr@2: return true; williamr@2: williamr@2: in_S[u] = false; williamr@2: } williamr@2: } williamr@2: williamr@2: } williamr@2: else if (dfs_num[j] > dfs_num_k) { williamr@2: vertex1_t k = dfs_vertices[dfs_num_k]; williamr@2: num_edges_on_k -= williamr@2: count_if(adjacent_vertices(f[k], G2), make_indirect_pmap(in_S)); williamr@2: williamr@2: for (int jj = 0; jj < dfs_num_k; ++jj) { williamr@2: vertex1_t j = dfs_vertices[jj]; williamr@2: num_edges_on_k -= count(adjacent_vertices(f[j], G2), f[k]); williamr@2: } williamr@2: williamr@2: if (num_edges_on_k != 0) williamr@2: return false; williamr@2: BGL_FORALL_ADJ_T(f[i], v, G2, Graph2) williamr@2: if (invariant2(v) == invariant1(j) && in_S[v] == false) { williamr@2: f[j] = v; williamr@2: in_S[v] = true; williamr@2: num_edges_on_k = 1; williamr@2: BOOST_USING_STD_MAX(); williamr@2: int next_k = max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num_k, max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num[i], dfs_num[j])); williamr@2: if (match(next(iter), next_k)) williamr@2: return true; williamr@2: in_S[v] = false; williamr@2: } williamr@2: williamr@2: williamr@2: } williamr@2: else { williamr@2: if (contains(adjacent_vertices(f[i], G2), f[j])) { williamr@2: ++num_edges_on_k; williamr@2: if (match(next(iter), dfs_num_k)) williamr@2: return true; williamr@2: } williamr@2: williamr@2: } williamr@2: } else williamr@2: return true; williamr@2: return false; williamr@2: } williamr@2: williamr@2: }; williamr@2: williamr@2: williamr@2: template williamr@2: void compute_in_degree(const Graph& g, InDegreeMap in_degree_map) williamr@2: { williamr@2: BGL_FORALL_VERTICES_T(v, g, Graph) williamr@2: put(in_degree_map, v, 0); williamr@2: williamr@2: BGL_FORALL_VERTICES_T(u, g, Graph) williamr@2: BGL_FORALL_ADJ_T(u, v, g, Graph) williamr@2: put(in_degree_map, v, get(in_degree_map, v) + 1); williamr@2: } williamr@2: williamr@2: } // namespace detail williamr@2: williamr@2: williamr@2: template williamr@2: class degree_vertex_invariant williamr@2: { williamr@2: typedef typename graph_traits::vertex_descriptor vertex_t; williamr@2: typedef typename graph_traits::degree_size_type size_type; williamr@2: public: williamr@2: typedef vertex_t argument_type; williamr@2: typedef size_type result_type; williamr@2: williamr@2: degree_vertex_invariant(const InDegreeMap& in_degree_map, const Graph& g) williamr@2: : m_in_degree_map(in_degree_map), m_g(g) { } williamr@2: williamr@2: size_type operator()(vertex_t v) const { williamr@2: return (num_vertices(m_g) + 1) * out_degree(v, m_g) williamr@2: + get(m_in_degree_map, v); williamr@2: } williamr@2: // The largest possible vertex invariant number williamr@2: size_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { williamr@2: return num_vertices(m_g) * num_vertices(m_g) + num_vertices(m_g); williamr@2: } williamr@2: private: williamr@2: InDegreeMap m_in_degree_map; williamr@2: const Graph& m_g; williamr@2: }; williamr@2: williamr@2: williamr@2: template williamr@2: bool isomorphism(const Graph1& G1, const Graph2& G2, IsoMapping f, williamr@2: Invariant1 invariant1, Invariant2 invariant2, williamr@2: std::size_t max_invariant, williamr@2: IndexMap1 index_map1, IndexMap2 index_map2) williamr@2: williamr@2: { williamr@2: // Graph requirements williamr@2: function_requires< VertexListGraphConcept >(); williamr@2: function_requires< EdgeListGraphConcept >(); williamr@2: function_requires< VertexListGraphConcept >(); williamr@2: function_requires< BidirectionalGraphConcept >(); williamr@2: williamr@2: typedef typename graph_traits::vertex_descriptor vertex1_t; williamr@2: typedef typename graph_traits::vertex_descriptor vertex2_t; williamr@2: typedef typename graph_traits::vertices_size_type size_type; williamr@2: williamr@2: // Vertex invariant requirement williamr@2: function_requires< AdaptableUnaryFunctionConcept >(); williamr@2: function_requires< AdaptableUnaryFunctionConcept >(); williamr@2: williamr@2: // Property map requirements williamr@2: function_requires< ReadWritePropertyMapConcept >(); williamr@2: typedef typename property_traits::value_type IsoMappingValue; williamr@2: BOOST_STATIC_ASSERT((is_same::value)); williamr@2: williamr@2: function_requires< ReadablePropertyMapConcept >(); williamr@2: typedef typename property_traits::value_type IndexMap1Value; williamr@2: BOOST_STATIC_ASSERT((is_convertible::value)); williamr@2: williamr@2: function_requires< ReadablePropertyMapConcept >(); williamr@2: typedef typename property_traits::value_type IndexMap2Value; williamr@2: BOOST_STATIC_ASSERT((is_convertible::value)); williamr@2: williamr@2: if (num_vertices(G1) != num_vertices(G2)) williamr@2: return false; williamr@2: if (num_vertices(G1) == 0 && num_vertices(G2) == 0) williamr@2: return true; williamr@2: williamr@2: detail::isomorphism_algo williamr@2: algo(G1, G2, f, invariant1, invariant2, max_invariant, williamr@2: index_map1, index_map2); williamr@2: return algo.test_isomorphism(); williamr@2: } williamr@2: williamr@2: williamr@2: namespace detail { williamr@2: williamr@2: template williamr@2: bool isomorphism_impl(const Graph1& G1, const Graph2& G2, williamr@2: IsoMapping f, IndexMap1 index_map1, IndexMap2 index_map2, williamr@2: const bgl_named_params& params) williamr@2: { williamr@2: std::vector in_degree1_vec(num_vertices(G1)); williamr@2: typedef safe_iterator_property_map::iterator, williamr@2: IndexMap1 williamr@2: #ifdef BOOST_NO_STD_ITERATOR_TRAITS williamr@2: , std::size_t, std::size_t& williamr@2: #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ williamr@2: > InDeg1; williamr@2: InDeg1 in_degree1(in_degree1_vec.begin(), in_degree1_vec.size(), index_map1); williamr@2: compute_in_degree(G1, in_degree1); williamr@2: williamr@2: std::vector in_degree2_vec(num_vertices(G2)); williamr@2: typedef safe_iterator_property_map::iterator, williamr@2: IndexMap2 williamr@2: #ifdef BOOST_NO_STD_ITERATOR_TRAITS williamr@2: , std::size_t, std::size_t& williamr@2: #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ williamr@2: > InDeg2; williamr@2: InDeg2 in_degree2(in_degree2_vec.begin(), in_degree2_vec.size(), index_map2); williamr@2: compute_in_degree(G2, in_degree2); williamr@2: williamr@2: degree_vertex_invariant invariant1(in_degree1, G1); williamr@2: degree_vertex_invariant invariant2(in_degree2, G2); williamr@2: williamr@2: return isomorphism(G1, G2, f, williamr@2: choose_param(get_param(params, vertex_invariant1_t()), invariant1), williamr@2: choose_param(get_param(params, vertex_invariant2_t()), invariant2), williamr@2: choose_param(get_param(params, vertex_max_invariant_t()), (invariant2.max)()), williamr@2: index_map1, index_map2 williamr@2: ); williamr@2: } williamr@2: williamr@2: } // namespace detail williamr@2: williamr@2: williamr@2: // Named parameter interface williamr@2: template williamr@2: bool isomorphism(const Graph1& g1, williamr@2: const Graph2& g2, williamr@2: const bgl_named_params& params) williamr@2: { williamr@2: typedef typename graph_traits::vertex_descriptor vertex2_t; williamr@2: typename std::vector::size_type n = num_vertices(g1); williamr@2: std::vector f(n); williamr@2: return detail::isomorphism_impl williamr@2: (g1, g2, williamr@2: choose_param(get_param(params, vertex_isomorphism_t()), williamr@2: make_safe_iterator_property_map(f.begin(), f.size(), williamr@2: choose_const_pmap(get_param(params, vertex_index1), williamr@2: g1, vertex_index), vertex2_t())), williamr@2: choose_const_pmap(get_param(params, vertex_index1), g1, vertex_index), williamr@2: choose_const_pmap(get_param(params, vertex_index2), g2, vertex_index), williamr@2: params williamr@2: ); williamr@2: } williamr@2: williamr@2: // All defaults interface williamr@2: template williamr@2: bool isomorphism(const Graph1& g1, const Graph2& g2) williamr@2: { williamr@2: return isomorphism(g1, g2, williamr@2: bgl_named_params(0));// bogus named param williamr@2: } williamr@2: williamr@2: williamr@2: // Verify that the given mapping iso_map from the vertices of g1 to the williamr@2: // vertices of g2 describes an isomorphism. williamr@2: // Note: this could be made much faster by specializing based on the graph williamr@2: // concepts modeled, but since we're verifying an O(n^(lg n)) algorithm, williamr@2: // O(n^4) won't hurt us. williamr@2: template williamr@2: inline bool verify_isomorphism(const Graph1& g1, const Graph2& g2, IsoMap iso_map) williamr@2: { williamr@2: #if 0 williamr@2: // problematic for filtered_graph! williamr@2: if (num_vertices(g1) != num_vertices(g2) || num_edges(g1) != num_edges(g2)) williamr@2: return false; williamr@2: #endif williamr@2: williamr@2: for (typename graph_traits::edge_iterator e1 = edges(g1).first; williamr@2: e1 != edges(g1).second; ++e1) { williamr@2: bool found_edge = false; williamr@2: for (typename graph_traits::edge_iterator e2 = edges(g2).first; williamr@2: e2 != edges(g2).second && !found_edge; ++e2) { williamr@2: if (source(*e2, g2) == get(iso_map, source(*e1, g1)) && williamr@2: target(*e2, g2) == get(iso_map, target(*e1, g1))) { williamr@2: found_edge = true; williamr@2: } williamr@2: } williamr@2: williamr@2: if (!found_edge) williamr@2: return false; williamr@2: } williamr@2: williamr@2: return true; williamr@2: } williamr@2: williamr@2: } // namespace boost williamr@2: williamr@2: #ifdef BOOST_ISO_INCLUDED_ITER_MACROS williamr@2: #undef BOOST_ISO_INCLUDED_ITER_MACROS williamr@2: #include williamr@2: #endif williamr@2: williamr@2: #endif // BOOST_GRAPH_ISOMORPHISM_HPP