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