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
   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
  52     vf2_print_callback(const Graph1& graph1, const Graph2& graph2)
  53     : graph1_(graph1), graph2_(graph2)
  54     {
  55     }
  56
  57     template < typename CorrespondenceMap1To2, typename CorrespondenceMap2To1 >
  58     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:
 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
 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
 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
 243         bool term_in() const { return core_count_ < term_in_count_; }
 244
 245         // Returns true if vertex belongs to the in-terminal set
 246         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
 253         bool term_out() const { return core_count_ < term_out_count_; }
 254
 255         // Returns true if vertex belongs to the out-terminal set
 256         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
 263         bool term_both() const { return core_count_ < term_both_count_; }
 264
 265         // Returns true if vertex belongs to both (in- and out-terminal) sets
 266         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
 274         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
 280         size_type count() const { return core_count_; }
 281
 282         // Returns the image (in graph_other) of vertex v (in graph_this)
 283         vertex_other_type core(const vertex_this_type& v) const
 284         {
 285             return get(core_, v);
 286         }
 287
 288         // Returns the mapping
 289         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
 293         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
 300         size_type out_depth(const vertex_this_type& v) const
 301         {
 302             return get(out_, v);
 303         }
 304
 305         // Returns the terminal set counts
 306         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 >
 324         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 >
 351         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
 375         edge1_predicate(EdgeEquivalencePredicate edge_comp,
 376             typename graph_traits< Graph2 >::edge_descriptor e2)
 377         : edge_comp_(edge_comp), e2_(e2)
 378         {
 379         }
 380
 381         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
 397         edge2_predicate(EdgeEquivalencePredicate edge_comp,
 398             typename graph_traits< Graph1 >::edge_descriptor e1)
 399         : edge_comp_(edge_comp), e1_(e1)
 400         {
 401         }
 402
 403         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
 452         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
 459         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
 466         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:
 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
 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
 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
 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
 676         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
 690         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
 703         bool success() const
 704         {
 705             return state1_.count() == num_vertices(graph1_);
 706         }
 707
 708         // Returns true if a state is valid
 709         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
 731         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 >
 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
 834         vertex_in_out_degree_cmp(const Graph& graph) : graph_(graph) {}
 835
 836         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
 852         vertex_frequency_degree_cmp(const Graph& graph, FrequencyMap freq)
 853         : graph_(graph), freq_(freq)
 854         {
 855         }
 856
 857         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 >
 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 >
 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 >
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 >
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 >
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 >
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 >
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 >
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 >
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 >
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 >
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 >
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 >
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 >
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