Chris@16: //=======================================================================
Chris@16: // Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi@gmail.com)
Chris@16: // Copyright (C) 2013 Jakob Lykke Andersen, University of Southern Denmark (jlandersen@imada.sdu.dk)
Chris@16: //
Chris@16: // The algorithm implemented here is derived from original ideas by 
Chris@16: // Pasquale Foggia and colaborators. For further information see 
Chris@16: // e.g. Cordella et al. 2001, 2004.
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: 
Chris@16: // Revision History:
Chris@16: //   8 April 2013: Fixed a typo in vf2_print_callback. (Flavio De Lorenzi) 
Chris@16: 
Chris@16: #ifndef BOOST_VF2_SUB_GRAPH_ISO_HPP
Chris@16: #define BOOST_VF2_SUB_GRAPH_ISO_HPP
Chris@16: 
Chris@16: #include <iostream>
Chris@16: #include <iomanip>
Chris@16: #include <iterator>
Chris@16: #include <vector>
Chris@16: #include <utility>
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: #include <boost/concept_check.hpp>
Chris@16: #include <boost/graph/graph_utility.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/mcgregor_common_subgraphs.hpp> // for always_equivalent
Chris@16: #include <boost/graph/named_function_params.hpp>
Chris@16: #include <boost/type_traits/has_less.hpp>
Chris@16: #include <boost/mpl/int.hpp>
Chris@16: #include <boost/range/algorithm/sort.hpp>
Chris@16: #include <boost/tuple/tuple.hpp>
Chris@16: #include <boost/utility/enable_if.hpp>
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_ITERATION_MACROS_HPP
Chris@16: #define BOOST_ISO_INCLUDED_ITER_MACROS // local macro, see bottom of file
Chris@16: #include <boost/graph/iteration_macros.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost {
Chris@16:   
Chris@16:   // Default print_callback
Chris@16:   template <typename Graph1,
Chris@16:             typename Graph2>
Chris@16:   struct vf2_print_callback {
Chris@16:     
Chris@16:     vf2_print_callback(const Graph1& graph1, const Graph2& graph2) 
Chris@16:       : graph1_(graph1), graph2_(graph2) {}
Chris@16:     
Chris@16:     template <typename CorrespondenceMap1To2,
Chris@16:               typename CorrespondenceMap2To1>
Chris@16:     bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {
Chris@16:       
Chris@16:       // Print (sub)graph isomorphism map
Chris@16:       BGL_FORALL_VERTICES_T(v, graph1_, Graph1) 
Chris@16:         std::cout << '(' << get(vertex_index_t(), graph1_, v) << ", " 
Chris@16:                   << get(vertex_index_t(), graph2_, get(f, v)) << ") ";
Chris@16:       
Chris@16:       std::cout << std::endl;
Chris@16:       
Chris@16:       return true;
Chris@16:     }
Chris@16:     
Chris@16:   private:
Chris@16:     const Graph1& graph1_;
Chris@16:     const Graph2& graph2_;
Chris@16:   };
Chris@16:   
Chris@16:   namespace detail {
Chris@16:     
Chris@16:     // State associated with a single graph (graph_this)
Chris@16:     template<typename GraphThis,
Chris@16:              typename GraphOther,
Chris@16:              typename IndexMapThis,
Chris@16:              typename IndexMapOther>
Chris@16:     class base_state {
Chris@16:       
Chris@16:       typedef typename graph_traits<GraphThis>::vertex_descriptor vertex_this_type;
Chris@16:       typedef typename graph_traits<GraphOther>::vertex_descriptor vertex_other_type;
Chris@16:       
Chris@16:       typedef typename graph_traits<GraphThis>::vertices_size_type size_type;
Chris@16:       
Chris@16:       const GraphThis& graph_this_;
Chris@16:       const GraphOther& graph_other_;
Chris@16:       
Chris@16:       IndexMapThis index_map_this_;
Chris@16:       IndexMapOther index_map_other_;
Chris@16:       
Chris@16:       std::vector<vertex_other_type> core_vec_;
Chris@16:       typedef iterator_property_map<typename std::vector<vertex_other_type>::iterator,
Chris@16:                                     IndexMapThis, vertex_other_type, 
Chris@16:                                     vertex_other_type&> core_map_type;
Chris@16:       core_map_type core_;
Chris@16:     
Chris@16:       std::vector<size_type> in_vec_, out_vec_;
Chris@16:       typedef iterator_property_map<typename std::vector<size_type>::iterator,
Chris@16:                                     IndexMapThis, size_type, size_type&> in_out_map_type;
Chris@16:       in_out_map_type in_, out_;
Chris@16: 
Chris@16:       size_type term_in_count_, term_out_count_, term_both_count_, core_count_;
Chris@16: 
Chris@16:       // Forbidden 
Chris@16:       base_state(const base_state&);
Chris@16:       base_state& operator=(const base_state&);
Chris@16: 
Chris@16:     public:
Chris@16: 
Chris@16:       base_state(const GraphThis& graph_this, const GraphOther& graph_other,
Chris@16:                  IndexMapThis index_map_this, IndexMapOther index_map_other)
Chris@16:         : graph_this_(graph_this), graph_other_(graph_other), 
Chris@16:           index_map_this_(index_map_this), index_map_other_(index_map_other), 
Chris@16:           term_in_count_(0), term_out_count_(0), term_both_count_(0), core_count_(0) {
Chris@16: 
Chris@16:         core_vec_.resize(num_vertices(graph_this_), graph_traits<GraphOther>::null_vertex());
Chris@16:         core_ = make_iterator_property_map(core_vec_.begin(), index_map_this_);
Chris@16: 
Chris@16:         in_vec_.resize(num_vertices(graph_this_), 0);
Chris@16:         in_ = make_iterator_property_map(in_vec_.begin(), index_map_this_);
Chris@16: 
Chris@16:         out_vec_.resize(num_vertices(graph_this_), 0);
Chris@16:         out_ = make_iterator_property_map(out_vec_.begin(), index_map_this_);
Chris@16:       }
Chris@16: 
Chris@16:       // Adds a vertex pair to the state of graph graph_this
Chris@16:       void push(const vertex_this_type& v_this, const vertex_other_type& v_other) {
Chris@16: 
Chris@16:         ++core_count_;
Chris@16: 
Chris@16:         put(core_, v_this, v_other);
Chris@16: 
Chris@16:         if (!get(in_, v_this)) {   
Chris@16:           put(in_, v_this, core_count_);
Chris@16:           ++term_in_count_;
Chris@16:           if (get(out_, v_this))
Chris@16:             ++term_both_count_;
Chris@16:         }
Chris@16: 
Chris@16:         if (!get(out_, v_this)) {   
Chris@16:           put(out_, v_this, core_count_);
Chris@16:           ++term_out_count_;
Chris@16:           if (get(in_, v_this))
Chris@16:             ++term_both_count_;
Chris@16:         }
Chris@16: 
Chris@16:         BGL_FORALL_INEDGES_T(v_this, e, graph_this_, GraphThis) {
Chris@16:           vertex_this_type w = source(e, graph_this_);
Chris@16:           if (!get(in_, w)) {
Chris@16:             put(in_, w, core_count_);
Chris@16:             ++term_in_count_;
Chris@16:             if (get(out_, w))
Chris@16:               ++term_both_count_;
Chris@16:           }
Chris@16:         }
Chris@16:         
Chris@16:         BGL_FORALL_OUTEDGES_T(v_this, e, graph_this_, GraphThis) {
Chris@16:           vertex_this_type w = target(e, graph_this_);
Chris@16:           if (!get(out_, w)) {
Chris@16:             put(out_, w, core_count_);
Chris@16:             ++term_out_count_;
Chris@16:             if (get(in_, w))
Chris@16:               ++term_both_count_;                        
Chris@16:           }
Chris@16:         }
Chris@16:         
Chris@16:       }
Chris@16: 
Chris@16:       // Removes vertex pair from state of graph_this
Chris@16:       void pop(const vertex_this_type& v_this, const vertex_other_type&) {
Chris@16:         
Chris@16:         if (!core_count_) return;
Chris@16:         
Chris@16:         if (get(in_, v_this) == core_count_) {
Chris@16:           put(in_, v_this, 0);
Chris@16:           --term_in_count_;
Chris@16:           if (get(out_, v_this))
Chris@16:             --term_both_count_;
Chris@16:         }
Chris@16: 
Chris@16:         BGL_FORALL_INEDGES_T(v_this, e, graph_this_, GraphThis) {
Chris@16:           vertex_this_type w = source(e, graph_this_);
Chris@16:           if (get(in_, w) == core_count_) {
Chris@16:             put(in_, w, 0);
Chris@16:             --term_in_count_;
Chris@16:             if (get(out_, w))
Chris@16:               --term_both_count_;
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:         if (get(out_, v_this) == core_count_) {
Chris@16:           put(out_, v_this, 0);
Chris@16:           --term_out_count_;
Chris@16:           if (get(in_, v_this))
Chris@16:             --term_both_count_;
Chris@16:         }
Chris@16: 
Chris@16:         BGL_FORALL_OUTEDGES_T(v_this, e, graph_this_, GraphThis) {
Chris@16:           vertex_this_type w = target(e, graph_this_);
Chris@16:           if (get(out_, w) == core_count_) {
Chris@16:             put(out_, w, 0);
Chris@16:             --term_out_count_;
Chris@16:             if (get(in_, w))
Chris@16:               --term_both_count_;
Chris@16:           }
Chris@16:         }
Chris@16:         put(core_, v_this, graph_traits<GraphOther>::null_vertex());
Chris@16: 
Chris@16:         --core_count_;
Chris@16:         
Chris@16:       }
Chris@16:             
Chris@16:       // Returns true if the in-terminal set is not empty  
Chris@16:       bool term_in() const {
Chris@16:         return core_count_ < term_in_count_ ;
Chris@16:       }
Chris@16: 
Chris@16:       // Returns true if vertex belongs to the in-terminal set
Chris@16:       bool term_in(const vertex_this_type& v) const {
Chris@16:         return (get(in_, v) > 0) &&
Chris@16:                (get(core_, v) == graph_traits<GraphOther>::null_vertex());
Chris@16:       }
Chris@16:             
Chris@16:       // Returns true if the out-terminal set is not empty  
Chris@16:       bool term_out() const {
Chris@16:         return core_count_ < term_out_count_;
Chris@16:       }
Chris@16: 
Chris@16:       // Returns true if vertex belongs to the out-terminal set
Chris@16:       bool term_out(const vertex_this_type& v) const {
Chris@16:         return (get(out_, v) > 0) && 
Chris@16:                (get(core_, v) == graph_traits<GraphOther>::null_vertex());
Chris@16:       }
Chris@16: 
Chris@16:       // Returns true of both (in- and out-terminal) sets are not empty
Chris@16:       bool term_both() const {
Chris@16:         return core_count_ < term_both_count_;
Chris@16:       }
Chris@16: 
Chris@16:       // Returns true if vertex belongs to both (in- and out-terminal) sets
Chris@16:       bool term_both(const vertex_this_type& v) const {
Chris@16:         return (get(in_, v) > 0) && (get(out_, v) > 0) && 
Chris@16:                (get(core_, v) == graph_traits<GraphOther>::null_vertex());
Chris@16:       }
Chris@16: 
Chris@16:       // Returns true if vertex belongs to the core map, i.e. it is in the 
Chris@16:       // present mapping
Chris@16:       bool in_core(const vertex_this_type& v) const {
Chris@16:         return get(core_, v) != graph_traits<GraphOther>::null_vertex();
Chris@16:       }
Chris@16: 
Chris@16:       // Returns the number of vertices in the mapping
Chris@16:       size_type count() const {
Chris@16:         return core_count_;
Chris@16:       }            
Chris@16: 
Chris@16:       // Returns the image (in graph_other) of vertex v (in graph_this)
Chris@16:       vertex_other_type core(const vertex_this_type& v) const {
Chris@16:         return get(core_, v);
Chris@16:       }
Chris@16: 
Chris@16:       // Returns the mapping
Chris@16:       core_map_type get_map() const {
Chris@16:         return core_;
Chris@16:       }
Chris@16: 
Chris@16:       // Returns the "time" (or depth) when vertex was added to the in-terminal set
Chris@16:       size_type in_depth(const vertex_this_type& v) const {
Chris@16:         return get(in_, v);
Chris@16:       }
Chris@16: 
Chris@16:       // Returns the "time" (or depth) when vertex was added to the out-terminal set
Chris@16:       size_type out_depth(const vertex_this_type& v) const {
Chris@16:         return get(out_, v);
Chris@16:       }            
Chris@16: 
Chris@16:       // Returns the terminal set counts
Chris@16:       boost::tuple<size_type, size_type, size_type>
Chris@16:       term_set() const {
Chris@16:         return boost::make_tuple(term_in_count_, term_out_count_, 
Chris@16:                                  term_both_count_);
Chris@16:       }
Chris@16:       
Chris@16:     };
Chris@16: 
Chris@16: 
Chris@16:     // Function object that checks whether a valid edge
Chris@16:     // exists. For multi-graphs matched edges are excluded  
Chris@16:     template <typename Graph, typename Enable = void>
Chris@16:     struct equivalent_edge_exists {
Chris@16:       typedef typename boost::graph_traits<Graph>::edge_descriptor edge_type;
Chris@16: 
Chris@16:       BOOST_CONCEPT_ASSERT(( LessThanComparable<edge_type> ));
Chris@16: 
Chris@16:       template<typename EdgePredicate>
Chris@16:       bool operator()(typename graph_traits<Graph>::vertex_descriptor s,
Chris@16:                       typename graph_traits<Graph>::vertex_descriptor t, 
Chris@16:                       EdgePredicate is_valid_edge, const Graph& g) {
Chris@16:         
Chris@16:         BGL_FORALL_OUTEDGES_T(s, e, g, Graph) {
Chris@16:           if ((target(e, g) == t) && is_valid_edge(e) && 
Chris@16:               (matched_edges_.find(e) == matched_edges_.end())) {
Chris@16:             matched_edges_.insert(e);
Chris@16:             return true;
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:         return false;
Chris@16:       }
Chris@16: 
Chris@16:     private:
Chris@16:       
Chris@16:       std::set<edge_type> matched_edges_;
Chris@16:     };
Chris@16:     
Chris@16:     template <typename Graph>
Chris@16:     struct equivalent_edge_exists<Graph, typename boost::disable_if<is_multigraph<Graph> >::type> {
Chris@16:       template<typename EdgePredicate>
Chris@16:       bool operator()(typename graph_traits<Graph>::vertex_descriptor s,
Chris@16:                       typename graph_traits<Graph>::vertex_descriptor t, 
Chris@16:                       EdgePredicate is_valid_edge, const Graph& g) {
Chris@16:         
Chris@16:         typename graph_traits<Graph>::edge_descriptor e;
Chris@16:         bool found;
Chris@16:         boost::tie(e, found) = edge(s, t, g);
Chris@16:         if (!found)
Chris@16:           return false;
Chris@16:         else if (is_valid_edge(e))
Chris@16:           return true;
Chris@16:         
Chris@16:         return false;
Chris@16:       }
Chris@16:       
Chris@16:     };
Chris@16: 
Chris@16: 
Chris@16:     // Generates a predicate for edge e1 given  a binary predicate and a 
Chris@16:     // fixed edge e2
Chris@16:     template <typename Graph1,
Chris@16:               typename Graph2,
Chris@16:               typename EdgeEquivalencePredicate>
Chris@16:     struct edge1_predicate {
Chris@16:       
Chris@16:       edge1_predicate(EdgeEquivalencePredicate edge_comp, 
Chris@16:                       typename graph_traits<Graph2>::edge_descriptor e2)
Chris@16:         : edge_comp_(edge_comp), e2_(e2) {}
Chris@16:       
Chris@16:       bool operator()(typename graph_traits<Graph1>::edge_descriptor e1) {
Chris@16:         return edge_comp_(e1, e2_);
Chris@16:       }
Chris@16: 
Chris@16:       EdgeEquivalencePredicate edge_comp_;
Chris@16:       typename graph_traits<Graph2>::edge_descriptor e2_;
Chris@16:     };
Chris@16: 
Chris@16: 
Chris@16:     // Generates a predicate for edge e2 given given a binary predicate and a
Chris@16:     // fixed edge e1
Chris@16:     template <typename Graph1,
Chris@16:               typename Graph2,
Chris@16:               typename EdgeEquivalencePredicate>
Chris@16:     struct edge2_predicate {
Chris@16:       
Chris@16:       edge2_predicate(EdgeEquivalencePredicate edge_comp, 
Chris@16:                       typename graph_traits<Graph1>::edge_descriptor e1)
Chris@16:         : edge_comp_(edge_comp), e1_(e1) {}
Chris@16: 
Chris@16:       bool operator()(typename graph_traits<Graph2>::edge_descriptor e2) {
Chris@16:         return edge_comp_(e1_, e2);
Chris@16:       }
Chris@16: 
Chris@16:       EdgeEquivalencePredicate edge_comp_;
Chris@16:       typename graph_traits<Graph1>::edge_descriptor e1_;
Chris@16:     };
Chris@16: 
Chris@16: 
Chris@16:     enum problem_selector {subgraph_mono, subgraph_iso, isomorphism };
Chris@16:     
Chris@16:     // The actual state associated with both graphs
Chris@16:     template<typename Graph1,
Chris@16:              typename Graph2,
Chris@16:              typename IndexMap1,
Chris@16:              typename IndexMap2,
Chris@16:              typename EdgeEquivalencePredicate,
Chris@16:              typename VertexEquivalencePredicate,
Chris@16:              typename SubGraphIsoMapCallback,
Chris@16:              problem_selector problem_selection>
Chris@16:     class state {
Chris@16: 
Chris@16:       typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_type;
Chris@16:       typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_type;
Chris@16: 
Chris@16:       typedef typename graph_traits<Graph1>::edge_descriptor edge1_type;
Chris@16:       typedef typename graph_traits<Graph2>::edge_descriptor edge2_type;
Chris@16: 
Chris@16:       typedef typename graph_traits<Graph1>::vertices_size_type graph1_size_type;
Chris@16:       typedef typename graph_traits<Graph2>::vertices_size_type graph2_size_type;
Chris@16: 
Chris@16:       const Graph1& graph1_;
Chris@16:       const Graph2& graph2_;
Chris@16:       
Chris@16:       IndexMap1 index_map1_;
Chris@16:       
Chris@16:       EdgeEquivalencePredicate edge_comp_;
Chris@16:       VertexEquivalencePredicate vertex_comp_;
Chris@16:                 
Chris@16:       base_state<Graph1, Graph2, IndexMap1, IndexMap2> state1_;
Chris@16:       base_state<Graph2, Graph1, IndexMap2, IndexMap1> state2_;
Chris@16: 
Chris@16:       // Three helper functions used in Feasibility and Valid functions to test
Chris@16:       // terminal set counts when testing for:
Chris@16:       // - graph sub-graph monomorphism, or
Chris@16:       inline bool comp_term_sets(graph1_size_type a, 
Chris@16:                                  graph2_size_type b,
Chris@16:                                  boost::mpl::int_<subgraph_mono>) const {
Chris@16:         return a <= b;
Chris@16:       }
Chris@16: 
Chris@16:       // - graph sub-graph isomorphism, or
Chris@16:       inline bool comp_term_sets(graph1_size_type a, 
Chris@16:                                  graph2_size_type b,
Chris@16:                                  boost::mpl::int_<subgraph_iso>) const {
Chris@16:         return a <= b;
Chris@16:       }
Chris@16: 
Chris@16:       // - graph isomorphism
Chris@16:       inline bool comp_term_sets(graph1_size_type a, 
Chris@16:                                  graph2_size_type b,
Chris@16:                                  boost::mpl::int_<isomorphism>) const {
Chris@16:         return a == b;
Chris@16:       }
Chris@16:       
Chris@16:       // Forbidden 
Chris@16:       state(const state&);
Chris@16:       state& operator=(const state&);
Chris@16: 
Chris@16:     public:
Chris@16: 
Chris@16:       state(const Graph1& graph1, const Graph2& graph2, 
Chris@16:             IndexMap1 index_map1, IndexMap2 index_map2, 
Chris@16:             EdgeEquivalencePredicate edge_comp,
Chris@16:             VertexEquivalencePredicate vertex_comp)
Chris@16:         : graph1_(graph1), graph2_(graph2), 
Chris@16:           index_map1_(index_map1), 
Chris@16:           edge_comp_(edge_comp), vertex_comp_(vertex_comp),
Chris@16:           state1_(graph1, graph2, index_map1, index_map2), 
Chris@16:           state2_(graph2, graph1, index_map2, index_map1) {}
Chris@16:       
Chris@16:             // Add vertex pair to the state
Chris@16:       void push(const vertex1_type& v, const vertex2_type& w) {
Chris@16:         state1_.push(v, w);
Chris@16:         state2_.push(w, v);
Chris@16:       }
Chris@16:       
Chris@16:       // Remove vertex pair from state
Chris@16:       void pop(const vertex1_type& v, const vertex2_type&) {
Chris@16:         vertex2_type w = state1_.core(v);
Chris@16:         state1_.pop(v, w);
Chris@16:         state2_.pop(w, v);
Chris@16:       }
Chris@16:            
Chris@16:       // Checks the feasibility of a new vertex pair
Chris@16:       bool feasible(const vertex1_type& v_new, const vertex2_type& w_new) {
Chris@16:         
Chris@16:         if (!vertex_comp_(v_new, w_new)) return false;
Chris@16:         
Chris@16:         // graph1
Chris@16:         graph1_size_type term_in1_count = 0, term_out1_count = 0, rest1_count = 0;
Chris@16:         
Chris@16:         {
Chris@16:           equivalent_edge_exists<Graph2> edge2_exists;
Chris@16:           
Chris@16:           BGL_FORALL_INEDGES_T(v_new, e1, graph1_, Graph1) {
Chris@16:             vertex1_type v = source(e1, graph1_);
Chris@16:             
Chris@16:             if (state1_.in_core(v) || (v == v_new)) {
Chris@16:               vertex2_type w = w_new;
Chris@16:               if (v != v_new)
Chris@16:                 w = state1_.core(v);
Chris@16:               if (!edge2_exists(w, w_new,
Chris@16:                                 edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e1), 
Chris@16:                                 graph2_))
Chris@16:                 return false;
Chris@16:               
Chris@16:             } else {
Chris@16:               if (0 < state1_.in_depth(v))
Chris@16:                 ++term_in1_count;
Chris@16:               if (0 < state1_.out_depth(v))
Chris@16:                 ++term_out1_count;
Chris@16:               if ((state1_.in_depth(v) == 0) && (state1_.out_depth(v) == 0))
Chris@16:                 ++rest1_count;
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16:         
Chris@16:         {
Chris@16:           equivalent_edge_exists<Graph2> edge2_exists;
Chris@16:           
Chris@16:           BGL_FORALL_OUTEDGES_T(v_new, e1, graph1_, Graph1) {
Chris@16:             vertex1_type v = target(e1, graph1_);
Chris@16:             if (state1_.in_core(v) || (v == v_new)) {
Chris@16:               vertex2_type w = w_new;
Chris@16:               if (v != v_new)
Chris@16:                 w = state1_.core(v);
Chris@16:               
Chris@16:               if (!edge2_exists(w_new, w,
Chris@16:                                 edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e1), 
Chris@16:                                 graph2_))
Chris@16:                 return false;
Chris@16:               
Chris@16:             } else {
Chris@16:               if (0 < state1_.in_depth(v))
Chris@16:                 ++term_in1_count;
Chris@16:               if (0 < state1_.out_depth(v))
Chris@16:                 ++term_out1_count;
Chris@16:               if ((state1_.in_depth(v) == 0) && (state1_.out_depth(v) == 0))
Chris@16:                 ++rest1_count;
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16:         
Chris@16:         // graph2
Chris@16:         graph2_size_type term_out2_count = 0, term_in2_count = 0, rest2_count = 0;
Chris@16:         
Chris@16:         {
Chris@16:           equivalent_edge_exists<Graph1> edge1_exists;
Chris@16:           
Chris@16:           BGL_FORALL_INEDGES_T(w_new, e2, graph2_, Graph2) {
Chris@16:             vertex2_type w = source(e2, graph2_);
Chris@16:             if (state2_.in_core(w) || (w == w_new)) {
Chris@16:               if (problem_selection != subgraph_mono) {
Chris@16:                 vertex1_type v = v_new;
Chris@16:                 if (w != w_new)
Chris@16:                   v = state2_.core(w);
Chris@16:               
Chris@16:                 if (!edge1_exists(v, v_new,
Chris@16:                                   edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2), 
Chris@16:                                   graph1_))
Chris@16:                   return false;
Chris@16:               }
Chris@16:             } else {
Chris@16:               if (0 < state2_.in_depth(w))
Chris@16:                 ++term_in2_count;
Chris@16:               if (0 < state2_.out_depth(w))
Chris@16:                 ++term_out2_count;
Chris@16:               if ((state2_.in_depth(w) == 0) && (state2_.out_depth(w) == 0))
Chris@16:                 ++rest2_count;
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:         {
Chris@16:           equivalent_edge_exists<Graph1> edge1_exists;
Chris@16:           
Chris@16:           BGL_FORALL_OUTEDGES_T(w_new, e2, graph2_, Graph2) {
Chris@16:             vertex2_type w = target(e2, graph2_);
Chris@16:             if (state2_.in_core(w) || (w == w_new)) {
Chris@16:               if (problem_selection != subgraph_mono) {
Chris@16:                 vertex1_type v = v_new;
Chris@16:                 if (w != w_new)
Chris@16:                   v = state2_.core(w);
Chris@16:               
Chris@16:                 if (!edge1_exists(v_new, v,
Chris@16:                                   edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2), 
Chris@16:                                   graph1_))
Chris@16:                   return false;
Chris@16:               }
Chris@16:             } else {
Chris@16:               if (0 < state2_.in_depth(w))
Chris@16:                 ++term_in2_count;
Chris@16:               if (0 < state2_.out_depth(w))
Chris@16:                 ++term_out2_count;
Chris@16:               if ((state2_.in_depth(w) == 0) && (state2_.out_depth(w) == 0))
Chris@16:                 ++rest2_count;
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:         if (problem_selection != subgraph_mono) { // subgraph_iso and isomorphism
Chris@16:           return comp_term_sets(term_in1_count, term_in2_count,
Chris@16:                                 boost::mpl::int_<problem_selection>()) &&
Chris@16:                  comp_term_sets(term_out1_count, term_out2_count, 
Chris@16:                                 boost::mpl::int_<problem_selection>()) &&
Chris@16:                  comp_term_sets(rest1_count, rest2_count, 
Chris@16:                                 boost::mpl::int_<problem_selection>());
Chris@16:         } else { // subgraph_mono
Chris@16:           return comp_term_sets(term_in1_count, term_in2_count,
Chris@16:                                 boost::mpl::int_<problem_selection>()) &&
Chris@16:                  comp_term_sets(term_out1_count, term_out2_count, 
Chris@16:                                 boost::mpl::int_<problem_selection>()) &&
Chris@16:                  comp_term_sets(term_in1_count + term_out1_count + rest1_count,
Chris@16:                                 term_in2_count + term_out2_count + rest2_count, 
Chris@16:                                 boost::mpl::int_<problem_selection>());
Chris@16:         }
Chris@16:       }
Chris@16:       
Chris@16:       // Returns true if vertex v in graph1 is a possible candidate to
Chris@16:       // be added to the current state
Chris@16:       bool possible_candidate1(const vertex1_type& v) const {
Chris@16:         if (state1_.term_both() && state2_.term_both()) 
Chris@16:           return state1_.term_both(v);
Chris@16:         else if (state1_.term_out() && state2_.term_out())
Chris@16:           return state1_.term_out(v);
Chris@16:         else if (state1_.term_in() && state2_.term_in())
Chris@16:           return state1_.term_in(v);
Chris@16:         else
Chris@16:           return !state1_.in_core(v);
Chris@16:       }
Chris@16: 
Chris@16:       // Returns true if vertex w in graph2 is a possible candidate to
Chris@16:       // be added to the current state
Chris@16:       bool possible_candidate2(const vertex2_type& w) const {
Chris@16:         if (state1_.term_both() && state2_.term_both()) 
Chris@16:           return state2_.term_both(w);
Chris@16:         else if (state1_.term_out() && state2_.term_out())
Chris@16:           return state2_.term_out(w);
Chris@16:         else if (state1_.term_in() && state2_.term_in())
Chris@16:           return state2_.term_in(w);
Chris@16:         else
Chris@16:           return !state2_.in_core(w);
Chris@16:       }
Chris@16: 
Chris@16:       // Returns true if a mapping was found
Chris@16:       bool success() const {
Chris@16:         return state1_.count() == num_vertices(graph1_);
Chris@16:       }
Chris@16:  
Chris@16:       // Returns true if a state is valid
Chris@16:       bool valid() const {
Chris@16:         boost::tuple<graph1_size_type, graph1_size_type, graph1_size_type> term1;
Chris@16:         boost::tuple<graph2_size_type, graph2_size_type, graph2_size_type> term2;
Chris@16:         
Chris@16:         term1 = state1_.term_set();
Chris@16:         term2 = state2_.term_set();
Chris@16:         
Chris@16:         return comp_term_sets(boost::get<0>(term1), boost::get<0>(term2),
Chris@16:                               boost::mpl::int_<problem_selection>()) &&
Chris@16:                comp_term_sets(boost::get<1>(term1), boost::get<1>(term2),
Chris@16:                               boost::mpl::int_<problem_selection>()) &&
Chris@16:                comp_term_sets(boost::get<2>(term1), boost::get<2>(term2),
Chris@16:                               boost::mpl::int_<problem_selection>()); 
Chris@16:       }
Chris@16:       
Chris@16:       // Calls the user_callback with a graph (sub)graph mapping 
Chris@16:       bool call_back(SubGraphIsoMapCallback user_callback) const {
Chris@16:         return user_callback(state1_.get_map(), state2_.get_map());
Chris@16:       }
Chris@16:       
Chris@16:     };
Chris@16: 
Chris@16:     
Chris@16:     // Data structure to keep info used for back tracking during
Chris@16:     // matching process
Chris@16:     template<typename Graph1,
Chris@16:              typename Graph2,
Chris@16:              typename VertexOrder1>
Chris@16:     struct vf2_match_continuation {
Chris@16:       typename VertexOrder1::const_iterator graph1_verts_iter;
Chris@16:       typename graph_traits<Graph2>::vertex_iterator graph2_verts_iter;
Chris@16:     };
Chris@16: 
Chris@16:     // Non-recursive method that explores state space using a depth-first
Chris@16:     // search strategy.  At each depth possible pairs candidate are compute
Chris@16:     // and tested for feasibility to extend the mapping. If a complete
Chris@16:     // mapping is found, the mapping is output to user_callback in the form
Chris@16:     // of a correspondence map (graph1 to graph2). Returning false from the
Chris@16:     // user_callback will terminate the search. Function match will return
Chris@16:     // true if the entire search space was explored.
Chris@16:     template<typename Graph1,
Chris@16:              typename Graph2,
Chris@16:              typename IndexMap1,
Chris@16:              typename IndexMap2,
Chris@16:              typename VertexOrder1,
Chris@16:              typename EdgeEquivalencePredicate,
Chris@16:              typename VertexEquivalencePredicate, 
Chris@16:              typename SubGraphIsoMapCallback,
Chris@16:              problem_selector problem_selection>
Chris@16:     bool match(const Graph1& graph1, const Graph2& graph2, 
Chris@16:                SubGraphIsoMapCallback user_callback, const VertexOrder1& vertex_order1, 
Chris@16:                state<Graph1, Graph2, IndexMap1, IndexMap2,
Chris@16:                EdgeEquivalencePredicate, VertexEquivalencePredicate,
Chris@16:                SubGraphIsoMapCallback, problem_selection>& s) {
Chris@16:       
Chris@16:       typename VertexOrder1::const_iterator graph1_verts_iter;
Chris@16: 
Chris@16:       typedef typename graph_traits<Graph2>::vertex_iterator vertex2_iterator_type;
Chris@16:       vertex2_iterator_type graph2_verts_iter, graph2_verts_iter_end;
Chris@16:     
Chris@16:       typedef vf2_match_continuation<Graph1, Graph2, VertexOrder1> match_continuation_type;
Chris@16:       std::vector<match_continuation_type> k;
Chris@101:       bool found_match = false;
Chris@16:   
Chris@16:       recur:
Chris@16:       if (s.success()) {
Chris@16:         if (!s.call_back(user_callback)) 
Chris@101:           return true;
Chris@101:         found_match = true;
Chris@16: 
Chris@16:         goto back_track;
Chris@16:       }
Chris@16:  
Chris@16:       if (!s.valid())
Chris@16:         goto back_track;
Chris@16: 
Chris@16:       graph1_verts_iter = vertex_order1.begin();
Chris@16:       while (graph1_verts_iter != vertex_order1.end() && 
Chris@16:              !s.possible_candidate1(*graph1_verts_iter)) {
Chris@16:         ++graph1_verts_iter;
Chris@16:       }
Chris@16: 
Chris@16:       boost::tie(graph2_verts_iter, graph2_verts_iter_end) = vertices(graph2);
Chris@16:       while (graph2_verts_iter != graph2_verts_iter_end) {
Chris@16:         if (s.possible_candidate2(*graph2_verts_iter)) {
Chris@16:           if (s.feasible(*graph1_verts_iter, *graph2_verts_iter)) {
Chris@16:             match_continuation_type kk;
Chris@16:             kk.graph1_verts_iter = graph1_verts_iter;
Chris@16:             kk.graph2_verts_iter = graph2_verts_iter;
Chris@16:             k.push_back(kk);
Chris@16:             
Chris@16:             s.push(*graph1_verts_iter, *graph2_verts_iter);
Chris@16:             goto recur;
Chris@16:           }
Chris@16:         }
Chris@16:         graph2_loop: ++graph2_verts_iter;
Chris@16:       }
Chris@16: 
Chris@16:       back_track:
Chris@16:       if (k.empty()) 
Chris@101:         return found_match;    
Chris@16:       
Chris@16:       const match_continuation_type kk = k.back();
Chris@16:       graph1_verts_iter = kk.graph1_verts_iter;
Chris@16:       graph2_verts_iter = kk.graph2_verts_iter;
Chris@16:       k.pop_back();
Chris@16:       
Chris@16:       s.pop(*graph1_verts_iter, *graph2_verts_iter);
Chris@16:       
Chris@16:       goto graph2_loop;
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     // Used to sort nodes by in/out degrees
Chris@16:     template<typename Graph>
Chris@16:     struct vertex_in_out_degree_cmp {
Chris@16:       typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
Chris@16: 
Chris@16:       vertex_in_out_degree_cmp(const Graph& graph)
Chris@16:         : graph_(graph) {}
Chris@16: 
Chris@16:       bool operator()(const vertex_type& v, const vertex_type& w) const {
Chris@16:         // lexicographical comparison
Chris@16:         return std::make_pair(in_degree(v, graph_), out_degree(v, graph_)) <
Chris@16:                std::make_pair(in_degree(w, graph_), out_degree(w, graph_));
Chris@16:       }
Chris@16: 
Chris@16:       const Graph& graph_;
Chris@16:     };
Chris@16: 
Chris@16: 
Chris@16:     // Used to sort nodes by multiplicity of in/out degrees
Chris@16:     template<typename Graph,
Chris@16:              typename FrequencyMap>
Chris@16:     struct vertex_frequency_degree_cmp {
Chris@16:       typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
Chris@16:       
Chris@16:       vertex_frequency_degree_cmp(const Graph& graph, FrequencyMap freq)
Chris@16:         : graph_(graph), freq_(freq) {}
Chris@16:       
Chris@16:       bool operator()(const vertex_type& v, const vertex_type& w) const {
Chris@16:         // lexicographical comparison
Chris@16:         return std::make_pair(freq_[v], in_degree(v, graph_)+out_degree(v, graph_)) <
Chris@16:                std::make_pair(freq_[w], in_degree(w, graph_)+out_degree(w, graph_));
Chris@16:       }
Chris@16: 
Chris@16:       const Graph& graph_;
Chris@16:       FrequencyMap freq_;
Chris@16:     };
Chris@16: 
Chris@16:     
Chris@16:     // Sorts vertices of a graph by multiplicity of in/out degrees 
Chris@16:     template<typename Graph,
Chris@16:              typename IndexMap,
Chris@16:              typename VertexOrder>
Chris@16:     void sort_vertices(const Graph& graph, IndexMap index_map, VertexOrder& order) {
Chris@16:       typedef typename graph_traits<Graph>::vertices_size_type size_type;
Chris@16: 
Chris@16:       boost::range::sort(order, vertex_in_out_degree_cmp<Graph>(graph));
Chris@16: 
Chris@16:       std::vector<size_type> freq_vec(num_vertices(graph), 0);
Chris@16:       typedef iterator_property_map<typename std::vector<size_type>::iterator,
Chris@16:                                     IndexMap, size_type, size_type&> frequency_map_type;
Chris@16:                 
Chris@16:       frequency_map_type freq = make_iterator_property_map(freq_vec.begin(), index_map);
Chris@16: 
Chris@16:       typedef typename VertexOrder::iterator order_iterator;
Chris@16: 
Chris@16:       for (order_iterator order_iter = order.begin(); order_iter != order.end(); ) {
Chris@16:         size_type count = 0;
Chris@16:         for (order_iterator count_iter = order_iter;
Chris@16:              (count_iter != order.end()) &&
Chris@16:              (in_degree(*order_iter, graph) == in_degree(*count_iter, graph)) &&
Chris@16:              (out_degree(*order_iter, graph) == out_degree(*count_iter, graph)); 
Chris@16:              ++count_iter)
Chris@16:           ++count;
Chris@16:       
Chris@16:         for (size_type i = 0; i < count; ++i) {
Chris@16:           freq[*order_iter] = count;
Chris@16:           ++order_iter;
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       boost::range::sort(order, vertex_frequency_degree_cmp<Graph, frequency_map_type>(graph, freq));
Chris@16: 
Chris@16:     }
Chris@16: 
Chris@16:     // Enumerates all graph sub-graph mono-/iso-morphism mappings between graphs
Chris@16:     // graph_small and graph_large. Continues until user_callback returns true or the
Chris@16:     // search space has been fully explored.
Chris@16:     template <problem_selector problem_selection,
Chris@16:               typename GraphSmall,
Chris@16:               typename GraphLarge,
Chris@16:               typename IndexMapSmall,
Chris@16:               typename IndexMapLarge,
Chris@16:               typename VertexOrderSmall,
Chris@16:               typename EdgeEquivalencePredicate,
Chris@16:               typename VertexEquivalencePredicate,
Chris@16:               typename SubGraphIsoMapCallback>
Chris@16:     bool vf2_subgraph_morphism(const GraphSmall& graph_small, const GraphLarge& graph_large,
Chris@16:                           SubGraphIsoMapCallback user_callback,
Chris@16:                           IndexMapSmall index_map_small, IndexMapLarge index_map_large, 
Chris@16:                           const VertexOrderSmall& vertex_order_small,
Chris@16:                           EdgeEquivalencePredicate edge_comp,
Chris@16:                           VertexEquivalencePredicate vertex_comp) {
Chris@16: 
Chris@16:       // Graph requirements
Chris@16:       BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<GraphSmall> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<GraphSmall> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<GraphSmall> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<GraphSmall> ));
Chris@16: 
Chris@16:       BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<GraphLarge> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<GraphLarge> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<GraphLarge> ));
Chris@16:       BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<GraphLarge> ));
Chris@16: 
Chris@16:       typedef typename graph_traits<GraphSmall>::vertex_descriptor vertex_small_type;
Chris@16:       typedef typename graph_traits<GraphLarge>::vertex_descriptor vertex_large_type;
Chris@16: 
Chris@16:       typedef typename graph_traits<GraphSmall>::vertices_size_type size_type_small;
Chris@16:       typedef typename graph_traits<GraphLarge>::vertices_size_type size_type_large;
Chris@16:         
Chris@16:       // Property map requirements
Chris@16:       BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMapSmall, vertex_small_type> ));
Chris@16:       typedef typename property_traits<IndexMapSmall>::value_type IndexMapSmallValue;
Chris@16:       BOOST_STATIC_ASSERT(( is_convertible<IndexMapSmallValue, size_type_small>::value ));
Chris@16:         
Chris@16:       BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMapLarge, vertex_large_type> ));
Chris@16:       typedef typename property_traits<IndexMapLarge>::value_type IndexMapLargeValue;
Chris@16:       BOOST_STATIC_ASSERT(( is_convertible<IndexMapLargeValue, size_type_large>::value ));
Chris@16: 
Chris@16:       // Edge & vertex requirements
Chris@16:       typedef typename graph_traits<GraphSmall>::edge_descriptor edge_small_type;
Chris@16:       typedef typename graph_traits<GraphLarge>::edge_descriptor edge_large_type;
Chris@16: 
Chris@16:       BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeEquivalencePredicate, 
Chris@16:                              edge_small_type, edge_large_type> ));
Chris@16: 
Chris@16:       BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexEquivalencePredicate, 
Chris@16:                              vertex_small_type, vertex_large_type> ));
Chris@16: 
Chris@16:       // Vertex order requirements
Chris@16:       BOOST_CONCEPT_ASSERT(( ContainerConcept<VertexOrderSmall> )); 
Chris@16:       typedef typename VertexOrderSmall::value_type order_value_type;
Chris@16:       BOOST_STATIC_ASSERT(( is_same<vertex_small_type, order_value_type>::value ));
Chris@16:       BOOST_ASSERT( num_vertices(graph_small) == vertex_order_small.size() );
Chris@16: 
Chris@16:       if (num_vertices(graph_small) > num_vertices(graph_large))
Chris@16:         return false;
Chris@16: 
Chris@16:       typename graph_traits<GraphSmall>::edges_size_type num_edges_small = num_edges(graph_small);
Chris@16:       typename graph_traits<GraphLarge>::edges_size_type num_edges_large = num_edges(graph_large);
Chris@16: 
Chris@16:       // Double the number of edges for undirected graphs: each edge counts as
Chris@16:       // in-edge and out-edge
Chris@16:       if (is_undirected(graph_small)) num_edges_small *= 2;
Chris@16:       if (is_undirected(graph_large)) num_edges_large *= 2;
Chris@16:       if (num_edges_small > num_edges_large)
Chris@16:         return false;
Chris@16:     
Chris@16:       detail::state<GraphSmall, GraphLarge, IndexMapSmall, IndexMapLarge,
Chris@16:                     EdgeEquivalencePredicate, VertexEquivalencePredicate,
Chris@16:                     SubGraphIsoMapCallback, problem_selection> 
Chris@16:         s(graph_small, graph_large, index_map_small, index_map_large, edge_comp, vertex_comp);
Chris@16: 
Chris@16:       return detail::match(graph_small, graph_large, user_callback, vertex_order_small, s);
Chris@16:     }
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16: 
Chris@16:   // Returns vertex order (vertices sorted by multiplicity of in/out degrees)
Chris@16:   template<typename Graph>
Chris@16:   std::vector<typename graph_traits<Graph>::vertex_descriptor> 
Chris@16:     vertex_order_by_mult(const Graph& graph) {
Chris@16: 
Chris@16:     std::vector<typename graph_traits<Graph>::vertex_descriptor> vertex_order;
Chris@16:     std::copy(vertices(graph).first, vertices(graph).second, std::back_inserter(vertex_order));
Chris@16: 
Chris@16:     detail::sort_vertices(graph, get(vertex_index, graph), vertex_order);
Chris@16:     return vertex_order;
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // Enumerates all graph sub-graph monomorphism mappings between graphs
Chris@16:   // graph_small and graph_large. Continues until user_callback returns true or the
Chris@16:   // search space has been fully explored.
Chris@16:   template <typename GraphSmall,
Chris@16:             typename GraphLarge,
Chris@16:             typename IndexMapSmall,
Chris@16:             typename IndexMapLarge,
Chris@16:             typename VertexOrderSmall,
Chris@16:             typename EdgeEquivalencePredicate,
Chris@16:             typename VertexEquivalencePredicate,
Chris@16:             typename SubGraphIsoMapCallback>
Chris@16:   bool vf2_subgraph_mono(const GraphSmall& graph_small, const GraphLarge& graph_large,
Chris@16:                          SubGraphIsoMapCallback user_callback,
Chris@16:                          IndexMapSmall index_map_small, IndexMapLarge index_map_large, 
Chris@16:                          const VertexOrderSmall& vertex_order_small,
Chris@16:                          EdgeEquivalencePredicate edge_comp,
Chris@16:                          VertexEquivalencePredicate vertex_comp) {
Chris@16:     return detail::vf2_subgraph_morphism<detail::subgraph_mono>
Chris@16:                                         (graph_small, graph_large,
Chris@16:                                          user_callback,
Chris@16:                                          index_map_small, index_map_large,
Chris@16:                                          vertex_order_small,
Chris@16:                                          edge_comp,
Chris@16:                                          vertex_comp);
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // All default interface for vf2_subgraph_iso
Chris@16:   template <typename GraphSmall,
Chris@16:             typename GraphLarge,
Chris@16:             typename SubGraphIsoMapCallback>
Chris@16:   bool vf2_subgraph_mono(const GraphSmall& graph_small, const GraphLarge& graph_large, 
Chris@16:                          SubGraphIsoMapCallback user_callback) {
Chris@16:     return vf2_subgraph_mono(graph_small, graph_large, user_callback, 
Chris@16:                              get(vertex_index, graph_small), get(vertex_index, graph_large),
Chris@16:                              vertex_order_by_mult(graph_small),
Chris@16:                              always_equivalent(), always_equivalent());
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // Named parameter interface of vf2_subgraph_iso
Chris@16:   template <typename GraphSmall,
Chris@16:             typename GraphLarge,
Chris@16:             typename VertexOrderSmall,
Chris@16:             typename SubGraphIsoMapCallback,
Chris@16:             typename Param,
Chris@16:             typename Tag,
Chris@16:             typename Rest>
Chris@16:   bool vf2_subgraph_mono(const GraphSmall& graph_small, const GraphLarge& graph_large,
Chris@16:                          SubGraphIsoMapCallback user_callback,
Chris@16:                          const VertexOrderSmall& vertex_order_small,
Chris@16:                          const bgl_named_params<Param, Tag, Rest>& params) {
Chris@16:     return vf2_subgraph_mono(graph_small, graph_large, user_callback,
Chris@16:                              choose_const_pmap(get_param(params, vertex_index1),
Chris@16:                                                graph_small, vertex_index),
Chris@16:                              choose_const_pmap(get_param(params, vertex_index2),
Chris@16:                                                graph_large, vertex_index),
Chris@16:                              vertex_order_small,
Chris@16:                              choose_param(get_param(params, edges_equivalent_t()),
Chris@16:                                           always_equivalent()),
Chris@16:                              choose_param(get_param(params, vertices_equivalent_t()),
Chris@16:                                           always_equivalent())
Chris@16:                              );
Chris@16:   }
Chris@16:   
Chris@16:   
Chris@16:   // Enumerates all graph sub-graph isomorphism mappings between graphs
Chris@16:   // graph_small and graph_large. Continues until user_callback returns true or the
Chris@16:   // search space has been fully explored.
Chris@16:   template <typename GraphSmall,
Chris@16:             typename GraphLarge,
Chris@16:             typename IndexMapSmall,
Chris@16:             typename IndexMapLarge,
Chris@16:             typename VertexOrderSmall,
Chris@16:             typename EdgeEquivalencePredicate,
Chris@16:             typename VertexEquivalencePredicate,
Chris@16:             typename SubGraphIsoMapCallback>
Chris@16:   bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
Chris@16:                         SubGraphIsoMapCallback user_callback,
Chris@16:                         IndexMapSmall index_map_small, IndexMapLarge index_map_large, 
Chris@16:                         const VertexOrderSmall& vertex_order_small,
Chris@16:                         EdgeEquivalencePredicate edge_comp,
Chris@16:                         VertexEquivalencePredicate vertex_comp) {
Chris@16:     return detail::vf2_subgraph_morphism<detail::subgraph_iso>
Chris@16:                                         (graph_small, graph_large,
Chris@16:                                          user_callback,
Chris@16:                                          index_map_small, index_map_large,
Chris@16:                                          vertex_order_small,
Chris@16:                                          edge_comp,
Chris@16:                                          vertex_comp);
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // All default interface for vf2_subgraph_iso
Chris@16:   template <typename GraphSmall,
Chris@16:             typename GraphLarge,
Chris@16:             typename SubGraphIsoMapCallback>
Chris@16:   bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large, 
Chris@16:                         SubGraphIsoMapCallback user_callback) {
Chris@16: 
Chris@16:     return vf2_subgraph_iso(graph_small, graph_large, user_callback, 
Chris@16:                             get(vertex_index, graph_small), get(vertex_index, graph_large),
Chris@16:                             vertex_order_by_mult(graph_small),
Chris@16:                             always_equivalent(), always_equivalent());
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // Named parameter interface of vf2_subgraph_iso
Chris@16:   template <typename GraphSmall,
Chris@16:             typename GraphLarge,
Chris@16:             typename VertexOrderSmall,
Chris@16:             typename SubGraphIsoMapCallback,
Chris@16:             typename Param,
Chris@16:             typename Tag,
Chris@16:             typename Rest>
Chris@16:   bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
Chris@16:                         SubGraphIsoMapCallback user_callback,
Chris@16:                         const VertexOrderSmall& vertex_order_small,
Chris@16:                         const bgl_named_params<Param, Tag, Rest>& params) {
Chris@16:     
Chris@16:     return vf2_subgraph_iso(graph_small, graph_large, user_callback,
Chris@16:                             choose_const_pmap(get_param(params, vertex_index1),
Chris@16:                                               graph_small, vertex_index),
Chris@16:                             choose_const_pmap(get_param(params, vertex_index2),
Chris@16:                                               graph_large, vertex_index),
Chris@16:                             vertex_order_small,
Chris@16:                             choose_param(get_param(params, edges_equivalent_t()),
Chris@16:                                          always_equivalent()),
Chris@16:                             choose_param(get_param(params, vertices_equivalent_t()),
Chris@16:                                          always_equivalent())
Chris@16:                             );
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // Enumerates all isomorphism mappings between graphs graph1_ and graph2_.
Chris@16:   // Continues until user_callback returns true or the search space has been
Chris@16:   // fully explored.
Chris@16:   template <typename Graph1,
Chris@16:             typename Graph2,
Chris@16:             typename IndexMap1,
Chris@16:             typename IndexMap2,
Chris@16:             typename VertexOrder1,
Chris@16:             typename EdgeEquivalencePredicate,
Chris@16:             typename VertexEquivalencePredicate,
Chris@16:             typename GraphIsoMapCallback>
Chris@16:   bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2,
Chris@16:                      GraphIsoMapCallback user_callback,
Chris@16:                      IndexMap1 index_map1, IndexMap2 index_map2, 
Chris@16:                      const VertexOrder1& vertex_order1,
Chris@16:                      EdgeEquivalencePredicate edge_comp,
Chris@16:                      VertexEquivalencePredicate vertex_comp) {
Chris@16: 
Chris@16:     // Graph requirements
Chris@16:     BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph1> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph1> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph1> ));
Chris@16: 
Chris@16:     BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph2> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph2> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph2> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph2> ));
Chris@16:  
Chris@16:         
Chris@16:     typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_type;
Chris@16:     typedef typename graph_traits<Graph2>::vertex_descriptor vertex2_type;
Chris@16:     
Chris@16:     typedef typename graph_traits<Graph1>::vertices_size_type size_type1;
Chris@16:     typedef typename graph_traits<Graph2>::vertices_size_type size_type2;
Chris@16:         
Chris@16:     // Property map requirements
Chris@16:     BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap1, vertex1_type> ));
Chris@16:     typedef typename property_traits<IndexMap1>::value_type IndexMap1Value;
Chris@16:     BOOST_STATIC_ASSERT(( is_convertible<IndexMap1Value, size_type1>::value ));
Chris@16:         
Chris@16:     BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap2, vertex2_type> ));
Chris@16:     typedef typename property_traits<IndexMap2>::value_type IndexMap2Value;
Chris@16:     BOOST_STATIC_ASSERT(( is_convertible<IndexMap2Value, size_type2>::value ));
Chris@16: 
Chris@16:     // Edge & vertex requirements
Chris@16:     typedef typename graph_traits<Graph1>::edge_descriptor edge1_type;
Chris@16:     typedef typename graph_traits<Graph2>::edge_descriptor edge2_type;
Chris@16: 
Chris@16:     BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeEquivalencePredicate, 
Chris@16:                            edge1_type, edge2_type> ));
Chris@16: 
Chris@16:     BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexEquivalencePredicate, 
Chris@16:                            vertex1_type, vertex2_type> ));
Chris@16:     
Chris@16:     // Vertex order requirements
Chris@16:     BOOST_CONCEPT_ASSERT(( ContainerConcept<VertexOrder1> )); 
Chris@16:     typedef typename VertexOrder1::value_type order_value_type;
Chris@16:     BOOST_STATIC_ASSERT(( is_same<vertex1_type, order_value_type>::value ));
Chris@16:     BOOST_ASSERT( num_vertices(graph1) == vertex_order1.size() );
Chris@16: 
Chris@16:     if (num_vertices(graph1) != num_vertices(graph2))
Chris@16:       return false;
Chris@16: 
Chris@16:     typename graph_traits<Graph1>::edges_size_type num_edges1 = num_edges(graph1);
Chris@16:     typename graph_traits<Graph2>::edges_size_type num_edges2 = num_edges(graph2);
Chris@16: 
Chris@16:     // Double the number of edges for undirected graphs: each edge counts as
Chris@16:     // in-edge and out-edge
Chris@16:     if (is_undirected(graph1)) num_edges1 *= 2;
Chris@16:     if (is_undirected(graph2)) num_edges2 *= 2;
Chris@16:     if (num_edges1 != num_edges2)
Chris@16:       return false;
Chris@16: 
Chris@16:     detail::state<Graph1, Graph2, IndexMap1, IndexMap2,
Chris@16:                   EdgeEquivalencePredicate, VertexEquivalencePredicate,
Chris@16:                   GraphIsoMapCallback, detail::isomorphism> 
Chris@16:       s(graph1, graph2, index_map1, index_map2, edge_comp, vertex_comp);
Chris@16: 
Chris@16:     return detail::match(graph1, graph2, user_callback, vertex_order1, s);
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // All default interface for vf2_graph_iso
Chris@16:   template <typename Graph1,
Chris@16:             typename Graph2,
Chris@16:             typename GraphIsoMapCallback>
Chris@16:   bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2, 
Chris@16:                      GraphIsoMapCallback user_callback) {
Chris@16:     
Chris@16:     return vf2_graph_iso(graph1, graph2, user_callback, 
Chris@16:                          get(vertex_index, graph1), get(vertex_index, graph2),
Chris@16:                          vertex_order_by_mult(graph1),
Chris@16:                          always_equivalent(), always_equivalent());
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // Named parameter interface of vf2_graph_iso
Chris@16:   template <typename Graph1,
Chris@16:             typename Graph2,
Chris@16:             typename VertexOrder1,
Chris@16:             typename GraphIsoMapCallback,
Chris@16:             typename Param,
Chris@16:             typename Tag,
Chris@16:             typename Rest>
Chris@16:   bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2,
Chris@16:                      GraphIsoMapCallback user_callback,
Chris@16:                      const VertexOrder1& vertex_order1,
Chris@16:                      const bgl_named_params<Param, Tag, Rest>& params) {
Chris@16:     
Chris@16:     return vf2_graph_iso(graph1, graph2, user_callback,
Chris@16:                          choose_const_pmap(get_param(params, vertex_index1),
Chris@16:                                            graph1, vertex_index),
Chris@16:                          choose_const_pmap(get_param(params, vertex_index2),
Chris@16:                                            graph2, vertex_index),
Chris@16:                          vertex_order1,
Chris@16:                          choose_param(get_param(params, edges_equivalent_t()),
Chris@16:                                 always_equivalent()),
Chris@16:                          choose_param(get_param(params, vertices_equivalent_t()),
Chris@16:                                       always_equivalent())
Chris@16:                          );
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // Verifies a graph (sub)graph isomorphism map 
Chris@16:   template<typename Graph1,
Chris@16:            typename Graph2,
Chris@16:            typename CorresponenceMap1To2,
Chris@16:            typename EdgeEquivalencePredicate,
Chris@16:            typename VertexEquivalencePredicate>
Chris@16:   inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2, 
Chris@16:                                       const CorresponenceMap1To2 f,
Chris@16:                                       EdgeEquivalencePredicate edge_comp, 
Chris@16:                                       VertexEquivalencePredicate vertex_comp) {
Chris@16:         
Chris@16:     BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> ));
Chris@16:     BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph2> ));
Chris@16: 
Chris@16:     detail::equivalent_edge_exists<Graph2> edge2_exists;
Chris@16: 
Chris@16:     BGL_FORALL_EDGES_T(e1, graph1, Graph1) {
Chris@16:       typename graph_traits<Graph1>::vertex_descriptor s1, t1;
Chris@16:       typename graph_traits<Graph2>::vertex_descriptor s2, t2;
Chris@16:       
Chris@16:       s1 = source(e1, graph1); t1 = target(e1, graph1);
Chris@16:       s2 = get(f, s1); t2 = get(f, t1);
Chris@16:       
Chris@16:       if (!vertex_comp(s1, s2) || !vertex_comp(t1, t2))
Chris@16:         return false;
Chris@16: 
Chris@16:       typename graph_traits<Graph2>::edge_descriptor e2;
Chris@16:       
Chris@16:       if (!edge2_exists(s2, t2,
Chris@16:                         detail::edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp, e1), 
Chris@16:                         graph2))
Chris@16:         return false;
Chris@16:       
Chris@16:     }
Chris@16:   
Chris@16:     return true;
Chris@16:   }
Chris@16: 
Chris@16:   // Variant of verify_subgraph_iso with all default parameters
Chris@16:   template<typename Graph1,
Chris@16:            typename Graph2,
Chris@16:            typename CorresponenceMap1To2>
Chris@16:   inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2, 
Chris@16:                                       const CorresponenceMap1To2 f) {
Chris@16:     return verify_vf2_subgraph_iso(graph1, graph2, f, 
Chris@16:                                    always_equivalent(), always_equivalent());
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #ifdef BOOST_ISO_INCLUDED_ITER_MACROS
Chris@16: #undef BOOST_ISO_INCLUDED_ITER_MACROS
Chris@16: #include <boost/graph/iteration_macros_undef.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: #endif // BOOST_VF2_SUB_GRAPH_ISO_HPP