1 | //======================================================================= |
2 | // Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi@gmail.com) |
3 | // Copyright (C) 2013 Jakob Lykke Andersen, University of Southern Denmark (jlandersen@imada.sdu.dk) |
4 | // |
5 | // The algorithm implemented here is derived from original ideas by |
6 | // Pasquale Foggia and colaborators. For further information see |
7 | // e.g. Cordella et al. 2001, 2004. |
8 | // |
9 | // Distributed under the Boost Software License, Version 1.0. (See |
10 | // accompanying file LICENSE_1_0.txt or copy at |
11 | // http://www.boost.org/LICENSE_1_0.txt) |
12 | //======================================================================= |
13 | |
14 | // Revision History: |
15 | // 8 April 2013: Fixed a typo in vf2_print_callback. (Flavio De Lorenzi) |
16 | |
17 | #ifndef BOOST_VF2_SUB_GRAPH_ISO_HPP |
18 | #define BOOST_VF2_SUB_GRAPH_ISO_HPP |
19 | |
20 | #include <iostream> |
21 | #include <iomanip> |
22 | #include <iterator> |
23 | #include <vector> |
24 | #include <utility> |
25 | |
26 | #include <boost/assert.hpp> |
27 | #include <boost/concept/assert.hpp> |
28 | #include <boost/concept_check.hpp> |
29 | #include <boost/graph/graph_utility.hpp> |
30 | #include <boost/graph/graph_traits.hpp> |
31 | #include <boost/graph/mcgregor_common_subgraphs.hpp> // for always_equivalent |
32 | #include <boost/graph/named_function_params.hpp> |
33 | #include <boost/type_traits/has_less.hpp> |
34 | #include <boost/mpl/int.hpp> |
35 | #include <boost/range/algorithm/sort.hpp> |
36 | #include <boost/tuple/tuple.hpp> |
37 | #include <boost/utility/enable_if.hpp> |
38 | |
39 | #ifndef BOOST_GRAPH_ITERATION_MACROS_HPP |
40 | #define BOOST_ISO_INCLUDED_ITER_MACROS // local macro, see bottom of file |
41 | #include <boost/graph/iteration_macros.hpp> |
42 | #endif |
43 | |
44 | namespace boost { |
45 | |
46 | // Default print_callback |
47 | template <typename Graph1, |
48 | typename Graph2> |
49 | struct vf2_print_callback { |
50 | |
51 | vf2_print_callback(const Graph1& graph1, const Graph2& graph2) |
52 | : graph1_(graph1), graph2_(graph2) {} |
53 | |
54 | template <typename CorrespondenceMap1To2, |
55 | typename CorrespondenceMap2To1> |
56 | bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const { |
57 | |
58 | // Print (sub)graph isomorphism map |
59 | BGL_FORALL_VERTICES_T(v, graph1_, Graph1) |
60 | std::cout << '(' << get(vertex_index_t(), graph1_, v) << ", " |
61 | << get(vertex_index_t(), graph2_, get(f, v)) << ") " ; |
62 | |
63 | std::cout << std::endl; |
64 | |
65 | return true; |
66 | } |
67 | |
68 | private: |
69 | const Graph1& graph1_; |
70 | const Graph2& graph2_; |
71 | }; |
72 | |
73 | namespace detail { |
74 | |
75 | // State associated with a single graph (graph_this) |
76 | template<typename GraphThis, |
77 | typename GraphOther, |
78 | typename IndexMapThis, |
79 | typename IndexMapOther> |
80 | class base_state { |
81 | |
82 | typedef typename graph_traits<GraphThis>::vertex_descriptor vertex_this_type; |
83 | typedef typename graph_traits<GraphOther>::vertex_descriptor vertex_other_type; |
84 | |
85 | typedef typename graph_traits<GraphThis>::vertices_size_type size_type; |
86 | |
87 | const GraphThis& graph_this_; |
88 | const GraphOther& graph_other_; |
89 | |
90 | IndexMapThis index_map_this_; |
91 | IndexMapOther index_map_other_; |
92 | |
93 | std::vector<vertex_other_type> core_vec_; |
94 | typedef iterator_property_map<typename std::vector<vertex_other_type>::iterator, |
95 | IndexMapThis, vertex_other_type, |
96 | vertex_other_type&> core_map_type; |
97 | core_map_type core_; |
98 | |
99 | std::vector<size_type> in_vec_, out_vec_; |
100 | typedef iterator_property_map<typename std::vector<size_type>::iterator, |
101 | IndexMapThis, size_type, size_type&> in_out_map_type; |
102 | in_out_map_type in_, out_; |
103 | |
104 | size_type term_in_count_, term_out_count_, term_both_count_, core_count_; |
105 | |
106 | // Forbidden |
107 | base_state(const base_state&); |
108 | base_state& operator=(const base_state&); |
109 | |
110 | public: |
111 | |
112 | base_state(const GraphThis& graph_this, const GraphOther& graph_other, |
113 | IndexMapThis index_map_this, IndexMapOther index_map_other) |
114 | : graph_this_(graph_this), graph_other_(graph_other), |
115 | index_map_this_(index_map_this), index_map_other_(index_map_other), |
116 | term_in_count_(0), term_out_count_(0), term_both_count_(0), core_count_(0) { |
117 | |
118 | core_vec_.resize(num_vertices(graph_this_), graph_traits<GraphOther>::null_vertex()); |
119 | core_ = make_iterator_property_map(core_vec_.begin(), index_map_this_); |
120 | |
121 | in_vec_.resize(num_vertices(graph_this_), 0); |
122 | in_ = make_iterator_property_map(in_vec_.begin(), index_map_this_); |
123 | |
124 | out_vec_.resize(num_vertices(graph_this_), 0); |
125 | out_ = make_iterator_property_map(out_vec_.begin(), index_map_this_); |
126 | } |
127 | |
128 | // Adds a vertex pair to the state of graph graph_this |
129 | void push(const vertex_this_type& v_this, const vertex_other_type& v_other) { |
130 | |
131 | ++core_count_; |
132 | |
133 | put(core_, v_this, v_other); |
134 | |
135 | if (!get(in_, v_this)) { |
136 | put(in_, v_this, core_count_); |
137 | ++term_in_count_; |
138 | if (get(out_, v_this)) |
139 | ++term_both_count_; |
140 | } |
141 | |
142 | if (!get(out_, v_this)) { |
143 | put(out_, v_this, core_count_); |
144 | ++term_out_count_; |
145 | if (get(in_, v_this)) |
146 | ++term_both_count_; |
147 | } |
148 | |
149 | BGL_FORALL_INEDGES_T(v_this, e, graph_this_, GraphThis) { |
150 | vertex_this_type w = source(e, graph_this_); |
151 | if (!get(in_, w)) { |
152 | put(in_, w, core_count_); |
153 | ++term_in_count_; |
154 | if (get(out_, w)) |
155 | ++term_both_count_; |
156 | } |
157 | } |
158 | |
159 | BGL_FORALL_OUTEDGES_T(v_this, e, graph_this_, GraphThis) { |
160 | vertex_this_type w = target(e, graph_this_); |
161 | if (!get(out_, w)) { |
162 | put(out_, w, core_count_); |
163 | ++term_out_count_; |
164 | if (get(in_, w)) |
165 | ++term_both_count_; |
166 | } |
167 | } |
168 | |
169 | } |
170 | |
171 | // Removes vertex pair from state of graph_this |
172 | void pop(const vertex_this_type& v_this, const vertex_other_type&) { |
173 | |
174 | if (!core_count_) return; |
175 | |
176 | if (get(in_, v_this) == core_count_) { |
177 | put(in_, v_this, 0); |
178 | --term_in_count_; |
179 | if (get(out_, v_this)) |
180 | --term_both_count_; |
181 | } |
182 | |
183 | BGL_FORALL_INEDGES_T(v_this, e, graph_this_, GraphThis) { |
184 | vertex_this_type w = source(e, graph_this_); |
185 | if (get(in_, w) == core_count_) { |
186 | put(in_, w, 0); |
187 | --term_in_count_; |
188 | if (get(out_, w)) |
189 | --term_both_count_; |
190 | } |
191 | } |
192 | |
193 | if (get(out_, v_this) == core_count_) { |
194 | put(out_, v_this, 0); |
195 | --term_out_count_; |
196 | if (get(in_, v_this)) |
197 | --term_both_count_; |
198 | } |
199 | |
200 | BGL_FORALL_OUTEDGES_T(v_this, e, graph_this_, GraphThis) { |
201 | vertex_this_type w = target(e, graph_this_); |
202 | if (get(out_, w) == core_count_) { |
203 | put(out_, w, 0); |
204 | --term_out_count_; |
205 | if (get(in_, w)) |
206 | --term_both_count_; |
207 | } |
208 | } |
209 | put(core_, v_this, graph_traits<GraphOther>::null_vertex()); |
210 | |
211 | --core_count_; |
212 | |
213 | } |
214 | |
215 | // Returns true if the in-terminal set is not empty |
216 | bool term_in() const { |
217 | return core_count_ < term_in_count_ ; |
218 | } |
219 | |
220 | // Returns true if vertex belongs to the in-terminal set |
221 | bool term_in(const vertex_this_type& v) const { |
222 | return (get(in_, v) > 0) && |
223 | (get(core_, v) == graph_traits<GraphOther>::null_vertex()); |
224 | } |
225 | |
226 | // Returns true if the out-terminal set is not empty |
227 | bool term_out() const { |
228 | return core_count_ < term_out_count_; |
229 | } |
230 | |
231 | // Returns true if vertex belongs to the out-terminal set |
232 | bool term_out(const vertex_this_type& v) const { |
233 | return (get(out_, v) > 0) && |
234 | (get(core_, v) == graph_traits<GraphOther>::null_vertex()); |
235 | } |
236 | |
237 | // Returns true of both (in- and out-terminal) sets are not empty |
238 | bool term_both() const { |
239 | return core_count_ < term_both_count_; |
240 | } |
241 | |
242 | // Returns true if vertex belongs to both (in- and out-terminal) sets |
243 | bool term_both(const vertex_this_type& v) const { |
244 | return (get(in_, v) > 0) && (get(out_, v) > 0) && |
245 | (get(core_, v) == graph_traits<GraphOther>::null_vertex()); |
246 | } |
247 | |
248 | // Returns true if vertex belongs to the core map, i.e. it is in the |
249 | // present mapping |
250 | bool in_core(const vertex_this_type& v) const { |
251 | return get(core_, v) != graph_traits<GraphOther>::null_vertex(); |
252 | } |
253 | |
254 | // Returns the number of vertices in the mapping |
255 | size_type count() const { |
256 | return core_count_; |
257 | } |
258 | |
259 | // Returns the image (in graph_other) of vertex v (in graph_this) |
260 | vertex_other_type core(const vertex_this_type& v) const { |
261 | return get(core_, v); |
262 | } |
263 | |
264 | // Returns the mapping |
265 | core_map_type get_map() const { |
266 | return core_; |
267 | } |
268 | |
269 | // Returns the "time" (or depth) when vertex was added to the in-terminal set |
270 | size_type in_depth(const vertex_this_type& v) const { |
271 | return get(in_, v); |
272 | } |
273 | |
274 | // Returns the "time" (or depth) when vertex was added to the out-terminal set |
275 | size_type out_depth(const vertex_this_type& v) const { |
276 | return get(out_, v); |
277 | } |
278 | |
279 | // Returns the terminal set counts |
280 | boost::tuple<size_type, size_type, size_type> |
281 | term_set() const { |
282 | return boost::make_tuple(term_in_count_, term_out_count_, |
283 | term_both_count_); |
284 | } |
285 | |
286 | }; |
287 | |
288 | |
289 | // Function object that checks whether a valid edge |
290 | // exists. For multi-graphs matched edges are excluded |
291 | template <typename Graph, typename Enable = void> |
292 | struct equivalent_edge_exists { |
293 | typedef typename boost::graph_traits<Graph>::edge_descriptor edge_type; |
294 | |
295 | BOOST_CONCEPT_ASSERT(( LessThanComparable<edge_type> )); |
296 | |
297 | template<typename EdgePredicate> |
298 | bool operator()(typename graph_traits<Graph>::vertex_descriptor s, |
299 | typename graph_traits<Graph>::vertex_descriptor t, |
300 | EdgePredicate is_valid_edge, const Graph& g) { |
301 | |
302 | BGL_FORALL_OUTEDGES_T(s, e, g, Graph) { |
303 | if ((target(e, g) == t) && is_valid_edge(e) && |
304 | (matched_edges_.find(e) == matched_edges_.end())) { |
305 | matched_edges_.insert(e); |
306 | return true; |
307 | } |
308 | } |
309 | |
310 | return false; |
311 | } |
312 | |
313 | private: |
314 | |
315 | std::set<edge_type> matched_edges_; |
316 | }; |
317 | |
318 | template <typename Graph> |
319 | struct equivalent_edge_exists<Graph, typename boost::disable_if<is_multigraph<Graph> >::type> { |
320 | template<typename EdgePredicate> |
321 | bool operator()(typename graph_traits<Graph>::vertex_descriptor s, |
322 | typename graph_traits<Graph>::vertex_descriptor t, |
323 | EdgePredicate is_valid_edge, const Graph& g) { |
324 | |
325 | typename graph_traits<Graph>::edge_descriptor e; |
326 | bool found; |
327 | boost::tie(e, found) = edge(s, t, g); |
328 | if (!found) |
329 | return false; |
330 | else if (is_valid_edge(e)) |
331 | return true; |
332 | |
333 | return false; |
334 | } |
335 | |
336 | }; |
337 | |
338 | |
339 | // Generates a predicate for edge e1 given a binary predicate and a |
340 | // fixed edge e2 |
341 | template <typename Graph1, |
342 | typename Graph2, |
343 | typename EdgeEquivalencePredicate> |
344 | struct edge1_predicate { |
345 | |
346 | edge1_predicate(EdgeEquivalencePredicate edge_comp, |
347 | typename graph_traits<Graph2>::edge_descriptor e2) |
348 | : edge_comp_(edge_comp), e2_(e2) {} |
349 | |
350 | bool operator()(typename graph_traits<Graph1>::edge_descriptor e1) { |
351 | return edge_comp_(e1, e2_); |
352 | } |
353 | |
354 | EdgeEquivalencePredicate edge_comp_; |
355 | typename graph_traits<Graph2>::edge_descriptor e2_; |
356 | }; |
357 | |
358 | |
359 | // Generates a predicate for edge e2 given given a binary predicate and a |
360 | // fixed edge e1 |
361 | template <typename Graph1, |
362 | typename Graph2, |
363 | typename EdgeEquivalencePredicate> |
364 | struct edge2_predicate { |
365 | |
366 | edge2_predicate(EdgeEquivalencePredicate edge_comp, |
367 | typename graph_traits<Graph1>::edge_descriptor e1) |
368 | : edge_comp_(edge_comp), e1_(e1) {} |
369 | |
370 | bool operator()(typename graph_traits<Graph2>::edge_descriptor e2) { |
371 | return edge_comp_(e1_, e2); |
372 | } |
373 | |
374 | EdgeEquivalencePredicate edge_comp_; |
375 | typename graph_traits<Graph1>::edge_descriptor e1_; |
376 | }; |
377 | |
378 | |
379 | enum problem_selector {subgraph_mono, subgraph_iso, isomorphism }; |
380 | |
381 | // The actual state associated with both graphs |
382 | template<typename Graph1, |
383 | typename Graph2, |
384 | typename IndexMap1, |
385 | typename IndexMap2, |
386 | typename EdgeEquivalencePredicate, |
387 | typename VertexEquivalencePredicate, |
388 | typename SubGraphIsoMapCallback, |
389 | problem_selector problem_selection> |
390 | class state { |
391 | |
392 | typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_type; |
393 | typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_type; |
394 | |
395 | typedef typename graph_traits<Graph1>::edge_descriptor edge1_type; |
396 | typedef typename graph_traits<Graph2>::edge_descriptor edge2_type; |
397 | |
398 | typedef typename graph_traits<Graph1>::vertices_size_type graph1_size_type; |
399 | typedef typename graph_traits<Graph2>::vertices_size_type graph2_size_type; |
400 | |
401 | const Graph1& graph1_; |
402 | const Graph2& graph2_; |
403 | |
404 | IndexMap1 index_map1_; |
405 | |
406 | EdgeEquivalencePredicate edge_comp_; |
407 | VertexEquivalencePredicate vertex_comp_; |
408 | |
409 | base_state<Graph1, Graph2, IndexMap1, IndexMap2> state1_; |
410 | base_state<Graph2, Graph1, IndexMap2, IndexMap1> state2_; |
411 | |
412 | // Three helper functions used in Feasibility and Valid functions to test |
413 | // terminal set counts when testing for: |
414 | // - graph sub-graph monomorphism, or |
415 | inline bool comp_term_sets(graph1_size_type a, |
416 | graph2_size_type b, |
417 | boost::mpl::int_<subgraph_mono>) const { |
418 | return a <= b; |
419 | } |
420 | |
421 | // - graph sub-graph isomorphism, or |
422 | inline bool comp_term_sets(graph1_size_type a, |
423 | graph2_size_type b, |
424 | boost::mpl::int_<subgraph_iso>) const { |
425 | return a <= b; |
426 | } |
427 | |
428 | // - graph isomorphism |
429 | inline bool comp_term_sets(graph1_size_type a, |
430 | graph2_size_type b, |
431 | boost::mpl::int_<isomorphism>) const { |
432 | return a == b; |
433 | } |
434 | |
435 | // Forbidden |
436 | state(const state&); |
437 | state& operator=(const state&); |
438 | |
439 | public: |
440 | |
441 | state(const Graph1& graph1, const Graph2& graph2, |
442 | IndexMap1 index_map1, IndexMap2 index_map2, |
443 | EdgeEquivalencePredicate edge_comp, |
444 | VertexEquivalencePredicate vertex_comp) |
445 | : graph1_(graph1), graph2_(graph2), |
446 | index_map1_(index_map1), |
447 | edge_comp_(edge_comp), vertex_comp_(vertex_comp), |
448 | state1_(graph1, graph2, index_map1, index_map2), |
449 | state2_(graph2, graph1, index_map2, index_map1) {} |
450 | |
451 | // Add vertex pair to the state |
452 | void push(const vertex1_type& v, const vertex2_type& w) { |
453 | state1_.push(v, w); |
454 | state2_.push(w, v); |
455 | } |
456 | |
457 | // Remove vertex pair from state |
458 | void pop(const vertex1_type& v, const vertex2_type&) { |
459 | vertex2_type w = state1_.core(v); |
460 | state1_.pop(v, w); |
461 | state2_.pop(w, v); |
462 | } |
463 | |
464 | // Checks the feasibility of a new vertex pair |
465 | bool feasible(const vertex1_type& v_new, const vertex2_type& w_new) { |
466 | |
467 | if (!vertex_comp_(v_new, w_new)) return false; |
468 | |
469 | // graph1 |
470 | graph1_size_type term_in1_count = 0, term_out1_count = 0, rest1_count = 0; |
471 | |
472 | { |
473 | equivalent_edge_exists<Graph2> edge2_exists; |
474 | |
475 | BGL_FORALL_INEDGES_T(v_new, e1, graph1_, Graph1) { |
476 | vertex1_type v = source(e1, graph1_); |
477 | |
478 | if (state1_.in_core(v) || (v == v_new)) { |
479 | vertex2_type w = w_new; |
480 | if (v != v_new) |
481 | w = state1_.core(v); |
482 | if (!edge2_exists(w, w_new, |
483 | edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e1), |
484 | graph2_)) |
485 | return false; |
486 | |
487 | } else { |
488 | if (0 < state1_.in_depth(v)) |
489 | ++term_in1_count; |
490 | if (0 < state1_.out_depth(v)) |
491 | ++term_out1_count; |
492 | if ((state1_.in_depth(v) == 0) && (state1_.out_depth(v) == 0)) |
493 | ++rest1_count; |
494 | } |
495 | } |
496 | } |
497 | |
498 | { |
499 | equivalent_edge_exists<Graph2> edge2_exists; |
500 | |
501 | BGL_FORALL_OUTEDGES_T(v_new, e1, graph1_, Graph1) { |
502 | vertex1_type v = target(e1, graph1_); |
503 | if (state1_.in_core(v) || (v == v_new)) { |
504 | vertex2_type w = w_new; |
505 | if (v != v_new) |
506 | w = state1_.core(v); |
507 | |
508 | if (!edge2_exists(w_new, w, |
509 | edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e1), |
510 | graph2_)) |
511 | return false; |
512 | |
513 | } else { |
514 | if (0 < state1_.in_depth(v)) |
515 | ++term_in1_count; |
516 | if (0 < state1_.out_depth(v)) |
517 | ++term_out1_count; |
518 | if ((state1_.in_depth(v) == 0) && (state1_.out_depth(v) == 0)) |
519 | ++rest1_count; |
520 | } |
521 | } |
522 | } |
523 | |
524 | // graph2 |
525 | graph2_size_type term_out2_count = 0, term_in2_count = 0, rest2_count = 0; |
526 | |
527 | { |
528 | equivalent_edge_exists<Graph1> edge1_exists; |
529 | |
530 | BGL_FORALL_INEDGES_T(w_new, e2, graph2_, Graph2) { |
531 | vertex2_type w = source(e2, graph2_); |
532 | if (state2_.in_core(w) || (w == w_new)) { |
533 | if (problem_selection != subgraph_mono) { |
534 | vertex1_type v = v_new; |
535 | if (w != w_new) |
536 | v = state2_.core(w); |
537 | |
538 | if (!edge1_exists(v, v_new, |
539 | edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2), |
540 | graph1_)) |
541 | return false; |
542 | } |
543 | } else { |
544 | if (0 < state2_.in_depth(w)) |
545 | ++term_in2_count; |
546 | if (0 < state2_.out_depth(w)) |
547 | ++term_out2_count; |
548 | if ((state2_.in_depth(w) == 0) && (state2_.out_depth(w) == 0)) |
549 | ++rest2_count; |
550 | } |
551 | } |
552 | } |
553 | |
554 | { |
555 | equivalent_edge_exists<Graph1> edge1_exists; |
556 | |
557 | BGL_FORALL_OUTEDGES_T(w_new, e2, graph2_, Graph2) { |
558 | vertex2_type w = target(e2, graph2_); |
559 | if (state2_.in_core(w) || (w == w_new)) { |
560 | if (problem_selection != subgraph_mono) { |
561 | vertex1_type v = v_new; |
562 | if (w != w_new) |
563 | v = state2_.core(w); |
564 | |
565 | if (!edge1_exists(v_new, v, |
566 | edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2), |
567 | graph1_)) |
568 | return false; |
569 | } |
570 | } else { |
571 | if (0 < state2_.in_depth(w)) |
572 | ++term_in2_count; |
573 | if (0 < state2_.out_depth(w)) |
574 | ++term_out2_count; |
575 | if ((state2_.in_depth(w) == 0) && (state2_.out_depth(w) == 0)) |
576 | ++rest2_count; |
577 | } |
578 | } |
579 | } |
580 | |
581 | if (problem_selection != subgraph_mono) { // subgraph_iso and isomorphism |
582 | return comp_term_sets(term_in1_count, term_in2_count, |
583 | boost::mpl::int_<problem_selection>()) && |
584 | comp_term_sets(term_out1_count, term_out2_count, |
585 | boost::mpl::int_<problem_selection>()) && |
586 | comp_term_sets(rest1_count, rest2_count, |
587 | boost::mpl::int_<problem_selection>()); |
588 | } else { // subgraph_mono |
589 | return comp_term_sets(term_in1_count, term_in2_count, |
590 | boost::mpl::int_<problem_selection>()) && |
591 | comp_term_sets(term_out1_count, term_out2_count, |
592 | boost::mpl::int_<problem_selection>()) && |
593 | comp_term_sets(term_in1_count + term_out1_count + rest1_count, |
594 | term_in2_count + term_out2_count + rest2_count, |
595 | boost::mpl::int_<problem_selection>()); |
596 | } |
597 | } |
598 | |
599 | // Returns true if vertex v in graph1 is a possible candidate to |
600 | // be added to the current state |
601 | bool possible_candidate1(const vertex1_type& v) const { |
602 | if (state1_.term_both() && state2_.term_both()) |
603 | return state1_.term_both(v); |
604 | else if (state1_.term_out() && state2_.term_out()) |
605 | return state1_.term_out(v); |
606 | else if (state1_.term_in() && state2_.term_in()) |
607 | return state1_.term_in(v); |
608 | else |
609 | return !state1_.in_core(v); |
610 | } |
611 | |
612 | // Returns true if vertex w in graph2 is a possible candidate to |
613 | // be added to the current state |
614 | bool possible_candidate2(const vertex2_type& w) const { |
615 | if (state1_.term_both() && state2_.term_both()) |
616 | return state2_.term_both(w); |
617 | else if (state1_.term_out() && state2_.term_out()) |
618 | return state2_.term_out(w); |
619 | else if (state1_.term_in() && state2_.term_in()) |
620 | return state2_.term_in(w); |
621 | else |
622 | return !state2_.in_core(w); |
623 | } |
624 | |
625 | // Returns true if a mapping was found |
626 | bool success() const { |
627 | return state1_.count() == num_vertices(graph1_); |
628 | } |
629 | |
630 | // Returns true if a state is valid |
631 | bool valid() const { |
632 | boost::tuple<graph1_size_type, graph1_size_type, graph1_size_type> term1; |
633 | boost::tuple<graph2_size_type, graph2_size_type, graph2_size_type> term2; |
634 | |
635 | term1 = state1_.term_set(); |
636 | term2 = state2_.term_set(); |
637 | |
638 | return comp_term_sets(boost::get<0>(term1), boost::get<0>(term2), |
639 | boost::mpl::int_<problem_selection>()) && |
640 | comp_term_sets(boost::get<1>(term1), boost::get<1>(term2), |
641 | boost::mpl::int_<problem_selection>()) && |
642 | comp_term_sets(boost::get<2>(term1), boost::get<2>(term2), |
643 | boost::mpl::int_<problem_selection>()); |
644 | } |
645 | |
646 | // Calls the user_callback with a graph (sub)graph mapping |
647 | bool call_back(SubGraphIsoMapCallback user_callback) const { |
648 | return user_callback(state1_.get_map(), state2_.get_map()); |
649 | } |
650 | |
651 | }; |
652 | |
653 | |
654 | // Data structure to keep info used for back tracking during |
655 | // matching process |
656 | template<typename Graph1, |
657 | typename Graph2, |
658 | typename VertexOrder1> |
659 | struct vf2_match_continuation { |
660 | typename VertexOrder1::const_iterator graph1_verts_iter; |
661 | typename graph_traits<Graph2>::vertex_iterator graph2_verts_iter; |
662 | }; |
663 | |
664 | // Non-recursive method that explores state space using a depth-first |
665 | // search strategy. At each depth possible pairs candidate are compute |
666 | // and tested for feasibility to extend the mapping. If a complete |
667 | // mapping is found, the mapping is output to user_callback in the form |
668 | // of a correspondence map (graph1 to graph2). Returning false from the |
669 | // user_callback will terminate the search. Function match will return |
670 | // true if the entire search space was explored. |
671 | template<typename Graph1, |
672 | typename Graph2, |
673 | typename IndexMap1, |
674 | typename IndexMap2, |
675 | typename VertexOrder1, |
676 | typename EdgeEquivalencePredicate, |
677 | typename VertexEquivalencePredicate, |
678 | typename SubGraphIsoMapCallback, |
679 | problem_selector problem_selection> |
680 | bool match(const Graph1& graph1, const Graph2& graph2, |
681 | SubGraphIsoMapCallback user_callback, const VertexOrder1& vertex_order1, |
682 | state<Graph1, Graph2, IndexMap1, IndexMap2, |
683 | EdgeEquivalencePredicate, VertexEquivalencePredicate, |
684 | SubGraphIsoMapCallback, problem_selection>& s) { |
685 | |
686 | typename VertexOrder1::const_iterator graph1_verts_iter; |
687 | |
688 | typedef typename graph_traits<Graph2>::vertex_iterator vertex2_iterator_type; |
689 | vertex2_iterator_type graph2_verts_iter, graph2_verts_iter_end; |
690 | |
691 | typedef vf2_match_continuation<Graph1, Graph2, VertexOrder1> match_continuation_type; |
692 | std::vector<match_continuation_type> k; |
693 | bool found_match = false; |
694 | |
695 | recur: |
696 | if (s.success()) { |
697 | if (!s.call_back(user_callback)) |
698 | return true; |
699 | found_match = true; |
700 | |
701 | goto back_track; |
702 | } |
703 | |
704 | if (!s.valid()) |
705 | goto back_track; |
706 | |
707 | graph1_verts_iter = vertex_order1.begin(); |
708 | while (graph1_verts_iter != vertex_order1.end() && |
709 | !s.possible_candidate1(*graph1_verts_iter)) { |
710 | ++graph1_verts_iter; |
711 | } |
712 | |
713 | boost::tie(graph2_verts_iter, graph2_verts_iter_end) = vertices(graph2); |
714 | while (graph2_verts_iter != graph2_verts_iter_end) { |
715 | if (s.possible_candidate2(*graph2_verts_iter)) { |
716 | if (s.feasible(*graph1_verts_iter, *graph2_verts_iter)) { |
717 | match_continuation_type kk; |
718 | kk.graph1_verts_iter = graph1_verts_iter; |
719 | kk.graph2_verts_iter = graph2_verts_iter; |
720 | k.push_back(kk); |
721 | |
722 | s.push(*graph1_verts_iter, *graph2_verts_iter); |
723 | goto recur; |
724 | } |
725 | } |
726 | graph2_loop: ++graph2_verts_iter; |
727 | } |
728 | |
729 | back_track: |
730 | if (k.empty()) |
731 | return found_match; |
732 | |
733 | const match_continuation_type kk = k.back(); |
734 | graph1_verts_iter = kk.graph1_verts_iter; |
735 | graph2_verts_iter = kk.graph2_verts_iter; |
736 | k.pop_back(); |
737 | |
738 | s.pop(*graph1_verts_iter, *graph2_verts_iter); |
739 | |
740 | goto graph2_loop; |
741 | } |
742 | |
743 | |
744 | // Used to sort nodes by in/out degrees |
745 | template<typename Graph> |
746 | struct vertex_in_out_degree_cmp { |
747 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_type; |
748 | |
749 | vertex_in_out_degree_cmp(const Graph& graph) |
750 | : graph_(graph) {} |
751 | |
752 | bool operator()(const vertex_type& v, const vertex_type& w) const { |
753 | // lexicographical comparison |
754 | return std::make_pair(in_degree(v, graph_), out_degree(v, graph_)) < |
755 | std::make_pair(in_degree(w, graph_), out_degree(w, graph_)); |
756 | } |
757 | |
758 | const Graph& graph_; |
759 | }; |
760 | |
761 | |
762 | // Used to sort nodes by multiplicity of in/out degrees |
763 | template<typename Graph, |
764 | typename FrequencyMap> |
765 | struct vertex_frequency_degree_cmp { |
766 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_type; |
767 | |
768 | vertex_frequency_degree_cmp(const Graph& graph, FrequencyMap freq) |
769 | : graph_(graph), freq_(freq) {} |
770 | |
771 | bool operator()(const vertex_type& v, const vertex_type& w) const { |
772 | // lexicographical comparison |
773 | return std::make_pair(freq_[v], in_degree(v, graph_)+out_degree(v, graph_)) < |
774 | std::make_pair(freq_[w], in_degree(w, graph_)+out_degree(w, graph_)); |
775 | } |
776 | |
777 | const Graph& graph_; |
778 | FrequencyMap freq_; |
779 | }; |
780 | |
781 | |
782 | // Sorts vertices of a graph by multiplicity of in/out degrees |
783 | template<typename Graph, |
784 | typename IndexMap, |
785 | typename VertexOrder> |
786 | void sort_vertices(const Graph& graph, IndexMap index_map, VertexOrder& order) { |
787 | typedef typename graph_traits<Graph>::vertices_size_type size_type; |
788 | |
789 | boost::range::sort(order, vertex_in_out_degree_cmp<Graph>(graph)); |
790 | |
791 | std::vector<size_type> freq_vec(num_vertices(graph), 0); |
792 | typedef iterator_property_map<typename std::vector<size_type>::iterator, |
793 | IndexMap, size_type, size_type&> frequency_map_type; |
794 | |
795 | frequency_map_type freq = make_iterator_property_map(freq_vec.begin(), index_map); |
796 | |
797 | typedef typename VertexOrder::iterator order_iterator; |
798 | |
799 | for (order_iterator order_iter = order.begin(); order_iter != order.end(); ) { |
800 | size_type count = 0; |
801 | for (order_iterator count_iter = order_iter; |
802 | (count_iter != order.end()) && |
803 | (in_degree(*order_iter, graph) == in_degree(*count_iter, graph)) && |
804 | (out_degree(*order_iter, graph) == out_degree(*count_iter, graph)); |
805 | ++count_iter) |
806 | ++count; |
807 | |
808 | for (size_type i = 0; i < count; ++i) { |
809 | freq[*order_iter] = count; |
810 | ++order_iter; |
811 | } |
812 | } |
813 | |
814 | boost::range::sort(order, vertex_frequency_degree_cmp<Graph, frequency_map_type>(graph, freq)); |
815 | |
816 | } |
817 | |
818 | // Enumerates all graph sub-graph mono-/iso-morphism mappings between graphs |
819 | // graph_small and graph_large. Continues until user_callback returns true or the |
820 | // search space has been fully explored. |
821 | template <problem_selector problem_selection, |
822 | typename GraphSmall, |
823 | typename GraphLarge, |
824 | typename IndexMapSmall, |
825 | typename IndexMapLarge, |
826 | typename VertexOrderSmall, |
827 | typename EdgeEquivalencePredicate, |
828 | typename VertexEquivalencePredicate, |
829 | typename SubGraphIsoMapCallback> |
830 | bool vf2_subgraph_morphism(const GraphSmall& graph_small, const GraphLarge& graph_large, |
831 | SubGraphIsoMapCallback user_callback, |
832 | IndexMapSmall index_map_small, IndexMapLarge index_map_large, |
833 | const VertexOrderSmall& vertex_order_small, |
834 | EdgeEquivalencePredicate edge_comp, |
835 | VertexEquivalencePredicate vertex_comp) { |
836 | |
837 | // Graph requirements |
838 | BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<GraphSmall> )); |
839 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<GraphSmall> )); |
840 | BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<GraphSmall> )); |
841 | BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<GraphSmall> )); |
842 | |
843 | BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<GraphLarge> )); |
844 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<GraphLarge> )); |
845 | BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<GraphLarge> )); |
846 | BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<GraphLarge> )); |
847 | |
848 | typedef typename graph_traits<GraphSmall>::vertex_descriptor vertex_small_type; |
849 | typedef typename graph_traits<GraphLarge>::vertex_descriptor vertex_large_type; |
850 | |
851 | typedef typename graph_traits<GraphSmall>::vertices_size_type size_type_small; |
852 | typedef typename graph_traits<GraphLarge>::vertices_size_type size_type_large; |
853 | |
854 | // Property map requirements |
855 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMapSmall, vertex_small_type> )); |
856 | typedef typename property_traits<IndexMapSmall>::value_type IndexMapSmallValue; |
857 | BOOST_STATIC_ASSERT(( is_convertible<IndexMapSmallValue, size_type_small>::value )); |
858 | |
859 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMapLarge, vertex_large_type> )); |
860 | typedef typename property_traits<IndexMapLarge>::value_type IndexMapLargeValue; |
861 | BOOST_STATIC_ASSERT(( is_convertible<IndexMapLargeValue, size_type_large>::value )); |
862 | |
863 | // Edge & vertex requirements |
864 | typedef typename graph_traits<GraphSmall>::edge_descriptor edge_small_type; |
865 | typedef typename graph_traits<GraphLarge>::edge_descriptor edge_large_type; |
866 | |
867 | BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeEquivalencePredicate, |
868 | edge_small_type, edge_large_type> )); |
869 | |
870 | BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexEquivalencePredicate, |
871 | vertex_small_type, vertex_large_type> )); |
872 | |
873 | // Vertex order requirements |
874 | BOOST_CONCEPT_ASSERT(( ContainerConcept<VertexOrderSmall> )); |
875 | typedef typename VertexOrderSmall::value_type order_value_type; |
876 | BOOST_STATIC_ASSERT(( is_same<vertex_small_type, order_value_type>::value )); |
877 | BOOST_ASSERT( num_vertices(graph_small) == vertex_order_small.size() ); |
878 | |
879 | if (num_vertices(graph_small) > num_vertices(graph_large)) |
880 | return false; |
881 | |
882 | typename graph_traits<GraphSmall>::edges_size_type num_edges_small = num_edges(graph_small); |
883 | typename graph_traits<GraphLarge>::edges_size_type num_edges_large = num_edges(graph_large); |
884 | |
885 | // Double the number of edges for undirected graphs: each edge counts as |
886 | // in-edge and out-edge |
887 | if (is_undirected(graph_small)) num_edges_small *= 2; |
888 | if (is_undirected(graph_large)) num_edges_large *= 2; |
889 | if (num_edges_small > num_edges_large) |
890 | return false; |
891 | |
892 | detail::state<GraphSmall, GraphLarge, IndexMapSmall, IndexMapLarge, |
893 | EdgeEquivalencePredicate, VertexEquivalencePredicate, |
894 | SubGraphIsoMapCallback, problem_selection> |
895 | s(graph_small, graph_large, index_map_small, index_map_large, edge_comp, vertex_comp); |
896 | |
897 | return detail::match(graph_small, graph_large, user_callback, vertex_order_small, s); |
898 | } |
899 | |
900 | } // namespace detail |
901 | |
902 | |
903 | // Returns vertex order (vertices sorted by multiplicity of in/out degrees) |
904 | template<typename Graph> |
905 | std::vector<typename graph_traits<Graph>::vertex_descriptor> |
906 | vertex_order_by_mult(const Graph& graph) { |
907 | |
908 | std::vector<typename graph_traits<Graph>::vertex_descriptor> vertex_order; |
909 | std::copy(vertices(graph).first, vertices(graph).second, std::back_inserter(vertex_order)); |
910 | |
911 | detail::sort_vertices(graph, get(vertex_index, graph), vertex_order); |
912 | return vertex_order; |
913 | } |
914 | |
915 | |
916 | // Enumerates all graph sub-graph monomorphism mappings between graphs |
917 | // graph_small and graph_large. Continues until user_callback returns true or the |
918 | // search space has been fully explored. |
919 | template <typename GraphSmall, |
920 | typename GraphLarge, |
921 | typename IndexMapSmall, |
922 | typename IndexMapLarge, |
923 | typename VertexOrderSmall, |
924 | typename EdgeEquivalencePredicate, |
925 | typename VertexEquivalencePredicate, |
926 | typename SubGraphIsoMapCallback> |
927 | bool vf2_subgraph_mono(const GraphSmall& graph_small, const GraphLarge& graph_large, |
928 | SubGraphIsoMapCallback user_callback, |
929 | IndexMapSmall index_map_small, IndexMapLarge index_map_large, |
930 | const VertexOrderSmall& vertex_order_small, |
931 | EdgeEquivalencePredicate edge_comp, |
932 | VertexEquivalencePredicate vertex_comp) { |
933 | return detail::vf2_subgraph_morphism<detail::subgraph_mono> |
934 | (graph_small, graph_large, |
935 | user_callback, |
936 | index_map_small, index_map_large, |
937 | vertex_order_small, |
938 | edge_comp, |
939 | vertex_comp); |
940 | } |
941 | |
942 | |
943 | // All default interface for vf2_subgraph_iso |
944 | template <typename GraphSmall, |
945 | typename GraphLarge, |
946 | typename SubGraphIsoMapCallback> |
947 | bool vf2_subgraph_mono(const GraphSmall& graph_small, const GraphLarge& graph_large, |
948 | SubGraphIsoMapCallback user_callback) { |
949 | return vf2_subgraph_mono(graph_small, graph_large, user_callback, |
950 | get(vertex_index, graph_small), get(vertex_index, graph_large), |
951 | vertex_order_by_mult(graph_small), |
952 | always_equivalent(), always_equivalent()); |
953 | } |
954 | |
955 | |
956 | // Named parameter interface of vf2_subgraph_iso |
957 | template <typename GraphSmall, |
958 | typename GraphLarge, |
959 | typename VertexOrderSmall, |
960 | typename SubGraphIsoMapCallback, |
961 | typename Param, |
962 | typename Tag, |
963 | typename Rest> |
964 | bool vf2_subgraph_mono(const GraphSmall& graph_small, const GraphLarge& graph_large, |
965 | SubGraphIsoMapCallback user_callback, |
966 | const VertexOrderSmall& vertex_order_small, |
967 | const bgl_named_params<Param, Tag, Rest>& params) { |
968 | return vf2_subgraph_mono(graph_small, graph_large, user_callback, |
969 | choose_const_pmap(get_param(params, vertex_index1), |
970 | graph_small, vertex_index), |
971 | choose_const_pmap(get_param(params, vertex_index2), |
972 | graph_large, vertex_index), |
973 | vertex_order_small, |
974 | choose_param(get_param(params, edges_equivalent_t()), |
975 | always_equivalent()), |
976 | choose_param(get_param(params, vertices_equivalent_t()), |
977 | always_equivalent()) |
978 | ); |
979 | } |
980 | |
981 | |
982 | // Enumerates all graph sub-graph isomorphism mappings between graphs |
983 | // graph_small and graph_large. Continues until user_callback returns true or the |
984 | // search space has been fully explored. |
985 | template <typename GraphSmall, |
986 | typename GraphLarge, |
987 | typename IndexMapSmall, |
988 | typename IndexMapLarge, |
989 | typename VertexOrderSmall, |
990 | typename EdgeEquivalencePredicate, |
991 | typename VertexEquivalencePredicate, |
992 | typename SubGraphIsoMapCallback> |
993 | bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large, |
994 | SubGraphIsoMapCallback user_callback, |
995 | IndexMapSmall index_map_small, IndexMapLarge index_map_large, |
996 | const VertexOrderSmall& vertex_order_small, |
997 | EdgeEquivalencePredicate edge_comp, |
998 | VertexEquivalencePredicate vertex_comp) { |
999 | return detail::vf2_subgraph_morphism<detail::subgraph_iso> |
1000 | (graph_small, graph_large, |
1001 | user_callback, |
1002 | index_map_small, index_map_large, |
1003 | vertex_order_small, |
1004 | edge_comp, |
1005 | vertex_comp); |
1006 | } |
1007 | |
1008 | |
1009 | // All default interface for vf2_subgraph_iso |
1010 | template <typename GraphSmall, |
1011 | typename GraphLarge, |
1012 | typename SubGraphIsoMapCallback> |
1013 | bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large, |
1014 | SubGraphIsoMapCallback user_callback) { |
1015 | |
1016 | return vf2_subgraph_iso(graph_small, graph_large, user_callback, |
1017 | get(vertex_index, graph_small), get(vertex_index, graph_large), |
1018 | vertex_order_by_mult(graph_small), |
1019 | always_equivalent(), always_equivalent()); |
1020 | } |
1021 | |
1022 | |
1023 | // Named parameter interface of vf2_subgraph_iso |
1024 | template <typename GraphSmall, |
1025 | typename GraphLarge, |
1026 | typename VertexOrderSmall, |
1027 | typename SubGraphIsoMapCallback, |
1028 | typename Param, |
1029 | typename Tag, |
1030 | typename Rest> |
1031 | bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large, |
1032 | SubGraphIsoMapCallback user_callback, |
1033 | const VertexOrderSmall& vertex_order_small, |
1034 | const bgl_named_params<Param, Tag, Rest>& params) { |
1035 | |
1036 | return vf2_subgraph_iso(graph_small, graph_large, user_callback, |
1037 | choose_const_pmap(get_param(params, vertex_index1), |
1038 | graph_small, vertex_index), |
1039 | choose_const_pmap(get_param(params, vertex_index2), |
1040 | graph_large, vertex_index), |
1041 | vertex_order_small, |
1042 | choose_param(get_param(params, edges_equivalent_t()), |
1043 | always_equivalent()), |
1044 | choose_param(get_param(params, vertices_equivalent_t()), |
1045 | always_equivalent()) |
1046 | ); |
1047 | |
1048 | } |
1049 | |
1050 | |
1051 | // Enumerates all isomorphism mappings between graphs graph1_ and graph2_. |
1052 | // Continues until user_callback returns true or the search space has been |
1053 | // fully explored. |
1054 | template <typename Graph1, |
1055 | typename Graph2, |
1056 | typename IndexMap1, |
1057 | typename IndexMap2, |
1058 | typename VertexOrder1, |
1059 | typename EdgeEquivalencePredicate, |
1060 | typename VertexEquivalencePredicate, |
1061 | typename GraphIsoMapCallback> |
1062 | bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2, |
1063 | GraphIsoMapCallback user_callback, |
1064 | IndexMap1 index_map1, IndexMap2 index_map2, |
1065 | const VertexOrder1& vertex_order1, |
1066 | EdgeEquivalencePredicate edge_comp, |
1067 | VertexEquivalencePredicate vertex_comp) { |
1068 | |
1069 | // Graph requirements |
1070 | BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph1> )); |
1071 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph1> )); |
1072 | BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> )); |
1073 | BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph1> )); |
1074 | |
1075 | BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph2> )); |
1076 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph2> )); |
1077 | BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph2> )); |
1078 | BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph2> )); |
1079 | |
1080 | |
1081 | typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_type; |
1082 | typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_type; |
1083 | |
1084 | typedef typename graph_traits<Graph1>::vertices_size_type size_type1; |
1085 | typedef typename graph_traits<Graph2>::vertices_size_type size_type2; |
1086 | |
1087 | // Property map requirements |
1088 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap1, vertex1_type> )); |
1089 | typedef typename property_traits<IndexMap1>::value_type IndexMap1Value; |
1090 | BOOST_STATIC_ASSERT(( is_convertible<IndexMap1Value, size_type1>::value )); |
1091 | |
1092 | BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap2, vertex2_type> )); |
1093 | typedef typename property_traits<IndexMap2>::value_type IndexMap2Value; |
1094 | BOOST_STATIC_ASSERT(( is_convertible<IndexMap2Value, size_type2>::value )); |
1095 | |
1096 | // Edge & vertex requirements |
1097 | typedef typename graph_traits<Graph1>::edge_descriptor edge1_type; |
1098 | typedef typename graph_traits<Graph2>::edge_descriptor edge2_type; |
1099 | |
1100 | BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeEquivalencePredicate, |
1101 | edge1_type, edge2_type> )); |
1102 | |
1103 | BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexEquivalencePredicate, |
1104 | vertex1_type, vertex2_type> )); |
1105 | |
1106 | // Vertex order requirements |
1107 | BOOST_CONCEPT_ASSERT(( ContainerConcept<VertexOrder1> )); |
1108 | typedef typename VertexOrder1::value_type order_value_type; |
1109 | BOOST_STATIC_ASSERT(( is_same<vertex1_type, order_value_type>::value )); |
1110 | BOOST_ASSERT( num_vertices(graph1) == vertex_order1.size() ); |
1111 | |
1112 | if (num_vertices(graph1) != num_vertices(graph2)) |
1113 | return false; |
1114 | |
1115 | typename graph_traits<Graph1>::edges_size_type num_edges1 = num_edges(graph1); |
1116 | typename graph_traits<Graph2>::edges_size_type num_edges2 = num_edges(graph2); |
1117 | |
1118 | // Double the number of edges for undirected graphs: each edge counts as |
1119 | // in-edge and out-edge |
1120 | if (is_undirected(graph1)) num_edges1 *= 2; |
1121 | if (is_undirected(graph2)) num_edges2 *= 2; |
1122 | if (num_edges1 != num_edges2) |
1123 | return false; |
1124 | |
1125 | detail::state<Graph1, Graph2, IndexMap1, IndexMap2, |
1126 | EdgeEquivalencePredicate, VertexEquivalencePredicate, |
1127 | GraphIsoMapCallback, detail::isomorphism> |
1128 | s(graph1, graph2, index_map1, index_map2, edge_comp, vertex_comp); |
1129 | |
1130 | return detail::match(graph1, graph2, user_callback, vertex_order1, s); |
1131 | } |
1132 | |
1133 | |
1134 | // All default interface for vf2_graph_iso |
1135 | template <typename Graph1, |
1136 | typename Graph2, |
1137 | typename GraphIsoMapCallback> |
1138 | bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2, |
1139 | GraphIsoMapCallback user_callback) { |
1140 | |
1141 | return vf2_graph_iso(graph1, graph2, user_callback, |
1142 | get(vertex_index, graph1), get(vertex_index, graph2), |
1143 | vertex_order_by_mult(graph1), |
1144 | always_equivalent(), always_equivalent()); |
1145 | } |
1146 | |
1147 | |
1148 | // Named parameter interface of vf2_graph_iso |
1149 | template <typename Graph1, |
1150 | typename Graph2, |
1151 | typename VertexOrder1, |
1152 | typename GraphIsoMapCallback, |
1153 | typename Param, |
1154 | typename Tag, |
1155 | typename Rest> |
1156 | bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2, |
1157 | GraphIsoMapCallback user_callback, |
1158 | const VertexOrder1& vertex_order1, |
1159 | const bgl_named_params<Param, Tag, Rest>& params) { |
1160 | |
1161 | return vf2_graph_iso(graph1, graph2, user_callback, |
1162 | choose_const_pmap(get_param(params, vertex_index1), |
1163 | graph1, vertex_index), |
1164 | choose_const_pmap(get_param(params, vertex_index2), |
1165 | graph2, vertex_index), |
1166 | vertex_order1, |
1167 | choose_param(get_param(params, edges_equivalent_t()), |
1168 | always_equivalent()), |
1169 | choose_param(get_param(params, vertices_equivalent_t()), |
1170 | always_equivalent()) |
1171 | ); |
1172 | |
1173 | } |
1174 | |
1175 | |
1176 | // Verifies a graph (sub)graph isomorphism map |
1177 | template<typename Graph1, |
1178 | typename Graph2, |
1179 | typename CorresponenceMap1To2, |
1180 | typename EdgeEquivalencePredicate, |
1181 | typename VertexEquivalencePredicate> |
1182 | inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2, |
1183 | const CorresponenceMap1To2 f, |
1184 | EdgeEquivalencePredicate edge_comp, |
1185 | VertexEquivalencePredicate vertex_comp) { |
1186 | |
1187 | BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> )); |
1188 | BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph2> )); |
1189 | |
1190 | detail::equivalent_edge_exists<Graph2> edge2_exists; |
1191 | |
1192 | BGL_FORALL_EDGES_T(e1, graph1, Graph1) { |
1193 | typename graph_traits<Graph1>::vertex_descriptor s1, t1; |
1194 | typename graph_traits<Graph2>::vertex_descriptor s2, t2; |
1195 | |
1196 | s1 = source(e1, graph1); t1 = target(e1, graph1); |
1197 | s2 = get(f, s1); t2 = get(f, t1); |
1198 | |
1199 | if (!vertex_comp(s1, s2) || !vertex_comp(t1, t2)) |
1200 | return false; |
1201 | |
1202 | typename graph_traits<Graph2>::edge_descriptor e2; |
1203 | |
1204 | if (!edge2_exists(s2, t2, |
1205 | detail::edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp, e1), |
1206 | graph2)) |
1207 | return false; |
1208 | |
1209 | } |
1210 | |
1211 | return true; |
1212 | } |
1213 | |
1214 | // Variant of verify_subgraph_iso with all default parameters |
1215 | template<typename Graph1, |
1216 | typename Graph2, |
1217 | typename CorresponenceMap1To2> |
1218 | inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2, |
1219 | const CorresponenceMap1To2 f) { |
1220 | return verify_vf2_subgraph_iso(graph1, graph2, f, |
1221 | always_equivalent(), always_equivalent()); |
1222 | } |
1223 | |
1224 | |
1225 | |
1226 | } // namespace boost |
1227 | |
1228 | #ifdef BOOST_ISO_INCLUDED_ITER_MACROS |
1229 | #undef BOOST_ISO_INCLUDED_ITER_MACROS |
1230 | #include <boost/graph/iteration_macros_undef.hpp> |
1231 | #endif |
1232 | |
1233 | #endif // BOOST_VF2_SUB_GRAPH_ISO_HPP |
1234 | |