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