ceph/src/boost/boost/graph/vf2_sub_graph_iso.hpp

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