1 | // Copyright (C) 2001 Jeremy Siek, Douglas Gregor, Brian Osman |
2 | // |
3 | // Distributed under the Boost Software License, Version 1.0. (See |
4 | // accompanying file LICENSE_1_0.txt or copy at |
5 | // http://www.boost.org/LICENSE_1_0.txt) |
6 | #ifndef BOOST_GRAPH_ISOMORPHISM_HPP |
7 | #define BOOST_GRAPH_ISOMORPHISM_HPP |
8 | |
9 | #include <utility> |
10 | #include <vector> |
11 | #include <iterator> |
12 | #include <algorithm> |
13 | #include <boost/config.hpp> |
14 | #include <boost/assert.hpp> |
15 | #include <boost/smart_ptr.hpp> |
16 | #include <boost/graph/depth_first_search.hpp> |
17 | #include <boost/detail/algorithm.hpp> |
18 | #include <boost/pending/indirect_cmp.hpp> // for make_indirect_pmap |
19 | #include <boost/concept/assert.hpp> |
20 | |
21 | #ifndef BOOST_GRAPH_ITERATION_MACROS_HPP |
22 | #define BOOST_ISO_INCLUDED_ITER_MACROS // local macro, see bottom of file |
23 | #include <boost/graph/iteration_macros.hpp> |
24 | #endif |
25 | |
26 | namespace boost { |
27 | |
28 | namespace detail { |
29 | |
30 | template <typename Graph1, typename Graph2, typename IsoMapping, |
31 | typename Invariant1, typename Invariant2, |
32 | typename IndexMap1, typename IndexMap2> |
33 | class isomorphism_algo |
34 | { |
35 | typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t; |
36 | typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t; |
37 | typedef typename graph_traits<Graph1>::edge_descriptor edge1_t; |
38 | typedef typename graph_traits<Graph1>::vertices_size_type size_type; |
39 | typedef typename Invariant1::result_type invar1_value; |
40 | typedef typename Invariant2::result_type invar2_value; |
41 | |
42 | const Graph1& G1; |
43 | const Graph2& G2; |
44 | IsoMapping f; |
45 | Invariant1 invariant1; |
46 | Invariant2 invariant2; |
47 | std::size_t max_invariant; |
48 | IndexMap1 index_map1; |
49 | IndexMap2 index_map2; |
50 | |
51 | std::vector<vertex1_t> dfs_vertices; |
52 | typedef typename std::vector<vertex1_t>::iterator vertex_iter; |
53 | std::vector<int> dfs_num_vec; |
54 | typedef safe_iterator_property_map<typename std::vector<int>::iterator, |
55 | IndexMap1 |
56 | #ifdef BOOST_NO_STD_ITERATOR_TRAITS |
57 | , int, int& |
58 | #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ |
59 | > DFSNumMap; |
60 | DFSNumMap dfs_num; |
61 | std::vector<edge1_t> ordered_edges; |
62 | typedef typename std::vector<edge1_t>::iterator edge_iter; |
63 | |
64 | std::vector<char> in_S_vec; |
65 | typedef safe_iterator_property_map<typename std::vector<char>::iterator, |
66 | IndexMap2 |
67 | #ifdef BOOST_NO_STD_ITERATOR_TRAITS |
68 | , char, char& |
69 | #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ |
70 | > InSMap; |
71 | InSMap in_S; |
72 | |
73 | int num_edges_on_k; |
74 | |
75 | friend struct compare_multiplicity; |
76 | struct compare_multiplicity |
77 | { |
78 | compare_multiplicity(Invariant1 invariant1, size_type* multiplicity) |
79 | : invariant1(invariant1), multiplicity(multiplicity) { } |
80 | bool operator()(const vertex1_t& x, const vertex1_t& y) const { |
81 | return multiplicity[invariant1(x)] < multiplicity[invariant1(y)]; |
82 | } |
83 | Invariant1 invariant1; |
84 | size_type* multiplicity; |
85 | }; |
86 | |
87 | struct record_dfs_order : default_dfs_visitor |
88 | { |
89 | record_dfs_order(std::vector<vertex1_t>& v, std::vector<edge1_t>& e) |
90 | : vertices(v), edges(e) { } |
91 | |
92 | void discover_vertex(vertex1_t v, const Graph1&) const { |
93 | vertices.push_back(v); |
94 | } |
95 | void examine_edge(edge1_t e, const Graph1&) const { |
96 | edges.push_back(e); |
97 | } |
98 | std::vector<vertex1_t>& vertices; |
99 | std::vector<edge1_t>& edges; |
100 | }; |
101 | |
102 | struct edge_cmp { |
103 | edge_cmp(const Graph1& G1, DFSNumMap dfs_num) |
104 | : G1(G1), dfs_num(dfs_num) { } |
105 | bool operator()(const edge1_t& e1, const edge1_t& e2) const { |
106 | using namespace std; |
107 | int u1 = dfs_num[source(e1,G1)], v1 = dfs_num[target(e1,G1)]; |
108 | int u2 = dfs_num[source(e2,G1)], v2 = dfs_num[target(e2,G1)]; |
109 | int m1 = (max)(a: u1, b: v1); |
110 | int m2 = (max)(a: u2, b: v2); |
111 | // lexicographical comparison |
112 | return std::make_pair(x&: m1, y: std::make_pair(x&: u1, y&: v1)) |
113 | < std::make_pair(x&: m2, y: std::make_pair(x&: u2, y&: v2)); |
114 | } |
115 | const Graph1& G1; |
116 | DFSNumMap dfs_num; |
117 | }; |
118 | |
119 | public: |
120 | isomorphism_algo(const Graph1& G1, const Graph2& G2, IsoMapping f, |
121 | Invariant1 invariant1, Invariant2 invariant2, std::size_t max_invariant, |
122 | IndexMap1 index_map1, IndexMap2 index_map2) |
123 | : G1(G1), G2(G2), f(f), invariant1(invariant1), invariant2(invariant2), |
124 | max_invariant(max_invariant), |
125 | index_map1(index_map1), index_map2(index_map2) |
126 | { |
127 | in_S_vec.resize(num_vertices(G1)); |
128 | in_S = make_safe_iterator_property_map |
129 | (in_S_vec.begin(), in_S_vec.size(), index_map2 |
130 | #ifdef BOOST_NO_STD_ITERATOR_TRAITS |
131 | , in_S_vec.front() |
132 | #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ |
133 | ); |
134 | } |
135 | |
136 | bool test_isomorphism() |
137 | { |
138 | // reset isomapping |
139 | BGL_FORALL_VERTICES_T(v, G1, Graph1) |
140 | f[v] = graph_traits<Graph2>::null_vertex(); |
141 | |
142 | { |
143 | std::vector<invar1_value> invar1_array; |
144 | BGL_FORALL_VERTICES_T(v, G1, Graph1) |
145 | invar1_array.push_back(invariant1(v)); |
146 | sort(invar1_array); |
147 | |
148 | std::vector<invar2_value> invar2_array; |
149 | BGL_FORALL_VERTICES_T(v, G2, Graph2) |
150 | invar2_array.push_back(invariant2(v)); |
151 | sort(invar2_array); |
152 | if (! equal(invar1_array, invar2_array)) |
153 | return false; |
154 | } |
155 | |
156 | std::vector<vertex1_t> V_mult; |
157 | BGL_FORALL_VERTICES_T(v, G1, Graph1) |
158 | V_mult.push_back(v); |
159 | { |
160 | std::vector<size_type> multiplicity(max_invariant, 0); |
161 | BGL_FORALL_VERTICES_T(v, G1, Graph1) |
162 | ++multiplicity.at(invariant1(v)); |
163 | sort(V_mult, compare_multiplicity(invariant1, &multiplicity[0])); |
164 | } |
165 | |
166 | std::vector<default_color_type> color_vec(num_vertices(G1)); |
167 | safe_iterator_property_map<std::vector<default_color_type>::iterator, |
168 | IndexMap1 |
169 | #ifdef BOOST_NO_STD_ITERATOR_TRAITS |
170 | , default_color_type, default_color_type& |
171 | #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ |
172 | > |
173 | color_map(color_vec.begin(), color_vec.size(), index_map1); |
174 | record_dfs_order dfs_visitor(dfs_vertices, ordered_edges); |
175 | typedef color_traits<default_color_type> Color; |
176 | for (vertex_iter u = V_mult.begin(); u != V_mult.end(); ++u) { |
177 | if (color_map[*u] == Color::white()) { |
178 | dfs_visitor.start_vertex(*u, G1); |
179 | depth_first_visit(G1, *u, dfs_visitor, color_map); |
180 | } |
181 | } |
182 | // Create the dfs_num array and dfs_num_map |
183 | dfs_num_vec.resize(num_vertices(G1)); |
184 | dfs_num = make_safe_iterator_property_map(dfs_num_vec.begin(), |
185 | dfs_num_vec.size(), |
186 | index_map1 |
187 | #ifdef BOOST_NO_STD_ITERATOR_TRAITS |
188 | , dfs_num_vec.front() |
189 | #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ |
190 | ); |
191 | size_type n = 0; |
192 | for (vertex_iter v = dfs_vertices.begin(); v != dfs_vertices.end(); ++v) |
193 | dfs_num[*v] = n++; |
194 | |
195 | sort(ordered_edges, edge_cmp(G1, dfs_num)); |
196 | |
197 | |
198 | int dfs_num_k = -1; |
199 | return this->match(ordered_edges.begin(), dfs_num_k); |
200 | } |
201 | |
202 | private: |
203 | struct match_continuation { |
204 | enum {pos_G2_vertex_loop, pos_fi_adj_loop, pos_dfs_num} position; |
205 | typedef typename graph_traits<Graph2>::vertex_iterator vertex_iterator; |
206 | std::pair<vertex_iterator, vertex_iterator> G2_verts; |
207 | typedef typename graph_traits<Graph2>::adjacency_iterator adjacency_iterator; |
208 | std::pair<adjacency_iterator, adjacency_iterator> fi_adj; |
209 | edge_iter iter; |
210 | int dfs_num_k; |
211 | }; |
212 | |
213 | bool match(edge_iter iter, int dfs_num_k) |
214 | { |
215 | std::vector<match_continuation> k; |
216 | typedef typename graph_traits<Graph2>::vertex_iterator vertex_iterator; |
217 | std::pair<vertex_iterator, vertex_iterator> G2_verts(vertices(G2)); |
218 | typedef typename graph_traits<Graph2>::adjacency_iterator adjacency_iterator; |
219 | std::pair<adjacency_iterator, adjacency_iterator> fi_adj; |
220 | vertex1_t i, j; |
221 | |
222 | recur: |
223 | if (iter != ordered_edges.end()) { |
224 | i = source(*iter, G1); |
225 | j = target(*iter, G1); |
226 | if (dfs_num[i] > dfs_num_k) { |
227 | G2_verts = vertices(G2); |
228 | while (G2_verts.first != G2_verts.second) { |
229 | { |
230 | vertex2_t u = *G2_verts.first; |
231 | vertex1_t kp1 = dfs_vertices[dfs_num_k + 1]; |
232 | if (invariant1(kp1) == invariant2(u) && in_S[u] == false) { |
233 | { |
234 | f[kp1] = u; |
235 | in_S[u] = true; |
236 | num_edges_on_k = 0; |
237 | |
238 | match_continuation new_k; |
239 | new_k.position = match_continuation::pos_G2_vertex_loop; |
240 | new_k.G2_verts = G2_verts; |
241 | new_k.iter = iter; |
242 | new_k.dfs_num_k = dfs_num_k; |
243 | k.push_back(new_k); |
244 | ++dfs_num_k; |
245 | goto recur; |
246 | } |
247 | } |
248 | } |
249 | G2_loop_k: ++G2_verts.first; |
250 | } |
251 | |
252 | } |
253 | else if (dfs_num[j] > dfs_num_k) { |
254 | { |
255 | vertex1_t vk = dfs_vertices[dfs_num_k]; |
256 | num_edges_on_k -= |
257 | count_if(adjacent_vertices(f[vk], G2), make_indirect_pmap(in_S)); |
258 | |
259 | for (int jj = 0; jj < dfs_num_k; ++jj) { |
260 | vertex1_t j = dfs_vertices[jj]; |
261 | num_edges_on_k -= count(adjacent_vertices(f[j], G2), f[vk]); |
262 | } |
263 | } |
264 | |
265 | if (num_edges_on_k != 0) |
266 | goto return_point_false; |
267 | fi_adj = adjacent_vertices(f[i], G2); |
268 | while (fi_adj.first != fi_adj.second) { |
269 | { |
270 | vertex2_t v = *fi_adj.first; |
271 | if (invariant2(v) == invariant1(j) && in_S[v] == false) { |
272 | f[j] = v; |
273 | in_S[v] = true; |
274 | num_edges_on_k = 1; |
275 | BOOST_USING_STD_MAX(); |
276 | int next_k = max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num_k, max BOOST_PREVENT_MACRO_SUBSTITUTION(dfs_num[i], dfs_num[j])); |
277 | match_continuation new_k; |
278 | new_k.position = match_continuation::pos_fi_adj_loop; |
279 | new_k.fi_adj = fi_adj; |
280 | new_k.iter = iter; |
281 | new_k.dfs_num_k = dfs_num_k; |
282 | ++iter; |
283 | dfs_num_k = next_k; |
284 | k.push_back(new_k); |
285 | goto recur; |
286 | } |
287 | } |
288 | fi_adj_loop_k:++fi_adj.first; |
289 | } |
290 | } |
291 | else { |
292 | if (container_contains(adjacent_vertices(f[i], G2), f[j])) { |
293 | ++num_edges_on_k; |
294 | match_continuation new_k; |
295 | new_k.position = match_continuation::pos_dfs_num; |
296 | k.push_back(new_k); |
297 | ++iter; |
298 | goto recur; |
299 | } |
300 | |
301 | } |
302 | } else |
303 | goto return_point_true; |
304 | goto return_point_false; |
305 | |
306 | { |
307 | return_point_true: return true; |
308 | |
309 | return_point_false: |
310 | if (k.empty()) return false; |
311 | const match_continuation& this_k = k.back(); |
312 | switch (this_k.position) { |
313 | 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, G1); goto G2_loop_k;} |
314 | 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, G1); goto fi_adj_loop_k;} |
315 | case match_continuation::pos_dfs_num: {k.pop_back(); goto return_point_false;} |
316 | default: { |
317 | BOOST_ASSERT(!"Bad position" ); |
318 | #ifdef UNDER_CE |
319 | exit(-1); |
320 | #else |
321 | abort(); |
322 | #endif |
323 | } |
324 | } |
325 | } |
326 | } |
327 | }; |
328 | |
329 | |
330 | template <typename Graph, typename InDegreeMap> |
331 | void compute_in_degree(const Graph& g, InDegreeMap in_degree_map) |
332 | { |
333 | BGL_FORALL_VERTICES_T(v, g, Graph) |
334 | put(in_degree_map, v, 0); |
335 | |
336 | BGL_FORALL_VERTICES_T(u, g, Graph) |
337 | BGL_FORALL_ADJ_T(u, v, g, Graph) |
338 | put(in_degree_map, v, get(in_degree_map, v) + 1); |
339 | } |
340 | |
341 | } // namespace detail |
342 | |
343 | |
344 | template <typename InDegreeMap, typename Graph> |
345 | class degree_vertex_invariant |
346 | { |
347 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
348 | typedef typename graph_traits<Graph>::degree_size_type size_type; |
349 | public: |
350 | typedef vertex_t argument_type; |
351 | typedef size_type result_type; |
352 | |
353 | degree_vertex_invariant(const InDegreeMap& in_degree_map, const Graph& g) |
354 | : m_in_degree_map(in_degree_map), |
355 | m_max_vertex_in_degree(0), |
356 | m_max_vertex_out_degree(0), |
357 | m_g(g) { |
358 | BGL_FORALL_VERTICES_T(v, g, Graph) { |
359 | m_max_vertex_in_degree = |
360 | (std::max)(m_max_vertex_in_degree, get(m_in_degree_map, v)); |
361 | m_max_vertex_out_degree = |
362 | (std::max)(m_max_vertex_out_degree, out_degree(v, g)); |
363 | } |
364 | } |
365 | |
366 | size_type operator()(vertex_t v) const { |
367 | return (m_max_vertex_in_degree + 1) * out_degree(v, m_g) |
368 | + get(m_in_degree_map, v); |
369 | } |
370 | // The largest possible vertex invariant number |
371 | size_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { |
372 | return (m_max_vertex_in_degree + 1) * (m_max_vertex_out_degree + 1); |
373 | } |
374 | private: |
375 | InDegreeMap m_in_degree_map; |
376 | size_type m_max_vertex_in_degree; |
377 | size_type m_max_vertex_out_degree; |
378 | const Graph& m_g; |
379 | }; |
380 | |
381 | // Count actual number of vertices, even in filtered graphs. |
382 | template <typename Graph> |
383 | size_t count_vertices(const Graph& g) |
384 | { |
385 | size_t n = 0; |
386 | BGL_FORALL_VERTICES_T(v, g, Graph) {(void)v; ++n;} |
387 | return n; |
388 | } |
389 | |
390 | template <typename Graph1, typename Graph2, typename IsoMapping, |
391 | typename Invariant1, typename Invariant2, |
392 | typename IndexMap1, typename IndexMap2> |
393 | bool isomorphism(const Graph1& G1, const Graph2& G2, IsoMapping f, |
394 | Invariant1 invariant1, Invariant2 invariant2, |
395 | std::size_t max_invariant, |
396 | IndexMap1 index_map1, IndexMap2 index_map2) |
397 | |
398 | { |
399 | // Graph requirements |
400 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph1> )); |
401 | BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> )); |
402 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph2> )); |
403 | //BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph2> )); |
404 | |
405 | typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_t; |
406 | typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t; |
407 | typedef typename graph_traits<Graph1>::vertices_size_type size_type; |
408 | |
409 | // Vertex invariant requirement |
410 | BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Invariant1, |
411 | size_type, vertex1_t> )); |
412 | BOOST_CONCEPT_ASSERT(( AdaptableUnaryFunctionConcept<Invariant2, |
413 | size_type, vertex2_t> )); |
414 | |
415 | // Property map requirements |
416 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<IsoMapping, vertex1_t> )); |
417 | typedef typename property_traits<IsoMapping>::value_type IsoMappingValue; |
418 | BOOST_STATIC_ASSERT((is_convertible<IsoMappingValue, vertex2_t>::value)); |
419 | |
420 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap1, vertex1_t> )); |
421 | typedef typename property_traits<IndexMap1>::value_type IndexMap1Value; |
422 | BOOST_STATIC_ASSERT((is_convertible<IndexMap1Value, size_type>::value)); |
423 | |
424 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap2, vertex2_t> )); |
425 | typedef typename property_traits<IndexMap2>::value_type IndexMap2Value; |
426 | BOOST_STATIC_ASSERT((is_convertible<IndexMap2Value, size_type>::value)); |
427 | |
428 | if (count_vertices(G1) != count_vertices(G2)) |
429 | return false; |
430 | if (count_vertices(G1) == 0 && count_vertices(G2) == 0) |
431 | return true; |
432 | |
433 | detail::isomorphism_algo<Graph1, Graph2, IsoMapping, Invariant1, |
434 | Invariant2, IndexMap1, IndexMap2> |
435 | algo(G1, G2, f, invariant1, invariant2, max_invariant, |
436 | index_map1, index_map2); |
437 | return algo.test_isomorphism(); |
438 | } |
439 | |
440 | |
441 | namespace detail { |
442 | |
443 | template <typename Graph1, typename Graph2, |
444 | typename IsoMapping, |
445 | typename IndexMap1, typename IndexMap2, |
446 | typename P, typename T, typename R> |
447 | bool isomorphism_impl(const Graph1& G1, const Graph2& G2, |
448 | IsoMapping f, IndexMap1 index_map1, IndexMap2 index_map2, |
449 | const bgl_named_params<P,T,R>& params) |
450 | { |
451 | std::vector<std::size_t> in_degree1_vec(num_vertices(G1)); |
452 | typedef safe_iterator_property_map<std::vector<std::size_t>::iterator, |
453 | IndexMap1 |
454 | #ifdef BOOST_NO_STD_ITERATOR_TRAITS |
455 | , std::size_t, std::size_t& |
456 | #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ |
457 | > InDeg1; |
458 | InDeg1 in_degree1(in_degree1_vec.begin(), in_degree1_vec.size(), index_map1); |
459 | compute_in_degree(G1, in_degree1); |
460 | |
461 | std::vector<std::size_t> in_degree2_vec(num_vertices(G2)); |
462 | typedef safe_iterator_property_map<std::vector<std::size_t>::iterator, |
463 | IndexMap2 |
464 | #ifdef BOOST_NO_STD_ITERATOR_TRAITS |
465 | , std::size_t, std::size_t& |
466 | #endif /* BOOST_NO_STD_ITERATOR_TRAITS */ |
467 | > InDeg2; |
468 | InDeg2 in_degree2(in_degree2_vec.begin(), in_degree2_vec.size(), index_map2); |
469 | compute_in_degree(G2, in_degree2); |
470 | |
471 | degree_vertex_invariant<InDeg1, Graph1> invariant1(in_degree1, G1); |
472 | degree_vertex_invariant<InDeg2, Graph2> invariant2(in_degree2, G2); |
473 | |
474 | return isomorphism(G1, G2, f, |
475 | choose_param(get_param(params, vertex_invariant1_t()), invariant1), |
476 | choose_param(get_param(params, vertex_invariant2_t()), invariant2), |
477 | choose_param(get_param(params, vertex_max_invariant_t()), (invariant2.max)()), |
478 | index_map1, index_map2 |
479 | ); |
480 | } |
481 | |
482 | template <typename G, typename Index> |
483 | struct make_degree_invariant { |
484 | const G& g; |
485 | const Index& index; |
486 | make_degree_invariant(const G& g, const Index& index): g(g), index(index) {} |
487 | typedef typename boost::graph_traits<G>::degree_size_type degree_size_type; |
488 | typedef shared_array_property_map<degree_size_type, Index> prop_map_type; |
489 | typedef degree_vertex_invariant<prop_map_type, G> result_type; |
490 | result_type operator()() const { |
491 | prop_map_type pm = make_shared_array_property_map(num_vertices(g), degree_size_type(), index); |
492 | compute_in_degree(g, pm); |
493 | return result_type(pm, g); |
494 | } |
495 | }; |
496 | |
497 | } // namespace detail |
498 | |
499 | namespace graph { |
500 | namespace detail { |
501 | template <typename Graph1, typename Graph2> |
502 | struct isomorphism_impl { |
503 | typedef bool result_type; |
504 | template <typename ArgPack> |
505 | bool operator()(const Graph1& g1, const Graph2& g2, const ArgPack& arg_pack) const { |
506 | using namespace boost::graph::keywords; |
507 | typedef typename boost::detail::override_const_property_result<ArgPack, tag::vertex_index1_map, boost::vertex_index_t, Graph1>::type index1_map_type; |
508 | typedef typename boost::detail::override_const_property_result<ArgPack, tag::vertex_index2_map, boost::vertex_index_t, Graph2>::type index2_map_type; |
509 | index1_map_type index1_map = boost::detail::override_const_property(arg_pack, _vertex_index1_map, g1, boost::vertex_index); |
510 | index2_map_type index2_map = boost::detail::override_const_property(arg_pack, _vertex_index2_map, g2, boost::vertex_index); |
511 | typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_t; |
512 | typename std::vector<vertex2_t>::size_type n = (typename std::vector<vertex2_t>::size_type)num_vertices(g1); |
513 | std::vector<vertex2_t> f(n); |
514 | typename boost::parameter::lazy_binding< |
515 | ArgPack, |
516 | tag::vertex_invariant1, |
517 | boost::detail::make_degree_invariant<Graph1, index1_map_type> >::type |
518 | invariant1 = |
519 | arg_pack[_vertex_invariant1 || boost::detail::make_degree_invariant<Graph1, index1_map_type>(g1, index1_map)]; |
520 | typename boost::parameter::lazy_binding< |
521 | ArgPack, |
522 | tag::vertex_invariant2, |
523 | boost::detail::make_degree_invariant<Graph2, index2_map_type> >::type |
524 | invariant2 = |
525 | arg_pack[_vertex_invariant2 || boost::detail::make_degree_invariant<Graph2, index2_map_type>(g2, index2_map)]; |
526 | return boost::isomorphism |
527 | (g1, g2, |
528 | choose_param(arg_pack[_isomorphism_map | boost::param_not_found()], |
529 | make_shared_array_property_map(num_vertices(g1), vertex2_t(), index1_map)), |
530 | invariant1, |
531 | invariant2, |
532 | arg_pack[_vertex_max_invariant | (invariant2.max)()], |
533 | index1_map, |
534 | index2_map); |
535 | } |
536 | }; |
537 | } |
538 | BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(isomorphism, 2, 6) |
539 | } |
540 | |
541 | // Named parameter interface |
542 | BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(isomorphism, 2) |
543 | |
544 | // Verify that the given mapping iso_map from the vertices of g1 to the |
545 | // vertices of g2 describes an isomorphism. |
546 | // Note: this could be made much faster by specializing based on the graph |
547 | // concepts modeled, but since we're verifying an O(n^(lg n)) algorithm, |
548 | // O(n^4) won't hurt us. |
549 | template<typename Graph1, typename Graph2, typename IsoMap> |
550 | inline bool verify_isomorphism(const Graph1& g1, const Graph2& g2, IsoMap iso_map) |
551 | { |
552 | #if 0 |
553 | // problematic for filtered_graph! |
554 | if (num_vertices(g1) != num_vertices(g2) || num_edges(g1) != num_edges(g2)) |
555 | return false; |
556 | #endif |
557 | |
558 | BGL_FORALL_EDGES_T(e1, g1, Graph1) { |
559 | bool found_edge = false; |
560 | BGL_FORALL_EDGES_T(e2, g2, Graph2) { |
561 | if (source(e2, g2) == get(iso_map, source(e1, g1)) && |
562 | target(e2, g2) == get(iso_map, target(e1, g1))) { |
563 | found_edge = true; |
564 | } |
565 | } |
566 | |
567 | if (!found_edge) |
568 | return false; |
569 | } |
570 | |
571 | return true; |
572 | } |
573 | |
574 | } // namespace boost |
575 | |
576 | #ifdef BOOST_ISO_INCLUDED_ITER_MACROS |
577 | #undef BOOST_ISO_INCLUDED_ITER_MACROS |
578 | #include <boost/graph/iteration_macros_undef.hpp> |
579 | #endif |
580 | |
581 | #endif // BOOST_GRAPH_ISOMORPHISM_HPP |
582 | |