Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:37:40 

0001 //=======================================================================
0002 // Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi@gmail.com)
0003 // Copyright (C) 2013 Jakob Lykke Andersen, University of Southern Denmark
0004 // (jlandersen@imada.sdu.dk)
0005 //
0006 // The algorithm implemented here is derived from original ideas by
0007 // Pasquale Foggia and colaborators. For further information see
0008 // e.g. Cordella et al. 2001, 2004.
0009 //
0010 // Distributed under the Boost Software License, Version 1.0. (See
0011 // accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013 //=======================================================================
0014 
0015 // Revision History:
0016 //   8 April 2013: Fixed a typo in vf2_print_callback. (Flavio De Lorenzi)
0017 
0018 #ifndef BOOST_VF2_SUB_GRAPH_ISO_HPP
0019 #define BOOST_VF2_SUB_GRAPH_ISO_HPP
0020 
0021 #include <iostream>
0022 #include <iomanip>
0023 #include <iterator>
0024 #include <vector>
0025 #include <utility>
0026 
0027 #include <boost/assert.hpp>
0028 #include <boost/concept/assert.hpp>
0029 #include <boost/concept_check.hpp>
0030 #include <boost/graph/graph_utility.hpp>
0031 #include <boost/graph/graph_traits.hpp>
0032 #include <boost/graph/mcgregor_common_subgraphs.hpp> // for always_equivalent
0033 #include <boost/graph/named_function_params.hpp>
0034 #include <boost/type_traits/has_less.hpp>
0035 #include <boost/mpl/int.hpp>
0036 #include <boost/range/algorithm/sort.hpp>
0037 #include <boost/tuple/tuple.hpp>
0038 #include <boost/utility/enable_if.hpp>
0039 
0040 #ifndef BOOST_GRAPH_ITERATION_MACROS_HPP
0041 #define BOOST_ISO_INCLUDED_ITER_MACROS // local macro, see bottom of file
0042 #include <boost/graph/iteration_macros.hpp>
0043 #endif
0044 
0045 namespace boost
0046 {
0047 
0048 // Default print_callback
0049 template < typename Graph1, typename Graph2 > struct vf2_print_callback
0050 {
0051 
0052     vf2_print_callback(const Graph1& graph1, const Graph2& graph2)
0053     : graph1_(graph1), graph2_(graph2)
0054     {
0055     }
0056 
0057     template < typename CorrespondenceMap1To2, typename CorrespondenceMap2To1 >
0058     bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const
0059     {
0060 
0061         // Print (sub)graph isomorphism map
0062         BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
0063         std::cout << '(' << get(vertex_index_t(), graph1_, v) << ", "
0064                   << get(vertex_index_t(), graph2_, get(f, v)) << ") ";
0065 
0066         std::cout << std::endl;
0067 
0068         return true;
0069     }
0070 
0071 private:
0072     const Graph1& graph1_;
0073     const Graph2& graph2_;
0074 };
0075 
0076 namespace detail
0077 {
0078 
0079     // State associated with a single graph (graph_this)
0080     template < typename GraphThis, typename GraphOther, typename IndexMapThis,
0081         typename IndexMapOther >
0082     class base_state
0083     {
0084 
0085         typedef typename graph_traits< GraphThis >::vertex_descriptor
0086             vertex_this_type;
0087         typedef typename graph_traits< GraphOther >::vertex_descriptor
0088             vertex_other_type;
0089 
0090         typedef
0091             typename graph_traits< GraphThis >::vertices_size_type size_type;
0092 
0093         const GraphThis& graph_this_;
0094         const GraphOther& graph_other_;
0095 
0096         IndexMapThis index_map_this_;
0097         IndexMapOther index_map_other_;
0098 
0099         std::vector< vertex_other_type > core_vec_;
0100         typedef iterator_property_map<
0101             typename std::vector< vertex_other_type >::iterator, IndexMapThis,
0102             vertex_other_type, vertex_other_type& >
0103             core_map_type;
0104         core_map_type core_;
0105 
0106         std::vector< size_type > in_vec_, out_vec_;
0107         typedef iterator_property_map<
0108             typename std::vector< size_type >::iterator, IndexMapThis,
0109             size_type, size_type& >
0110             in_out_map_type;
0111         in_out_map_type in_, out_;
0112 
0113         size_type term_in_count_, term_out_count_, term_both_count_,
0114             core_count_;
0115 
0116         // Forbidden
0117         base_state(const base_state&);
0118         base_state& operator=(const base_state&);
0119 
0120     public:
0121         base_state(const GraphThis& graph_this, const GraphOther& graph_other,
0122             IndexMapThis index_map_this, IndexMapOther index_map_other)
0123         : graph_this_(graph_this)
0124         , graph_other_(graph_other)
0125         , index_map_this_(index_map_this)
0126         , index_map_other_(index_map_other)
0127         , core_vec_(num_vertices(graph_this_),
0128               graph_traits< GraphOther >::null_vertex())
0129         , core_(core_vec_.begin(), index_map_this_)
0130         , in_vec_(num_vertices(graph_this_), 0)
0131         , out_vec_(num_vertices(graph_this_), 0)
0132         , in_(in_vec_.begin(), index_map_this_)
0133         , out_(out_vec_.begin(), index_map_this_)
0134         , term_in_count_(0)
0135         , term_out_count_(0)
0136         , term_both_count_(0)
0137         , core_count_(0)
0138         {
0139         }
0140 
0141         // Adds a vertex pair to the state of graph graph_this
0142         void push(
0143             const vertex_this_type& v_this, const vertex_other_type& v_other)
0144         {
0145 
0146             ++core_count_;
0147 
0148             put(core_, v_this, v_other);
0149 
0150             if (!get(in_, v_this))
0151             {
0152                 put(in_, v_this, core_count_);
0153                 ++term_in_count_;
0154                 if (get(out_, v_this))
0155                     ++term_both_count_;
0156             }
0157 
0158             if (!get(out_, v_this))
0159             {
0160                 put(out_, v_this, core_count_);
0161                 ++term_out_count_;
0162                 if (get(in_, v_this))
0163                     ++term_both_count_;
0164             }
0165 
0166             BGL_FORALL_INEDGES_T(v_this, e, graph_this_, GraphThis)
0167             {
0168                 vertex_this_type w = source(e, graph_this_);
0169                 if (!get(in_, w))
0170                 {
0171                     put(in_, w, core_count_);
0172                     ++term_in_count_;
0173                     if (get(out_, w))
0174                         ++term_both_count_;
0175                 }
0176             }
0177 
0178             BGL_FORALL_OUTEDGES_T(v_this, e, graph_this_, GraphThis)
0179             {
0180                 vertex_this_type w = target(e, graph_this_);
0181                 if (!get(out_, w))
0182                 {
0183                     put(out_, w, core_count_);
0184                     ++term_out_count_;
0185                     if (get(in_, w))
0186                         ++term_both_count_;
0187                 }
0188             }
0189         }
0190 
0191         // Removes vertex pair from state of graph_this
0192         void pop(const vertex_this_type& v_this, const vertex_other_type&)
0193         {
0194 
0195             if (!core_count_)
0196                 return;
0197 
0198             if (get(in_, v_this) == core_count_)
0199             {
0200                 put(in_, v_this, 0);
0201                 --term_in_count_;
0202                 if (get(out_, v_this))
0203                     --term_both_count_;
0204             }
0205 
0206             BGL_FORALL_INEDGES_T(v_this, e, graph_this_, GraphThis)
0207             {
0208                 vertex_this_type w = source(e, graph_this_);
0209                 if (get(in_, w) == core_count_)
0210                 {
0211                     put(in_, w, 0);
0212                     --term_in_count_;
0213                     if (get(out_, w))
0214                         --term_both_count_;
0215                 }
0216             }
0217 
0218             if (get(out_, v_this) == core_count_)
0219             {
0220                 put(out_, v_this, 0);
0221                 --term_out_count_;
0222                 if (get(in_, v_this))
0223                     --term_both_count_;
0224             }
0225 
0226             BGL_FORALL_OUTEDGES_T(v_this, e, graph_this_, GraphThis)
0227             {
0228                 vertex_this_type w = target(e, graph_this_);
0229                 if (get(out_, w) == core_count_)
0230                 {
0231                     put(out_, w, 0);
0232                     --term_out_count_;
0233                     if (get(in_, w))
0234                         --term_both_count_;
0235                 }
0236             }
0237             put(core_, v_this, graph_traits< GraphOther >::null_vertex());
0238 
0239             --core_count_;
0240         }
0241 
0242         // Returns true if the in-terminal set is not empty
0243         bool term_in() const { return core_count_ < term_in_count_; }
0244 
0245         // Returns true if vertex belongs to the in-terminal set
0246         bool term_in(const vertex_this_type& v) const
0247         {
0248             return (get(in_, v) > 0)
0249                 && (get(core_, v) == graph_traits< GraphOther >::null_vertex());
0250         }
0251 
0252         // Returns true if the out-terminal set is not empty
0253         bool term_out() const { return core_count_ < term_out_count_; }
0254 
0255         // Returns true if vertex belongs to the out-terminal set
0256         bool term_out(const vertex_this_type& v) const
0257         {
0258             return (get(out_, v) > 0)
0259                 && (get(core_, v) == graph_traits< GraphOther >::null_vertex());
0260         }
0261 
0262         // Returns true of both (in- and out-terminal) sets are not empty
0263         bool term_both() const { return core_count_ < term_both_count_; }
0264 
0265         // Returns true if vertex belongs to both (in- and out-terminal) sets
0266         bool term_both(const vertex_this_type& v) const
0267         {
0268             return (get(in_, v) > 0) && (get(out_, v) > 0)
0269                 && (get(core_, v) == graph_traits< GraphOther >::null_vertex());
0270         }
0271 
0272         // Returns true if vertex belongs to the core map, i.e. it is in the
0273         // present mapping
0274         bool in_core(const vertex_this_type& v) const
0275         {
0276             return get(core_, v) != graph_traits< GraphOther >::null_vertex();
0277         }
0278 
0279         // Returns the number of vertices in the mapping
0280         size_type count() const { return core_count_; }
0281 
0282         // Returns the image (in graph_other) of vertex v (in graph_this)
0283         vertex_other_type core(const vertex_this_type& v) const
0284         {
0285             return get(core_, v);
0286         }
0287 
0288         // Returns the mapping
0289         core_map_type get_map() const { return core_; }
0290 
0291         // Returns the "time" (or depth) when vertex was added to the
0292         // in-terminal set
0293         size_type in_depth(const vertex_this_type& v) const
0294         {
0295             return get(in_, v);
0296         }
0297 
0298         // Returns the "time" (or depth) when vertex was added to the
0299         // out-terminal set
0300         size_type out_depth(const vertex_this_type& v) const
0301         {
0302             return get(out_, v);
0303         }
0304 
0305         // Returns the terminal set counts
0306         boost::tuple< size_type, size_type, size_type > term_set() const
0307         {
0308             return boost::make_tuple(
0309                 term_in_count_, term_out_count_, term_both_count_);
0310         }
0311     };
0312 
0313     // Function object that checks whether a valid edge
0314     // exists. For multi-graphs matched edges are excluded
0315     template < typename Graph, typename Enable = void >
0316     struct equivalent_edge_exists
0317     {
0318         typedef
0319             typename boost::graph_traits< Graph >::edge_descriptor edge_type;
0320 
0321         BOOST_CONCEPT_ASSERT((LessThanComparable< edge_type >));
0322 
0323         template < typename EdgePredicate >
0324         bool operator()(typename graph_traits< Graph >::vertex_descriptor s,
0325             typename graph_traits< Graph >::vertex_descriptor t,
0326             EdgePredicate is_valid_edge, const Graph& g)
0327         {
0328 
0329             BGL_FORALL_OUTEDGES_T(s, e, g, Graph)
0330             {
0331                 if ((target(e, g) == t) && is_valid_edge(e)
0332                     && (matched_edges_.find(e) == matched_edges_.end()))
0333                 {
0334                     matched_edges_.insert(e);
0335                     return true;
0336                 }
0337             }
0338 
0339             return false;
0340         }
0341 
0342     private:
0343         std::set< edge_type > matched_edges_;
0344     };
0345 
0346     template < typename Graph >
0347     struct equivalent_edge_exists< Graph,
0348         typename boost::disable_if< is_multigraph< Graph > >::type >
0349     {
0350         template < typename EdgePredicate >
0351         bool operator()(typename graph_traits< Graph >::vertex_descriptor s,
0352             typename graph_traits< Graph >::vertex_descriptor t,
0353             EdgePredicate is_valid_edge, const Graph& g)
0354         {
0355 
0356             typename graph_traits< Graph >::edge_descriptor e;
0357             bool found;
0358             boost::tie(e, found) = edge(s, t, g);
0359             if (!found)
0360                 return false;
0361             else if (is_valid_edge(e))
0362                 return true;
0363 
0364             return false;
0365         }
0366     };
0367 
0368     // Generates a predicate for edge e1 given  a binary predicate and a
0369     // fixed edge e2
0370     template < typename Graph1, typename Graph2,
0371         typename EdgeEquivalencePredicate >
0372     struct edge1_predicate
0373     {
0374 
0375         edge1_predicate(EdgeEquivalencePredicate edge_comp,
0376             typename graph_traits< Graph2 >::edge_descriptor e2)
0377         : edge_comp_(edge_comp), e2_(e2)
0378         {
0379         }
0380 
0381         bool operator()(typename graph_traits< Graph1 >::edge_descriptor e1)
0382         {
0383             return edge_comp_(e1, e2_);
0384         }
0385 
0386         EdgeEquivalencePredicate edge_comp_;
0387         typename graph_traits< Graph2 >::edge_descriptor e2_;
0388     };
0389 
0390     // Generates a predicate for edge e2 given given a binary predicate and a
0391     // fixed edge e1
0392     template < typename Graph1, typename Graph2,
0393         typename EdgeEquivalencePredicate >
0394     struct edge2_predicate
0395     {
0396 
0397         edge2_predicate(EdgeEquivalencePredicate edge_comp,
0398             typename graph_traits< Graph1 >::edge_descriptor e1)
0399         : edge_comp_(edge_comp), e1_(e1)
0400         {
0401         }
0402 
0403         bool operator()(typename graph_traits< Graph2 >::edge_descriptor e2)
0404         {
0405             return edge_comp_(e1_, e2);
0406         }
0407 
0408         EdgeEquivalencePredicate edge_comp_;
0409         typename graph_traits< Graph1 >::edge_descriptor e1_;
0410     };
0411 
0412     enum problem_selector
0413     {
0414         subgraph_mono,
0415         subgraph_iso,
0416         isomorphism
0417     };
0418 
0419     // The actual state associated with both graphs
0420     template < typename Graph1, typename Graph2, typename IndexMap1,
0421         typename IndexMap2, typename EdgeEquivalencePredicate,
0422         typename VertexEquivalencePredicate, typename SubGraphIsoMapCallback,
0423         problem_selector problem_selection >
0424     class state
0425     {
0426 
0427         typedef typename graph_traits< Graph1 >::vertex_descriptor vertex1_type;
0428         typedef typename graph_traits< Graph2 >::vertex_descriptor vertex2_type;
0429 
0430         typedef typename graph_traits< Graph1 >::edge_descriptor edge1_type;
0431         typedef typename graph_traits< Graph2 >::edge_descriptor edge2_type;
0432 
0433         typedef typename graph_traits< Graph1 >::vertices_size_type
0434             graph1_size_type;
0435         typedef typename graph_traits< Graph2 >::vertices_size_type
0436             graph2_size_type;
0437 
0438         const Graph1& graph1_;
0439         const Graph2& graph2_;
0440 
0441         IndexMap1 index_map1_;
0442 
0443         EdgeEquivalencePredicate edge_comp_;
0444         VertexEquivalencePredicate vertex_comp_;
0445 
0446         base_state< Graph1, Graph2, IndexMap1, IndexMap2 > state1_;
0447         base_state< Graph2, Graph1, IndexMap2, IndexMap1 > state2_;
0448 
0449         // Three helper functions used in Feasibility and Valid functions to
0450         // test terminal set counts when testing for:
0451         // - graph sub-graph monomorphism, or
0452         inline bool comp_term_sets(graph1_size_type a, graph2_size_type b,
0453             boost::mpl::int_< subgraph_mono >) const
0454         {
0455             return a <= b;
0456         }
0457 
0458         // - graph sub-graph isomorphism, or
0459         inline bool comp_term_sets(graph1_size_type a, graph2_size_type b,
0460             boost::mpl::int_< subgraph_iso >) const
0461         {
0462             return a <= b;
0463         }
0464 
0465         // - graph isomorphism
0466         inline bool comp_term_sets(graph1_size_type a, graph2_size_type b,
0467             boost::mpl::int_< isomorphism >) const
0468         {
0469             return a == b;
0470         }
0471 
0472         // Forbidden
0473         state(const state&);
0474         state& operator=(const state&);
0475 
0476     public:
0477         state(const Graph1& graph1, const Graph2& graph2, IndexMap1 index_map1,
0478             IndexMap2 index_map2, EdgeEquivalencePredicate edge_comp,
0479             VertexEquivalencePredicate vertex_comp)
0480         : graph1_(graph1)
0481         , graph2_(graph2)
0482         , index_map1_(index_map1)
0483         , edge_comp_(edge_comp)
0484         , vertex_comp_(vertex_comp)
0485         , state1_(graph1, graph2, index_map1, index_map2)
0486         , state2_(graph2, graph1, index_map2, index_map1)
0487         {
0488         }
0489 
0490         // Add vertex pair to the state
0491         void push(const vertex1_type& v, const vertex2_type& w)
0492         {
0493             state1_.push(v, w);
0494             state2_.push(w, v);
0495         }
0496 
0497         // Remove vertex pair from state
0498         void pop(const vertex1_type& v, const vertex2_type&)
0499         {
0500             vertex2_type w = state1_.core(v);
0501             state1_.pop(v, w);
0502             state2_.pop(w, v);
0503         }
0504 
0505         // Checks the feasibility of a new vertex pair
0506         bool feasible(const vertex1_type& v_new, const vertex2_type& w_new)
0507         {
0508 
0509             if (!vertex_comp_(v_new, w_new))
0510                 return false;
0511 
0512             // graph1
0513             graph1_size_type term_in1_count = 0, term_out1_count = 0,
0514                              rest1_count = 0;
0515 
0516             {
0517                 equivalent_edge_exists< Graph2 > edge2_exists;
0518 
0519                 BGL_FORALL_INEDGES_T(v_new, e1, graph1_, Graph1)
0520                 {
0521                     vertex1_type v = source(e1, graph1_);
0522 
0523                     if (state1_.in_core(v) || (v == v_new))
0524                     {
0525                         vertex2_type w = w_new;
0526                         if (v != v_new)
0527                             w = state1_.core(v);
0528                         if (!edge2_exists(w, w_new,
0529                                 edge2_predicate< Graph1, Graph2,
0530                                     EdgeEquivalencePredicate >(edge_comp_, e1),
0531                                 graph2_))
0532                             return false;
0533                     }
0534                     else
0535                     {
0536                         if (0 < state1_.in_depth(v))
0537                             ++term_in1_count;
0538                         if (0 < state1_.out_depth(v))
0539                             ++term_out1_count;
0540                         if ((state1_.in_depth(v) == 0)
0541                             && (state1_.out_depth(v) == 0))
0542                             ++rest1_count;
0543                     }
0544                 }
0545             }
0546 
0547             {
0548                 equivalent_edge_exists< Graph2 > edge2_exists;
0549 
0550                 BGL_FORALL_OUTEDGES_T(v_new, e1, graph1_, Graph1)
0551                 {
0552                     vertex1_type v = target(e1, graph1_);
0553                     if (state1_.in_core(v) || (v == v_new))
0554                     {
0555                         vertex2_type w = w_new;
0556                         if (v != v_new)
0557                             w = state1_.core(v);
0558 
0559                         if (!edge2_exists(w_new, w,
0560                                 edge2_predicate< Graph1, Graph2,
0561                                     EdgeEquivalencePredicate >(edge_comp_, e1),
0562                                 graph2_))
0563                             return false;
0564                     }
0565                     else
0566                     {
0567                         if (0 < state1_.in_depth(v))
0568                             ++term_in1_count;
0569                         if (0 < state1_.out_depth(v))
0570                             ++term_out1_count;
0571                         if ((state1_.in_depth(v) == 0)
0572                             && (state1_.out_depth(v) == 0))
0573                             ++rest1_count;
0574                     }
0575                 }
0576             }
0577 
0578             // graph2
0579             graph2_size_type term_out2_count = 0, term_in2_count = 0,
0580                              rest2_count = 0;
0581 
0582             {
0583                 equivalent_edge_exists< Graph1 > edge1_exists;
0584 
0585                 BGL_FORALL_INEDGES_T(w_new, e2, graph2_, Graph2)
0586                 {
0587                     vertex2_type w = source(e2, graph2_);
0588                     if (state2_.in_core(w) || (w == w_new))
0589                     {
0590                         if (problem_selection != subgraph_mono)
0591                         {
0592                             vertex1_type v = v_new;
0593                             if (w != w_new)
0594                                 v = state2_.core(w);
0595 
0596                             if (!edge1_exists(v, v_new,
0597                                     edge1_predicate< Graph1, Graph2,
0598                                         EdgeEquivalencePredicate >(
0599                                         edge_comp_, e2),
0600                                     graph1_))
0601                                 return false;
0602                         }
0603                     }
0604                     else
0605                     {
0606                         if (0 < state2_.in_depth(w))
0607                             ++term_in2_count;
0608                         if (0 < state2_.out_depth(w))
0609                             ++term_out2_count;
0610                         if ((state2_.in_depth(w) == 0)
0611                             && (state2_.out_depth(w) == 0))
0612                             ++rest2_count;
0613                     }
0614                 }
0615             }
0616 
0617             {
0618                 equivalent_edge_exists< Graph1 > edge1_exists;
0619 
0620                 BGL_FORALL_OUTEDGES_T(w_new, e2, graph2_, Graph2)
0621                 {
0622                     vertex2_type w = target(e2, graph2_);
0623                     if (state2_.in_core(w) || (w == w_new))
0624                     {
0625                         if (problem_selection != subgraph_mono)
0626                         {
0627                             vertex1_type v = v_new;
0628                             if (w != w_new)
0629                                 v = state2_.core(w);
0630 
0631                             if (!edge1_exists(v_new, v,
0632                                     edge1_predicate< Graph1, Graph2,
0633                                         EdgeEquivalencePredicate >(
0634                                         edge_comp_, e2),
0635                                     graph1_))
0636                                 return false;
0637                         }
0638                     }
0639                     else
0640                     {
0641                         if (0 < state2_.in_depth(w))
0642                             ++term_in2_count;
0643                         if (0 < state2_.out_depth(w))
0644                             ++term_out2_count;
0645                         if ((state2_.in_depth(w) == 0)
0646                             && (state2_.out_depth(w) == 0))
0647                             ++rest2_count;
0648                     }
0649                 }
0650             }
0651 
0652             if (problem_selection != subgraph_mono)
0653             { // subgraph_iso and isomorphism
0654                 return comp_term_sets(term_in1_count, term_in2_count,
0655                            boost::mpl::int_< problem_selection >())
0656                     && comp_term_sets(term_out1_count, term_out2_count,
0657                         boost::mpl::int_< problem_selection >())
0658                     && comp_term_sets(rest1_count, rest2_count,
0659                         boost::mpl::int_< problem_selection >());
0660             }
0661             else
0662             { // subgraph_mono
0663                 return comp_term_sets(term_in1_count, term_in2_count,
0664                            boost::mpl::int_< problem_selection >())
0665                     && comp_term_sets(term_out1_count, term_out2_count,
0666                         boost::mpl::int_< problem_selection >())
0667                     && comp_term_sets(
0668                         term_in1_count + term_out1_count + rest1_count,
0669                         term_in2_count + term_out2_count + rest2_count,
0670                         boost::mpl::int_< problem_selection >());
0671             }
0672         }
0673 
0674         // Returns true if vertex v in graph1 is a possible candidate to
0675         // be added to the current state
0676         bool possible_candidate1(const vertex1_type& v) const
0677         {
0678             if (state1_.term_both() && state2_.term_both())
0679                 return state1_.term_both(v);
0680             else if (state1_.term_out() && state2_.term_out())
0681                 return state1_.term_out(v);
0682             else if (state1_.term_in() && state2_.term_in())
0683                 return state1_.term_in(v);
0684             else
0685                 return !state1_.in_core(v);
0686         }
0687 
0688         // Returns true if vertex w in graph2 is a possible candidate to
0689         // be added to the current state
0690         bool possible_candidate2(const vertex2_type& w) const
0691         {
0692             if (state1_.term_both() && state2_.term_both())
0693                 return state2_.term_both(w);
0694             else if (state1_.term_out() && state2_.term_out())
0695                 return state2_.term_out(w);
0696             else if (state1_.term_in() && state2_.term_in())
0697                 return state2_.term_in(w);
0698             else
0699                 return !state2_.in_core(w);
0700         }
0701 
0702         // Returns true if a mapping was found
0703         bool success() const
0704         {
0705             return state1_.count() == num_vertices(graph1_);
0706         }
0707 
0708         // Returns true if a state is valid
0709         bool valid() const
0710         {
0711             boost::tuple< graph1_size_type, graph1_size_type, graph1_size_type >
0712                 term1;
0713             boost::tuple< graph2_size_type, graph2_size_type, graph2_size_type >
0714                 term2;
0715 
0716             term1 = state1_.term_set();
0717             term2 = state2_.term_set();
0718 
0719             return comp_term_sets(boost::get< 0 >(term1),
0720                        boost::get< 0 >(term2),
0721                        boost::mpl::int_< problem_selection >())
0722                 && comp_term_sets(boost::get< 1 >(term1),
0723                     boost::get< 1 >(term2),
0724                     boost::mpl::int_< problem_selection >())
0725                 && comp_term_sets(boost::get< 2 >(term1),
0726                     boost::get< 2 >(term2),
0727                     boost::mpl::int_< problem_selection >());
0728         }
0729 
0730         // Calls the user_callback with a graph (sub)graph mapping
0731         bool call_back(SubGraphIsoMapCallback user_callback) const
0732         {
0733             return user_callback(state1_.get_map(), state2_.get_map());
0734         }
0735     };
0736 
0737     // Data structure to keep info used for back tracking during
0738     // matching process
0739     template < typename Graph1, typename Graph2, typename VertexOrder1 >
0740     struct vf2_match_continuation
0741     {
0742         typename VertexOrder1::const_iterator graph1_verts_iter;
0743         typename graph_traits< Graph2 >::vertex_iterator graph2_verts_iter;
0744     };
0745 
0746     // Non-recursive method that explores state space using a depth-first
0747     // search strategy.  At each depth possible pairs candidate are compute
0748     // and tested for feasibility to extend the mapping. If a complete
0749     // mapping is found, the mapping is output to user_callback in the form
0750     // of a correspondence map (graph1 to graph2). Returning false from the
0751     // user_callback will terminate the search. Function match will return
0752     // true if the entire search space was explored.
0753     template < typename Graph1, typename Graph2, typename IndexMap1,
0754         typename IndexMap2, typename VertexOrder1,
0755         typename EdgeEquivalencePredicate, typename VertexEquivalencePredicate,
0756         typename SubGraphIsoMapCallback, problem_selector problem_selection >
0757     bool match(const Graph1& graph1, const Graph2& graph2,
0758         SubGraphIsoMapCallback user_callback, const VertexOrder1& vertex_order1,
0759         state< Graph1, Graph2, IndexMap1, IndexMap2, EdgeEquivalencePredicate,
0760             VertexEquivalencePredicate, SubGraphIsoMapCallback,
0761             problem_selection >& s)
0762     {
0763 
0764         typename VertexOrder1::const_iterator graph1_verts_iter;
0765 
0766         typedef typename graph_traits< Graph2 >::vertex_iterator
0767             vertex2_iterator_type;
0768         vertex2_iterator_type graph2_verts_iter, graph2_verts_iter_end;
0769 
0770         typedef vf2_match_continuation< Graph1, Graph2, VertexOrder1 >
0771             match_continuation_type;
0772         std::vector< match_continuation_type > k;
0773         bool found_match = false;
0774 
0775     recur:
0776         if (s.success())
0777         {
0778             if (!s.call_back(user_callback))
0779                 return true;
0780             found_match = true;
0781 
0782             goto back_track;
0783         }
0784 
0785         if (!s.valid())
0786             goto back_track;
0787 
0788         graph1_verts_iter = vertex_order1.begin();
0789         while (graph1_verts_iter != vertex_order1.end()
0790             && !s.possible_candidate1(*graph1_verts_iter))
0791         {
0792             ++graph1_verts_iter;
0793         }
0794 
0795         boost::tie(graph2_verts_iter, graph2_verts_iter_end) = vertices(graph2);
0796         while (graph2_verts_iter != graph2_verts_iter_end)
0797         {
0798             if (s.possible_candidate2(*graph2_verts_iter))
0799             {
0800                 if (s.feasible(*graph1_verts_iter, *graph2_verts_iter))
0801                 {
0802                     match_continuation_type kk;
0803                     kk.graph1_verts_iter = graph1_verts_iter;
0804                     kk.graph2_verts_iter = graph2_verts_iter;
0805                     k.push_back(kk);
0806 
0807                     s.push(*graph1_verts_iter, *graph2_verts_iter);
0808                     goto recur;
0809                 }
0810             }
0811         graph2_loop:
0812             ++graph2_verts_iter;
0813         }
0814 
0815     back_track:
0816         if (k.empty())
0817             return found_match;
0818 
0819         const match_continuation_type kk = k.back();
0820         graph1_verts_iter = kk.graph1_verts_iter;
0821         graph2_verts_iter = kk.graph2_verts_iter;
0822         k.pop_back();
0823 
0824         s.pop(*graph1_verts_iter, *graph2_verts_iter);
0825 
0826         goto graph2_loop;
0827     }
0828 
0829     // Used to sort nodes by in/out degrees
0830     template < typename Graph > struct vertex_in_out_degree_cmp
0831     {
0832         typedef typename graph_traits< Graph >::vertex_descriptor vertex_type;
0833 
0834         vertex_in_out_degree_cmp(const Graph& graph) : graph_(graph) {}
0835 
0836         bool operator()(const vertex_type& v, const vertex_type& w) const
0837         {
0838             // lexicographical comparison
0839             return std::make_pair(in_degree(v, graph_), out_degree(v, graph_))
0840                 < std::make_pair(in_degree(w, graph_), out_degree(w, graph_));
0841         }
0842 
0843         const Graph& graph_;
0844     };
0845 
0846     // Used to sort nodes by multiplicity of in/out degrees
0847     template < typename Graph, typename FrequencyMap >
0848     struct vertex_frequency_degree_cmp
0849     {
0850         typedef typename graph_traits< Graph >::vertex_descriptor vertex_type;
0851 
0852         vertex_frequency_degree_cmp(const Graph& graph, FrequencyMap freq)
0853         : graph_(graph), freq_(freq)
0854         {
0855         }
0856 
0857         bool operator()(const vertex_type& v, const vertex_type& w) const
0858         {
0859             // lexicographical comparison
0860             return std::make_pair(
0861                        freq_[v], in_degree(v, graph_) + out_degree(v, graph_))
0862                 < std::make_pair(
0863                     freq_[w], in_degree(w, graph_) + out_degree(w, graph_));
0864         }
0865 
0866         const Graph& graph_;
0867         FrequencyMap freq_;
0868     };
0869 
0870     // Sorts vertices of a graph by multiplicity of in/out degrees
0871     template < typename Graph, typename IndexMap, typename VertexOrder >
0872     void sort_vertices(
0873         const Graph& graph, IndexMap index_map, VertexOrder& order)
0874     {
0875         typedef typename graph_traits< Graph >::vertices_size_type size_type;
0876 
0877         boost::range::sort(order, vertex_in_out_degree_cmp< Graph >(graph));
0878 
0879         std::vector< size_type > freq_vec(num_vertices(graph), 0);
0880         typedef iterator_property_map<
0881             typename std::vector< size_type >::iterator, IndexMap, size_type,
0882             size_type& >
0883             frequency_map_type;
0884 
0885         frequency_map_type freq
0886             = make_iterator_property_map(freq_vec.begin(), index_map);
0887 
0888         typedef typename VertexOrder::iterator order_iterator;
0889 
0890         for (order_iterator order_iter = order.begin();
0891              order_iter != order.end();)
0892         {
0893             size_type count = 0;
0894             for (order_iterator count_iter = order_iter;
0895                  (count_iter != order.end())
0896                  && (in_degree(*order_iter, graph)
0897                      == in_degree(*count_iter, graph))
0898                  && (out_degree(*order_iter, graph)
0899                      == out_degree(*count_iter, graph));
0900                  ++count_iter)
0901                 ++count;
0902 
0903             for (size_type i = 0; i < count; ++i)
0904             {
0905                 freq[*order_iter] = count;
0906                 ++order_iter;
0907             }
0908         }
0909 
0910         boost::range::sort(order,
0911             vertex_frequency_degree_cmp< Graph, frequency_map_type >(
0912                 graph, freq));
0913     }
0914 
0915     // Enumerates all graph sub-graph mono-/iso-morphism mappings between graphs
0916     // graph_small and graph_large. Continues until user_callback returns true
0917     // or the search space has been fully explored.
0918     template < problem_selector problem_selection, typename GraphSmall,
0919         typename GraphLarge, typename IndexMapSmall, typename IndexMapLarge,
0920         typename VertexOrderSmall, typename EdgeEquivalencePredicate,
0921         typename VertexEquivalencePredicate, typename SubGraphIsoMapCallback >
0922     bool vf2_subgraph_morphism(const GraphSmall& graph_small,
0923         const GraphLarge& graph_large, SubGraphIsoMapCallback user_callback,
0924         IndexMapSmall index_map_small, IndexMapLarge index_map_large,
0925         const VertexOrderSmall& vertex_order_small,
0926         EdgeEquivalencePredicate edge_comp,
0927         VertexEquivalencePredicate vertex_comp)
0928     {
0929 
0930         // Graph requirements
0931         BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept< GraphSmall >));
0932         BOOST_CONCEPT_ASSERT((VertexListGraphConcept< GraphSmall >));
0933         BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< GraphSmall >));
0934         BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< GraphSmall >));
0935 
0936         BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept< GraphLarge >));
0937         BOOST_CONCEPT_ASSERT((VertexListGraphConcept< GraphLarge >));
0938         BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< GraphLarge >));
0939         BOOST_CONCEPT_ASSERT((AdjacencyMatrixConcept< GraphLarge >));
0940 
0941         typedef typename graph_traits< GraphSmall >::vertex_descriptor
0942             vertex_small_type;
0943         typedef typename graph_traits< GraphLarge >::vertex_descriptor
0944             vertex_large_type;
0945 
0946         typedef typename graph_traits< GraphSmall >::vertices_size_type
0947             size_type_small;
0948         typedef typename graph_traits< GraphLarge >::vertices_size_type
0949             size_type_large;
0950 
0951         // Property map requirements
0952         BOOST_CONCEPT_ASSERT(
0953             (ReadablePropertyMapConcept< IndexMapSmall, vertex_small_type >));
0954         typedef typename property_traits< IndexMapSmall >::value_type
0955             IndexMapSmallValue;
0956         BOOST_STATIC_ASSERT(
0957             (is_convertible< IndexMapSmallValue, size_type_small >::value));
0958 
0959         BOOST_CONCEPT_ASSERT(
0960             (ReadablePropertyMapConcept< IndexMapLarge, vertex_large_type >));
0961         typedef typename property_traits< IndexMapLarge >::value_type
0962             IndexMapLargeValue;
0963         BOOST_STATIC_ASSERT(
0964             (is_convertible< IndexMapLargeValue, size_type_large >::value));
0965 
0966         // Edge & vertex requirements
0967         typedef typename graph_traits< GraphSmall >::edge_descriptor
0968             edge_small_type;
0969         typedef typename graph_traits< GraphLarge >::edge_descriptor
0970             edge_large_type;
0971 
0972         BOOST_CONCEPT_ASSERT((BinaryPredicateConcept< EdgeEquivalencePredicate,
0973             edge_small_type, edge_large_type >));
0974 
0975         BOOST_CONCEPT_ASSERT(
0976             (BinaryPredicateConcept< VertexEquivalencePredicate,
0977                 vertex_small_type, vertex_large_type >));
0978 
0979         // Vertex order requirements
0980         BOOST_CONCEPT_ASSERT((ContainerConcept< VertexOrderSmall >));
0981         typedef typename VertexOrderSmall::value_type order_value_type;
0982         BOOST_STATIC_ASSERT(
0983             (is_same< vertex_small_type, order_value_type >::value));
0984         BOOST_ASSERT(num_vertices(graph_small) == vertex_order_small.size());
0985 
0986         if (num_vertices(graph_small) > num_vertices(graph_large))
0987             return false;
0988 
0989         typename graph_traits< GraphSmall >::edges_size_type num_edges_small
0990             = num_edges(graph_small);
0991         typename graph_traits< GraphLarge >::edges_size_type num_edges_large
0992             = num_edges(graph_large);
0993 
0994         // Double the number of edges for undirected graphs: each edge counts as
0995         // in-edge and out-edge
0996         if (is_undirected(graph_small))
0997             num_edges_small *= 2;
0998         if (is_undirected(graph_large))
0999             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
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!