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
44namespace 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

source code of boost/boost/graph/vf2_sub_graph_iso.hpp