Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r81725 - in trunk: boost/graph libs/graph/doc libs/graph/example
From: jewillco_at_[hidden]
Date: 2012-12-05 14:28:15

Next message: dnljms_at_[hidden]: "[Boost-commit] svn:boost r81726 - trunk/libs/context/doc"
Previous message: jewillco_at_[hidden]: "[Boost-commit] svn:boost r81724 - trunk/boost/graph/detail"

Author: jewillco
Date: 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
New Revision: 81725
URL: http://svn.boost.org/trac/boost/changeset/81725

Log:
Added VF2 subgraph isomorphism algorithm from Flavio De Lorenzi and Vomel Christof
Added:
   trunk/boost/graph/vf2_sub_graph_iso.hpp (contents, props changed)
   trunk/libs/graph/doc/vf2_sub_graph_iso.html (contents, props changed)
   trunk/libs/graph/doc/vf2_sub_graph_iso_impl.pdf (contents, props changed)
   trunk/libs/graph/doc/vf2_sub_graph_iso_impl.tex (contents, props changed)
   trunk/libs/graph/example/vf2_random_graphs.sce (contents, props changed)
   trunk/libs/graph/example/vf2_sub_graph_iso_csr_example.cpp (contents, props changed)
   trunk/libs/graph/example/vf2_sub_graph_iso_example.cpp (contents, props changed)
   trunk/libs/graph/example/vf2_sub_graph_iso_grd_example.cpp (contents, props changed)
   trunk/libs/graph/example/vf2_sub_graph_iso_gviz_example.cpp (contents, props changed)
   trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp (contents, props changed)
   trunk/libs/graph/example/vf2_sub_graph_iso_undir_example.cpp (contents, props changed)
Text files modified:
   trunk/libs/graph/doc/table_of_contents.html | 1 +
   trunk/libs/graph/example/Jamfile.v2 | 7 +++++++
   2 files changed, 8 insertions(+), 0 deletions(-)

Added: trunk/boost/graph/vf2_sub_graph_iso.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/vf2_sub_graph_iso.hpp 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -0,0 +1,1182 @@
+//=======================================================================
+// Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi_at_[hidden])
+//
+// 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)
+//=======================================================================
+
+#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/named_function_params.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 {
+
+ // Utility functions (analogue to mcgregor_common_subgraphs)
+ // Returns binary predicate function object that compares vertices or edges
+ // between graphs using property maps
+ template <typename PropertyMap1,
+ typename PropertyMap2>
+ struct property_map_compatible {
+
+ property_map_compatible(const PropertyMap1 property_map1,
+ const PropertyMap2 property_map2)
+ : property_map1_(property_map1), property_map2_(property_map2) {}
+
+ template <typename Item1,
+ typename Item2>
+ bool operator()(const Item1 item1, const Item2 item2) const {
+ return (get(property_map1_, item1) == get(property_map2_, item2));
+ }
+
+ private:
+ const PropertyMap1 property_map1_;
+ const PropertyMap2 property_map2_;
+ };
+
+ // Returns a property_map_compatible object that compares the values
+ // of property_map1 and property_map2.
+ template <typename PropertyMap1,
+ typename PropertyMap2>
+ property_map_compatible<PropertyMap1, PropertyMap2>
+ make_property_map_compatible(const PropertyMap1 property_map1,
+ const PropertyMap2 property_map2) {
+ return property_map_compatible<PropertyMap1, PropertyMap2>
+ (property_map1, property_map2);
+ }
+
+ // Binary function object that always returns true. Used when
+ // vertices or edges are always compatible (i.e. have no labels).
+ struct always_compatible {
+ template <typename Item1,
+ typename Item2>
+ bool operator()(const Item1&, const Item2&) const {
+ return true;
+ }
+ };
+
+
+ // Default print_callback
+ template <typename Graph1,
+ typename Graph2>
+ struct vf2_print_callback {
+
+ vf2_print_callback(const Graph1& graph1, const Graph2& graph2,
+ bool verify = false)
+ : graph1_(graph1), graph2_(graph2), verify_(verify) {}
+
+ template <typename CorrespondenceMap1To2,
+ typename CorrespondenceMap2To1>
+ bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {
+
+ if (verify_)
+ std::cout << "Verify: " << std::boolalpha
+ << verify_vf2_sub_graph_iso(graph1_, graph2_, f)
+ << std::endl;
+
+ // Print sub graph isomorphism map
+ BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
+ std::cout << '(' << get(vertex_index, graph1_, v) << ", "
+ << get(vertex_index, graph1_, get(f, v)) << ") ";
+
+ std::cout << std::endl;
+
+ return true;
+ }
+
+ private:
+ const Graph1& graph1_;
+ const Graph2& graph2_;
+
+ const bool verify_;
+ };
+
+ 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),
+ term_in_count_(0), term_out_count_(0), term_both_count_(0), core_count_(0) {
+
+ core_vec_.resize(num_vertices(graph_this_), graph_traits<GraphOther>::null_vertex());
+ core_ = make_iterator_property_map(core_vec_.begin(), index_map_this_);
+
+ in_vec_.resize(num_vertices(graph_this_), 0);
+ in_ = make_iterator_property_map(in_vec_.begin(), index_map_this_);
+
+ out_vec_.resize(num_vertices(graph_this_), 0);
+ out_ = make_iterator_property_map(out_vec_.begin(), index_map_this_);
+ }
+
+ // 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 compatible_edge_exists {
+
+ compatible_edge_exists() {};
+
+ typedef typename boost::graph_traits<Graph>::out_edge_iterator edge_iterator_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) {
+
+ edge_iterator_type ei, ei_end;
+ for (boost::tie(ei, ei_end) = out_edges(s, g); ei != ei_end; ++ei) {
+ if ((target(*ei, g) == t) && is_valid_edge(*ei) &&
+ (matched_edges_.find(ei) == matched_edges_.end())) {
+ matched_edges_.insert(ei);
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ private:
+
+ std::set<edge_iterator_type> matched_edges_;
+ };
+
+ template <typename Graph>
+ struct compatible_edge_exists<Graph, typename boost::disable_if<is_multigraph<Graph> >::type> {
+
+ compatible_edge_exists() {};
+
+ 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 EdgeCompatibilityPredicate>
+ struct edge1_predicate {
+
+ edge1_predicate(EdgeCompatibilityPredicate edge_comp,
+ typename graph_traits<Graph2>::edge_descriptor e2)
+ : edge_comp_(edge_comp), e2_(e2) {}
+
+ bool operator()(typename graph_traits<Graph1>::edge_descriptor e1) const {
+ return edge_comp_(e1, e2_);
+ }
+
+ EdgeCompatibilityPredicate 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 EdgeCompatibilityPredicate>
+ struct edge2_predicate {
+
+ edge2_predicate(EdgeCompatibilityPredicate edge_comp,
+ typename graph_traits<Graph1>::edge_descriptor e1)
+ : edge_comp_(edge_comp), e1_(e1) {}
+
+ bool operator()(typename graph_traits<Graph2>::edge_descriptor e2) const {
+ return edge_comp_(e1_, e2);
+ }
+
+ EdgeCompatibilityPredicate edge_comp_;
+ typename graph_traits<Graph1>::edge_descriptor e1_;
+ };
+
+
+ enum problem_selector { sub_graph_iso, isomorphism };
+
+ // The actual state associated with both graphs
+ template<typename Graph1,
+ typename Graph2,
+ typename IndexMap1,
+ typename IndexMap2,
+ typename EdgeCompatibilityPredicate,
+ typename VertexCompatibilityPredicate,
+ 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_;
+
+ EdgeCompatibilityPredicate edge_comp_;
+ VertexCompatibilityPredicate vertex_comp_;
+
+ base_state<Graph1, Graph2, IndexMap1, IndexMap2> state1_;
+ base_state<Graph2, Graph1, IndexMap2, IndexMap1> state2_;
+
+ // Two helper functions used in Feasibility and Valid functions to test
+ // terminal set counts when testing for:
+ // - graph sub-graph isomorphism, or
+ inline bool comp_term_sets(graph1_size_type a,
+ graph2_size_type b,
+ boost::mpl::int_<sub_graph_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,
+ EdgeCompatibilityPredicate edge_comp,
+ VertexCompatibilityPredicate 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;
+
+ {
+ compatible_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, EdgeCompatibilityPredicate>(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;
+ }
+ }
+ }
+
+ {
+ compatible_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, EdgeCompatibilityPredicate>(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;
+
+ {
+ compatible_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)) {
+ vertex1_type v = v_new;
+ if (w != w_new)
+ v = state2_.core(w);
+
+ if (!edge1_exists(v, v_new,
+ edge1_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(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;
+ }
+ }
+ }
+
+ {
+ compatible_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)) {
+ vertex1_type v = v_new;
+ if (w != w_new)
+ v = state2_.core(w);
+
+ if (!edge1_exists(v_new, v,
+ edge1_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(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;
+ }
+ }
+ }
+
+ 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>());
+ }
+
+ // 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 EdgeCompatibilityPredicate,
+ typename VertexCompatibilityPredicate,
+ 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,
+ EdgeCompatibilityPredicate, VertexCompatibilityPredicate,
+ 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;
+
+ recur:
+ if (s.success()) {
+ if (!s.call_back(user_callback))
+ return false;
+
+ 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 true;
+
+ 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 frequency/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, const 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_;
+ const FrequencyMap& freq_;
+ };
+
+
+ // Sorts vertices of a graph by frequency/degree
+ template<typename Graph,
+ typename IndexMap,
+ typename VertexOrder>
+ void sort_vertices(const Graph& graph, const 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));
+
+ }
+
+ } // namespace detail
+
+
+ // 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 EdgeCompatibilityPredicate,
+ typename VertexCompatibilityPredicate,
+ typename SubGraphIsoMapCallBack>
+ bool vf2_sub_graph_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,
+ EdgeCompatibilityPredicate edge_comp,
+ VertexCompatibilityPredicate 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 compatibility 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<EdgeCompatibilityPredicate,
+ edge_small_type, edge_large_type> ));
+
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexCompatibilityPredicate,
+ 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;
+
+ if ((num_vertices(graph_small) == 0) && (num_vertices(graph_large) == 0))
+ return true;
+
+ detail::state<GraphSmall, GraphLarge, IndexMapSmall, IndexMapLarge,
+ EdgeCompatibilityPredicate, VertexCompatibilityPredicate,
+ SubGraphIsoMapCallBack, detail::sub_graph_iso>
+ 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);
+ }
+
+
+ // All default interface for vf2_sub_graph_iso
+ template <typename GraphSmall,
+ typename GraphLarge,
+ typename SubGraphIsoMapCallBack>
+ bool vf2_sub_graph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
+ SubGraphIsoMapCallBack user_callback) {
+
+ typedef typename graph_traits<GraphSmall>::vertex_descriptor vertex_small_type;
+
+ std::vector<vertex_small_type> vertex_order_small;
+ BGL_FORALL_VERTICES_T(v, graph_small, GraphSmall)
+ vertex_order_small.push_back(v);
+
+ detail::sort_vertices(graph_small, get(vertex_index, graph_small), vertex_order_small);
+
+ return vf2_sub_graph_iso(graph_small, graph_large, user_callback,
+ get(vertex_index, graph_small), get(vertex_index, graph_large),
+ vertex_order_small,
+ always_compatible(), always_compatible());
+ }
+
+
+ // Named parameter interface of vf2_sub_graph_iso
+ template <typename GraphSmall,
+ typename GraphLarge,
+ typename VertexOrderSmall,
+ typename SubGraphIsoMapCallBack,
+ typename Param,
+ typename Tag,
+ typename Rest>
+ bool vf2_sub_graph_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_sub_graph_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_compatible()),
+ choose_param(get_param(params, vertices_equivalent_t()),
+ always_compatible())
+ );
+
+ }
+
+
+ // 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 EdgeCompatibilityPredicate,
+ typename VertexCompatibilityPredicate,
+ 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,
+ EdgeCompatibilityPredicate edge_comp,
+ VertexCompatibilityPredicate 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 compatibility requirements
+ typedef typename graph_traits<Graph1>::edge_descriptor edge1_type;
+ typedef typename graph_traits<Graph2>::edge_descriptor edge2_type;
+
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeCompatibilityPredicate,
+ edge1_type, edge2_type> ));
+
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexCompatibilityPredicate,
+ 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;
+
+ if ((num_vertices(graph1) == 0) && (num_vertices(graph2) == 0))
+ return true;
+
+ detail::state<Graph1, Graph2, IndexMap1, IndexMap2,
+ EdgeCompatibilityPredicate, VertexCompatibilityPredicate,
+ 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) {
+
+ typedef typename graph_traits<Graph1>::vertex_descriptor vertex1_type;
+
+ std::vector<vertex1_type> vertex_order1;
+ BGL_FORALL_VERTICES_T(v, graph1, Graph1)
+ vertex_order1.push_back(v);
+
+ detail::sort_vertices(graph1, get(vertex_index, graph1), vertex_order1);
+
+ return vf2_graph_iso(graph1, graph2, user_callback,
+ get(vertex_index, graph1), get(vertex_index, graph2),
+ vertex_order1,
+ always_compatible(), always_compatible());
+ }
+
+
+ // 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_compatible()),
+ choose_param(get_param(params, vertices_equivalent_t()),
+ always_compatible())
+ );
+
+ }
+
+
+ // Verifies a graph (sub)graph isomorphism map
+ template<typename Graph1,
+ typename Graph2,
+ typename CorresponenceMap1To2,
+ typename EdgeCompatibilityPredicate,
+ typename VertexCompatibilityPredicate>
+ inline bool verify_vf2_sub_graph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f,
+ EdgeCompatibilityPredicate edge_comp,
+ VertexCompatibilityPredicate vertex_comp) {
+
+ BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> ));
+ BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph2> ));
+
+ detail::compatible_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, EdgeCompatibilityPredicate>(edge_comp, e1),
+ graph2))
+ return false;
+
+ }
+
+ return true;
+ }
+
+ // Variant of verify_sub_graph_iso with all default parameters
+ template<typename Graph1,
+ typename Graph2,
+ typename CorresponenceMap1To2>
+ inline bool verify_vf2_sub_graph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f) {
+ return verify_vf2_sub_graph_iso(graph1, graph2, f,
+ always_compatible(), always_compatible());
+ }
+
+
+
+} // 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

Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html (original)
+++ trunk/libs/graph/doc/table_of_contents.html 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -240,6 +240,7 @@
 <li>Graph Structure Comparisons
 <ol>
 <LI>isomorphism
+ <LI>vf2_sub_graph_iso (VF2 subgraph isomorphism algorithm)
 <li>mcgregor_common_subgraphs</li>
 </ol>

Added: trunk/libs/graph/doc/vf2_sub_graph_iso.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/vf2_sub_graph_iso.html 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -0,0 +1,547 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
+
+<html>
+ <head>
+ <title>Boost Graph Library: VF2 (Sub)Graph Isomorphism</title>
+ <style type="text/css">
+ 
+ </style>
+ </head>
+ <body>
+ <img src="../../../boost.png" alt="C++ Boost" width="277" height="86" />
+ 
+ <h1>
+ <tt>vf2_sub_graph_iso</tt>
+ </h1>
+ <pre>
+// all defaults interface
+template <typename GraphSmall,
+ typename GraphLarge,
+ typename SubGraphIsoMapCallBack>
+bool vf2_sub_graph_iso(const GraphSmall& graph_small,
+ const GraphLarge& graph_large,
+ SubGraphIsoMapCallBack user_callback)
+
+
+// named parameter version
+template <typename GraphSmall,
+ typename GraphLarge,
+ typename VertexOrderSmall,
+ typename SubGraphIsoMapCallBack,
+ typename Param,
+ typename Tag,
+ typename Rest>
+bool vf2_sub_graph_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)
+
+
+// non-named parameter version
+template <typename GraphSmall,
+ typename GraphLarge,
+ typename IndexMapSmall,
+ typename IndexMapLarge,
+ typename VertexOrderSmall,
+ typename EdgeCompatibilityPredicate,
+ typename VertexCompatibilityPredicate,
+ typename SubGraphIsoMapCallBack>
+bool vf2_sub_graph_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,
+ EdgeCompatibilityPredicate edge_comp,
+ VertexCompatibilityPredicate vertex_comp)
+ </pre>
+ 
+ An isomorphism between two graphs G1=(V1, E1)
+ and G2=(V2, E2) is a
+ bijective mapping M of the vertices of one graph to vertices of the other
+ graph that preserves the edge structure of the graphs. M is said to be a
+ graph-subgraph isomorphism iff M is an isomorphism between
+ G1 and a subgraph of G2.
+ 
+
+ 
+ This function finds all graph-subgraph isomorphism mappings between
+ graphs <tt>graph_small</tt> and <tt>graph_large</tt> and outputs them to
+ <tt>user_callback</tt>. It continues until <tt>user_callback</tt>
+ returns true or the search space has been fully explored.
+ <tt>EdgeCompatibilityPredicate</tt> and
+ <tt>VertexCompatibilityPredicate</tt> predicates are used to test whether
+ edges and vertices are compatible. To use property maps for equivalence,
+ look at the
+ <tt>make_property_map_compatible</tt>
+ function. By default <tt>always_compatible</tt> is used, which returns
+ true for any pair of vertices or edges.
+ 
+ 
+ The current implementation is based on the VF2 algorithm,
+ introduced by Cordella et al. An in-depth description of the algorithm is
+ given in [<a href=#cordella2001>1</a>] and [<a href=#cordella2004>2</a>]
+ and references therein. In brief, the process of finding a mapping between
+ the two graphs G1 and G2 determines
+ the isomorphism mapping M, which associates vertices
+ G1 with vertices of G2 and vice
+ versa. It can be described by means of a state space representation, which
+ is explored by the algorithm according to a depth-first strategy. Each
+ state s of the matching process can be associated with a partial
+ mapping M(s). At each level, the algorithm computes the set of
+ the vertex pairs that are candidates to be added to the current state
+ s. If a pair of vertices (v, w) is feasible, the mapping
+ is extended and the associated successor state s' is computed.
+ The whole procedure is then repeated for state s'. A somewhat more
+ detailed description of the current implementation is given in the file
+ vf2_sub_graph_iso_impl.pdf.
+ 
+
+ <h3>Where Defined</h3>
+ boost/graph/vf2_sub_graph_iso.hpp
+ 
+ All functions are defined in the boost namespace.
+ 
+
+ <h3>Parameters</h3>
+
+ IN: <tt>const GraphSmall& graph_small</tt>
+ <blockquote>
+ The (first) smaller graph (fewer vertices) of the pair to be tested for
+ isomorphism. The type <tt>GraphSmall</tt> must be a
+ model of
+ Vertex List Graph
+ Edge List Graph,
+ Bidirectional Graph and
+ Adjacency Matrix.
+ </blockquote>
+
+ IN: <tt>const GraphLarge& graph_large</tt>
+ <blockquote>
+ The (second) larger graph to be tested.
+ Type <tt>GraphLarge</tt> must be a model of
+ Vertex List Graph
+ Edge List Graph,
+ Bidirectional Graph and
+ Adjacency Matrix.
+ </blockquote>
+
+ OUT: <tt>SubGraphIsoMapCallBack user_callback</tt>
+ <blockquote>
+ A function object to be called when a graph-subgraph isomorphism has been discovered. The
+ <tt>operator()</tt> must have following form:
+ <pre>
+template <typename CorrespondenceMap1To2,
+ typename CorrespondenceMap2To1>
+bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1 g) const
+ </pre>
+ Both the <tt>CorrespondenceMap1To2</tt>
+ and <tt>CorresondenceMap2To1</tt> types are models
+ of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
+ Property Map</a> and map equivalent vertices across the two
+ graphs given to <tt>vf2_sub_graph_iso</tt> (or <tt>vf2_graph_iso</tt>. For
+ instance, if <tt>v</tt> is
+ from <tt>graph_small</tt>, <tt>w</tt> is from <tt>graph_large</tt>,
+ and the vertices can be considered equivalent,
+ then <tt>get(f, v)</tt> will be <tt>w</tt> and <tt>get(g, w)</tt>
+ will be <tt>v</tt>. If any vertex, say <tt>v</tt> in <tt>graph_small</tt>,
+ does not match a vertex in <tt>graph_large</tt> ,
+ then <tt>get(f, v)</tt> will be <tt>graph_traits<GraphLarge>::null_vertex()</tt>.
+ Likewise for any un-matched vertices from <tt>graph_large</tt>,
+ <tt>get(g, w)</tt> will be <tt>graph_traits<GraphSmall>::null_vertex()</tt>.
+
+ Returning false from the callback will abort the search immediately. Otherwise,
+ the entire search space will be explored. A "default" print callback
+ is provided as a utility function and another one is
+ given in Example 2.
+ </blockquote>
+
+ IN: <tt>const VertexOrderSmall& vertex_order_small</tt>
+ <blockquote>
+ The ordered vertices of the smaller (first) graph <tt>graph_small</tt>.
+ During the matching process the vertices are examined in the order given by
+ <tt>vertex_order_small</tt>. Type <tt>VertexOrderSmall</tt> must be a model
+ of ContainerConcept
+ with value type
+ <tt>graph_traits<GraphSmall>::vertex_descriptor</tt>.
+ 
+ Default The vertices are ordered by multiplicity of in/out degree.
+ </blockquote>
+
+ <h3>Named Parameters</h3>
+
+ IN: <tt>vertex_index1(IndexMapSmall index_map_small)</tt>
+ <blockquote>
+ This maps each vertex to an integer in the range <tt>[0, num_vertices(graph_small))</tt>.
+ Type <tt>IndexMapSmall</tt> must be a model of
+ Readable Property Map.
+ 
+ Default: <tt>get(vertex_index, graph_small)</tt>
+ </blockquote>
+
+ IN: <tt>vertex_index2(IndexMapLarge index_map_large)</tt>
+ <blockquote>
+ This maps each vertex to an integer in the range <tt>[0, num_vertices(graph_large))</tt>.
+ Type <tt>IndexMapLarge</tt> must be a model of
+ Readable Property Map.
+ 
+ Default: <tt>get(vertex_index, graph_large)</tt>
+ </blockquote>
+
+ IN: <tt>edges_equivalent(EdgeCompatibilityPredicate edge_comp)</tt>
+ <blockquote>
+ This function object is used to determine if edges between the two graphs
+ <tt>graph_small</tt> and <tt>graph_large</tt> are compatible.
+ Type <tt>EdgeCompatiblePredicate</tt> must be a model of
+ of <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary
+ Predicate</a> and have argument types of
+ <tt>graph_traits<GraphSmall>::edge_descriptor</tt> and
+ <tt>graph_traits<GraphLarge>::edge_descriptor</tt>. A return value of true
+ indicates that the edges are compatible.
+ 
+ Default: <tt>always_compatible</tt>
+ </blockquote>
+
+ IN: <tt>vertices_equivalent(VertexCompatibilityPredicate vertex_comp)</tt>
+ <blockquote>
+ This function object is used to determine if vertices between the two graphs
+ <tt>graph_small</tt> and <tt>graph_large</tt> are compatible.
+ Type <tt>VertexCompatiblePredicate</tt> must be a model of
+ Binary Predicate
+ and have argument types of
+ <tt>graph_traits<GraphSmall>::vertex_descriptor</tt> and
+ <tt>graph_traits<GraphLarge>::vertex_descriptor</tt>. A return value of true
+ indicates that the vertices are compatible.
+ 
+ Default: <tt>always_compatible</tt>
+ </blockquote>
+
+ <h3>Related Functions</h3>
+ 
+ Non-named parameter, named-parameter and all default parameter versions of
+ function
+ 
+ <pre>
+vf2_graph_iso(...)
+ </pre>
+ 
+ for isomorphism testing take the same parameters as the corresponding
+ functions <tt>vf2_sub_graph_iso</tt> for sub-graph isomorphism testing.
+ The algorithm finds all isomorphism mappings between graphs
+ <tt>graph1</tt> and <tt>graph2</tt> and outputs them to
+ <tt>user_callback</tt>. It continues until <tt>user_callback</tt>
+ returns true or the search space has been fully explored. As before,
+ <tt>EdgeCompatibilityPredicate</tt> and
+ <tt>VertexCompatibilityPredicate</tt> predicates are used to test
+ whether edges and vertices are compatible with
+ <tt>always_compatible</tt> as default.
+ 
+
+ <h3>Utility Functions and Structs</h3>
+ <pre id="make_property_map_compatible">
+template <typename PropertyMap1,
+ typename PropertyMap2>
+property_map_compatible<PropertyMap1, PropertyMap2>
+make_property_map_compatible(const PropertyMap1 property_map1,
+ const PropertyMap2 property_map2)
+ </pre>
+ <blockquote>
+ Returns a binary predicate function object
+ (<tt>property_map_compatible<PropertyMap1, PropertyMap2></tt>) that compares
+ vertices or edges between graphs using property maps.
+ </blockquote>
+
+ <tt id="always_compatible">struct always_compatible</tt>
+ <blockquote>
+ A binary function object that returns true for any pair of items.
+ </blockquote>
+
+ <pre id="vf2_callback">
+template <typename Graph1,
+ typename Graph2>
+struct vf2_print_callback
+ </pre>
+ <blockquote>
+ Callback function object that prints out the correspondences between vertices
+ of <tt>Graph1</tt> and <tt>Graph2</tt>. The constructor takes the two graphs G1
+ and G2 and an optional <tt>bool</tt> parameter as arguments. If the latter is
+ set to <tt>true</tt>, the callback function will verify the mapping before outputting
+ it to standard output.
+ </blockquote>
+
+ <pre>
+// Variant of verify_sub_graph_iso with all default parameters
+template<typename Graph1,
+ typename Graph2,
+ typename CorresponenceMap1To2>
+inline bool verify_vf2_sub_graph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f)
+
+
+// Verifies a graph (sub)graph isomorphism map
+template<typename Graph1,
+ typename Graph2,
+ typename CorresponenceMap1To2,
+ typename EdgeCompatibilityPredicate,
+ typename VertexCompatibilityPredicate>
+inline bool verify_vf2_sub_graph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f,
+ EdgeCompatibilityPredicate edge_comp,
+ VertexCompatibilityPredicate vertex_comp)
+ </pre>
+ <blockquote>
+This function can be used to verify a (sub)graph isomorphism mapping f. The parameters are
+akin to function <tt>vf2_sub_graph_iso</tt> (<tt>vf2_graph_iso</tt>).
+ </blockquote>
+
+
+ <h3>Complexity</h3>
+ 
+ Spatial and time complexity are given in [2]. The spatial
+ complexity of VF2 is of order O(V), where V is the (maximum) number
+ of vertices of the two graphs. Time complexity is O(V2) in the best case and
+ O(V!·V) in the worst case.
+ 
+
+ <h3>Examples</h3>
+
+ <h4>Example 1</h4>
+ 
+ In the example below, a small graph <tt>graph1</tt> and a larger graph
+ <tt>graph2</tt> are defined. Here small and large refers to the number of
+ vertices of the graphs. <tt>vf2_sub_graph_iso</tt> computes all the
+ sub-graph isomorphism mappings between the two graphs and outputs them
+ via <tt>callback</tt>.
+ 
+ <pre>
+typedef adjacency_list<vecS, vecS, bidirectionalS> graph_type;
+
+// Build graph1
+int num_vertices1 = 8; graph_type graph1(num_vertices1);
+add_edge(0, 6, graph1); add_edge(0, 7, graph1);
+add_edge(1, 5, graph1); add_edge(1, 7, graph1);
+add_edge(2, 4, graph1); add_edge(2, 5, graph1); add_edge(2, 6, graph1);
+add_edge(3, 4, graph1);
+
+// Build graph2
+int num_vertices2 = 9; graph_type graph2(num_vertices2);
+add_edge(0, 6, graph2); add_edge(0, 8, graph2);
+add_edge(1, 5, graph2); add_edge(1, 7, graph2);
+add_edge(2, 4, graph2); add_edge(2, 7, graph2); add_edge(2, 8, graph2);
+add_edge(3, 4, graph2); add_edge(3, 5, graph2); add_edge(3, 6, graph2);
+
+// true instructs callback to verify a map using
+// verify_vf2_sub_graph_iso
+vf2_print_callback<graph_type, graph_type> callback(graph1, graph2, true);
+
+bool ret = vf2_sub_graph_iso(graph1, graph2, callback);
+ </pre>
+
+The complete example can be found under
+examples/vf2_sub_graph_iso_example.cpp.
+ 
+
+
+
+ <h4>Example 2</h4>
+ This example uses the GraphViz input parser, i.e. read_graphviz
+ function to interpret the two graphs specified in files graph_small.dot and graph_large.dot
+ using the using the GraphViz DOT language. Sample files are provided
+ below. <tt>vf2_sub_graph_iso</tt> computes all the sub-graph isomorphism mappings
+ between <tt>graph_small</tt> and <tt>graph_large</tt>.
+ <pre>
+std::ifstream graph_small_file("graph_small.dot");
+std::ifstream graph_large_file("graph_large.dot");
+
+// Vertex properties
+typedef property <vertex_name_t, std::string> vertex_p;
+
+// adjacency_list-based type
+typedef adjacency_list <vecS, vecS, undirectedS, vertex_p> graph_t;
+
+// Construct an empty graph_small and prepare the dynamic_property_maps.
+graph_t graph_small(0);
+dynamic_properties dp_small;
+
+property_map<graph_t, vertex_name_t>::type name_small =
+ get(vertex_name, graph_small);
+dp_small.property("node_id", name_small);
+
+// Read graph_small
+bool status = read_graphviz(graph_small_file, graph_small, dp_small, "node_id");
+
+// Construct an empty graph_large and prepare the dynamic_property_maps,
+// following the read_graphviz example
+graph_t graph_large(0);
+dynamic_properties dp_large;
+
+property_map<graph_t, vertex_name_t>::type name_large =
+ get(vertex_name, graph_large);
+dp_large.property("node_id", name_large);
+
+// Read graph_large
+status = read_graphviz(graph_large_file, graph_large, dp_large, "node_id");
+
+// Create the call_back function
+typedef property_map<graph_t, vertex_name_t>::type p_map_t;
+print_callback<graph_t, graph_t, p_map_t, p_map_t> callback(graph_small, graph_large,
+ name_small, name_large, true);
+ // Compute the sub-graph isomorphism mappings
+bool ret = vf2_sub_graph_iso(graph_small, graph_large, callback);
+ </pre>
+
+ To output the mappings using the node names, the following callback function object is created:
+
+ <pre>
+// Define a print_callback
+template <typename Graph1,
+ typename Graph2,
+ typename PropertyMap1,
+ typename PropertyMap2>
+struct print_callback {
+
+ print_callback(const Graph1& graph1, const Graph2& graph2,
+ PropertyMap1 p_map1, PropertyMap2 p_map2,
+ bool verify = false)
+ : graph1_(graph1), graph2_(graph2),
+ p_map1_(p_map1), p_map2_(p_map2),
+ verify_(verify) {}
+
+ template <typename CorrespondenceMap1To2,
+ typename CorrespondenceMap2To1>
+ bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {
+
+ if (verify_)
+ std::cout << "Verify: " << std::boolalpha
+ << verify_vf2_sub_graph_iso(graph1_, graph2_, f)
+ << std::endl;
+
+// Print sub graph isomorphism map
+ BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
+ std::cout << '(' << get(p_map1_,v) << ", "
+ << get(p_map2_, get(f, v)) << ") ";
+
+ std::cout << std::endl;
+
+ return true;
+ }
+
+private:
+ const Graph1& graph1_;
+ const Graph2& graph2_;
+
+ const PropertyMap1& p_map1_;
+ const PropertyMap2& p_map2_;
+
+ const bool verify_;
+};
+ </pre>
+
+ Using the sample DOT-files graph_small.dot:
+
+ <pre id="dot_files">
+graph G_small {
+node1 -- node2;
+node1 -- node3;
+node3 -- node3;
+node4 -- node1;
+node4 -- node3;
+}
+ </pre>
+
+ and graph_large.dot:
+
+ <pre>
+graph G_large {
+node1 -- node3;
+node1 -- node4;
+node1 -- node6;
+node2 -- node4;
+node2 -- node5;
+node3 -- node3;
+node4 -- node5;
+node4 -- node6;
+node6 -- node6;
+}
+ </pre>
+
+ <tt>vf2_sub_graph_iso</tt> finds the mappings <tt>(node1, node4) (node2, node2)
+ (node3, node6) (node4, node1)</tt> and <tt>(node1, node4) (node2, node5)
+ (node3, node6) (node4, node1)</tt>.
+ To compile this example, you will need to build and link against the
+ "boost_graph" and "boost_regex" libraries
+ (cf. read_graphviz).
+
+
+The complete example is provided under
+examples/vf2_sub_graph_iso_gviz_example.cpp,
+including a Scilab script to generate simple dot-files
+examples/vf2_random_graphs.sce.
+ 
+
+
+
+<h4>Additional Examples</h4>
+
+
+These are: a multi-graph example
+examples/vf2_sub_graph_iso_multi_example.cpp,
+ 
+one using a compressed_sparse_row_graph (works not for <tt>directed</tt> because <tt>in_edges</tt> not available)
+examples/vf2_sub_graph_iso_csr_example.cpp,
+ 
+one putting a grid_graph
+examples/vf2_sub_graph_iso_grd_example.cpp
+ 
+and one matching bidirectional und undirected graphs
+examples/vf2_sub_graph_iso_undir_example.cpp.
+ 
+
+
+ <h3>Bibliography</h3>
+
+ <dl>
+ <dt><a name="cordella2001">1</a>
+ <dd>
+ L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
+ An improved algorithm for matching large graphs.
+ In: 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, pp. 149-159, Cuen, 2001.
+ </dd>
+ <dt><a name="cordella2004">2</a>
+ <dd>
+ L. P. Cordella, P. Foggia, C. Sansone, and M. Vento.
+ A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.
+ IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 10, pp. 1367-1372, 2004.
+ </dd>
+ </dl>
+
+ <hr />
+ Copyright © 2012, Flavio De Lorenzi
+ (<a href="mailto:fdlorenzi_at_[hidden]">fdlorenzi_at_[hidden]</a>)
+
+ </body>
+</html>

Added: trunk/libs/graph/doc/vf2_sub_graph_iso_impl.pdf
==============================================================================
Binary file. No diff available.

Added: trunk/libs/graph/doc/vf2_sub_graph_iso_impl.tex
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/vf2_sub_graph_iso_impl.tex 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -0,0 +1,474 @@
+\documentclass[12pt]{article}
+\usepackage{amsmath}
+\usepackage{algorithmicx}
+\usepackage{algpseudocode}
+\usepackage{listings}
+
+% abbreviations and acronyms
+\def\etal{{et al.\ }}
+\def\eg{{\it e.g.\ }}
+\def\etc{{\it etc.\ }}
+\def\ie{{\it i.e.\ }}
+\def\cf{{\it cf.\ }}
+
+\title{An Implementation of the {\sc VF2} (Sub)Graph Isomorphism Algorithm
+Using The Boost Graph Library}
+\author{Flavio De Lorenzi\thanks{E-mail: fdlorenzi_at_[hidden]}}
+
+\date{\today}
+
+\begin{document}
+\maketitle
+%\VerbatimFootnotes
+
+\begin{abstract}
+This article describes an implementation of the {\sc VF2} algorithm, introduced
+by Cordella \etal for solving the graph isomorphism and graph-subgraph
+isomorphism problems, using the Boost Graph Library. This implementation
+includes algorithmic improvements to account for self-loops and works for
+directed and undirected graphs.
+\end{abstract}
+
+\baselineskip=\normalbaselineskip
+
+%\newpage
+
+\section{Introduction}
+This section briefly outlines the {\sc VF2} algorithm\footnote{The original
+code by Pasquale Foggia and collaborators can be obtained from:
+\texttt{http://www.cs.sunysb.edu/{\textasciitilde}algorith/implement/vflib/implement.shtml}},
+following closely \cite{cordella+2001, cordella+2004}.
+
+An isomorphism between two graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ is a
+bijective mapping $M$ of the vertices of one graph to vertices of the other
+graph that preserves the edge structure of the graphs. $M$ is said to be a
+graph-subgraph isomorphism iff $M$ is an isomorphism between $G_1$ and a
+subgraph of $G_2$.
+
+A matching process between the two graphs $G_1$ and $G_2$ determines the
+isomorphism mapping $M$ which associates vertices of $G_1$ with vertices of
+$G_2$ and vice versa. The matching process can be described by means of a
+state space representation combined with a depth-first strategy. The details
+can be found in \cite{cordella+2001, cordella+2004} and references therein.
+
+Cordella \etal give the following high-level description of the matching
+algorithm:
+
+\begin{algorithmic}
+\Procedure{Match}{$s$}
+\If {$M(s)$ covers all the nodes of $G_2$}
+ \State \Return $M(s)$
+\Else
+ \State Compute the set $P(s)$ of the pairs of vertices for inclusion in $M(s)$
+ \ForAll {$(v,w) \in P(s)$}
+ \If {$F(s,v,w)$}
+ \State Compute the state $s'$ obtained by adding $(v,w)$ to $M(s)$
+ \State \Call {Match}{$s'$}
+ \EndIf
+ \EndFor
+ \State Restore data structures
+\EndIf
+\EndProcedure
+\end{algorithmic}
+
+$M(s)$ is a partial mapping associated with a state $s$, $P(s)$ is the set
+of all possible pairs of vertices $(v,w)$ to be added to the current state $s$
+and $F(s,v,w)$ is a boolean function (called {\em feasibility function}) used
+to prune the search tree. If its value is {\em true} the state $s'$ obtained
+by adding $(v,w)$ to $s$ is guaranteed to be a partial isomorphism if $s$ is.
+
+% \subsubsection*{State Space Representation}
+
+To construct $P(s)$ and $F(s,v,w)$ Cordella \etal define the
+{\em out-terminal set} as the set of vertices of $G_1$ that are not in $M(s)$
+but are successors of vertices in $M(s)$ (connected by out edges), and the
+{\em in-terminal set} as the set of vertices that are not in $M(s)$ but are
+predecessors of vertices in $M(s)$. Analogue sets are defined for $G_2$.
+
+% \subsubsection*{Data Structures}
+
+To compute $P(s)$ and $F(s,v,w)$ efficiently, Cordella \etal employ the
+following data structures:
+
+\begin{itemize}
+
+\item Vectors \verb+core_1+ and \verb+core_2+ whose dimensions correspond to
+the number of vertices in $G_1$ and $G_2$, respectively. These vectors store the
+present mapping.
+
+\item Vectors \verb+in_1+, \verb+out_1+, \verb+in_2+ and \verb+out_2+ used to
+describe the membership to the terminal sets. \verb+in_1+ is non-zero for a
+particular vertex if the vertex is either in the partial mapping $M(s)$ or
+belongs to the in-terminal state of $G_1$. The actual value is given by the
+level of the depth-first search tree at which the vertex was included in the
+corresponding set.
+
+\end{itemize}
+
+
+\section{Implementation}
+
+The computations of the terminal sets or the addition (deletion) of a pair of
+vertices to (from) a state are analogous for the two graphs $G_1$ and $G_2$.
+For example, to add the vertex pair $(v, w)$ with $v \in V_1$ and $w \in V_2$
+to vector \verb+core_1+ is the same as adding $(w, v)$ to \verb+core_2+. This
+observation suggests the following improvement to the original {\sc VF2}
+implementation. Instead of implementing a state for $G_1$ and $G_2$ with
+associated vectors \verb+core_1+, \verb+core_2+, \verb+in_1+, \verb+out_1+,
+\verb+in_2+ and \verb+out_2+ directly, we implement a ``helper state'' class
+\verb+base_state+ associated with a single graph. Class \verb+base_state+ then
+contains \verb+core_+, \verb+in_+ and \verb+out_+, and member functions such as
+%\eg \verb+push(const vertex_this_type& v_this, const vertex_other_type& v_other)+
+\eg \texttt{push(const vertex \_this\_type\& v\_this, const vertex\_other\_type\& v\_other)}
+to add a vertex pair. The actual state associated with both graphs (implemented in
+class \verb+state+) can thus be constructed using two ``helper states'', one
+for each graph. For instance, the member function \verb+push+ to add a pair of
+vertices to the actual state is obtained as illustrated in the code
+fragment below:
+
+\lstset{breaklines=true, breakatwhitespace=true}
+\lstset{columns=fullflexible}
+\lstset{language=C++}
+\begin{lstlisting}
+<template<typename Graph1,
+ typename Graph2,
+ typename IndexMap1,
+ typename IndexMap2, .... >
+class state
+{
+
+ ...
+
+ base_state<Graph1, Graph2, IndexMap1, IndexMap2> state1_;
+ base_state<Graph2, Graph1, IndexMap2, IndexMap1> state2_;
+
+public:
+ // Add vertex pair to the state
+ void push(const vertex1_type& v, const vertex2_type& w)
+ {
+ state1_.push(v, w);
+ state2_.push(w, v);
+ }
+
+ ...
+
+};
+\end{lstlisting}
+
+These classes (\verb+base_state+ and \verb+state+) and the non-recursive
+matching procedure \verb+match+ are all members of namespace \verb+boost::detail+.
+
+The functions of the public interface are all defined in namespace \verb+boost+ and their
+documentation will follow in the sections bellow.
+
+\subsection{Functions for Graph Sub-Graph Isomorphism Testing}
+
+\begin{lstlisting}
+// Non-named parameter version
+template <typename GraphSmall,
+ typename GraphLarge,
+ typename IndexMapSmall,
+ typename IndexMapLarge,
+ typename VertexOrderSmall,
+ typename EdgeCompatibilityPredicate,
+ typename VertexCompatibilityPredicate,
+ typename SubGraphIsoMapCallBack>
+bool vf2_sub_graph_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,
+ EdgeCompatibilityPredicate edge_comp,
+ VertexCompatibilityPredicate vertex_comp)
+\end{lstlisting}
+
+
+\begin{lstlisting}
+// Named parameter interface of vf2_sub_graph_iso
+template <typename GraphSmall,
+ typename GraphLarge,
+ typename VertexOrderSmall,
+ typename SubGraphIsoMapCallBack,
+ typename Param,
+ typename Tag,
+ typename Rest>
+bool vf2_sub_graph_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)
+\end{lstlisting}
+
+
+\begin{lstlisting}
+// All default interface for vf2_sub_graph_iso
+template <typename GraphSmall,
+ typename GraphLarge,
+ typename SubGraphIsoMapCallBack>
+bool vf2_sub_graph_iso(const GraphSmall& graph_small,
+ const GraphLarge& graph_large,
+ SubGraphIsoMapCallBack user_callback)
+\end{lstlisting}
+
+This algorithm finds all graph-subgraph isomorphism mappings between graphs
+\verb+graph_small+ and \verb+graph_large+ and outputs them to \verb+user_callback+.
+It continues until \verb+user_callback+ returns true or the search space has
+been fully explored.\\
+\verb+EdgeCompatibilityPredicate+ and \verb+VertexCompatibilityPredicate+
+predicates are used to test whether edges and vertices are compatible.
+By default \verb+always_compatible+ is used, which returns true for any pair of
+vertices or edges.
+
+\subsubsection*{Parameters}
+
+\begin{itemize}
+
+\item[IN:] \verb+const GraphSmall& graph_small+ The (first) smaller graph (fewer vertices)
+of the pair to be tested for isomorphism. The type \verb+GraphSmall+ must be a
+model of {\em Vertex List Graph}, {\em Bidirectional Graph}, {\em Edge List
+Graph} and {\em Adjacency Matrix}.
+
+
+\item[IN:] \verb+const GraphLarge& graph_large+ The (second) larger graph to be tested.
+Type \verb+GraphLarge+ must be a model of
+{\em Vertex List Graph}, {\em Bidirectional Graph}, {\em Edge List Graph} and
+{\em Adjacency Matrix}.
+
+\item[OUT:] \verb+SubGraphIsoMapCallBack user_callback+ A function object to be
+called when a graph-subgraph isomorphism has been discovered. The
+\verb+operator()+ must have following form:
+\begin{lstlisting}
+template <typename CorrespondenceMap1To2,
+ typename CorrespondenceMap2To1>
+bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1 g) const
+\end{lstlisting}
+
+Both the \verb+CorrespondenceMap1To2+ and \verb+CorresondenceMap2To1+ types
+are models of {\em Readable Property Map} and map equivalent vertices across
+the two graphs given to \verb+vf2_sub_graph_iso+ (or \verb+vf2_graph_iso+). An
+example is given below.
+
+Returning false from the callback will abort the search immediately. Otherwise,
+the entire search space will be explored.
+
+
+\item[IN:] \verb+const VertexOrderSmall& vertex_order_small+ The ordered
+vertices of the smaller graph \verb+graph_small+. During the matching process the
+vertices are examined in the order given by \verb+vertex_order_small+. Type
+\verb+VertexOrderSmall+ must be a model of \verb+ContainerConcept+ with value
+type \verb+graph_traits<GraphSmall>::vertex_descriptor+.
+\\
+{\em Default:} The vertices are ordered by multiplicity of in/out degree.
+
+\end{itemize}
+
+\subsubsection*{Named Parameters}
+
+\begin{itemize}
+
+\item[IN:] \verb+vertex_index1(IndexMapSmall index_map_small)+
+This maps each vertex to an integer in the range \verb+[0, num_vertices(graph_small))+.
+\\Type \verb+IndexMapSmall+ must be a model of {\em Readable Property Map}.
+\\
+{\em Default:} \verb+get(vertex_index, graph_small)+
+
+\item[IN:] \verb+vertex_index2(IndexMapLarge index_map_large)+
+This maps each vertex to an integer in the range \verb+[0, num_vertices(graph_large))+.
+\\Type \verb+IndexMapLarge+ must be a model of {\em Readable Property Map}.
+\\
+{\em Default:} \verb+get(vertex_index, graph_large)+
+
+\item[IN:] \verb+edges_equivalent(EdgeCompatibilityPredicate edge_comp)+
+This function object is used to determine if edges between the two graphs
+\verb+graph_small+ and \verb+graph_large+ are compatible.\\
+Type \verb+EdgeCompatiblePredicate+ must be a model of {\em Binary
+Predicate} and have argument types of
+\verb+graph_traits<GraphSmall>::edge_descriptor+ and
+\verb+graph_traits<GraphLarge>::edge_descriptor+. A return value of true
+indicates that the edges are compatible.\\
+{\em Default:} \verb+always_compatible+
+
+\item[IN:] \verb+vertices_equivalent(VertexCompatibilityPredicate vertex_comp)+
+This function object is used to determine if vertices between the two graphs
+\verb+graph_small+ and \verb+graph_large+ are compatible.\\
+Type \verb+VertexCompatiblePredicate+ must be a model of {\em Binary
+Predicate} and have argument types of\\
+\verb+graph_traits<GraphSmall>::vertex_descriptor+ and\\
+\verb+graph_traits<GraphLarge>::vertex_descriptor+. A return value of true
+indicates that the vertices are compatible.
+\\
+{\em Default:} \verb+always_compatible+
+
+\end{itemize}
+
+
+\subsection{Functions for Isomorphism Testing}
+
+Non-named parameter, named-parameter and all default parameter versions of
+function
+\begin{lstlisting}
+vf2_graph_iso(...)
+\end{lstlisting}
+
+for isomorphism testing take the same parameters as the corresponding
+functions \verb+vf2_sub_graph_iso+. The algorithm finds all isomorphism
+mappings between graphs \verb+graph1+ and \verb+graph2+ and outputs them to
+\verb+user_callback+. It continues until \verb+user_callback+ returns true
+or the search space has been fully explored. As before,
+\verb+EdgeCompatibilityPredicate+ and\\
+\verb+VertexCompatibilityPredicate+
+predicates are used to test whether edges and vertices are compatible with
+\verb+always_compatible+ as default.
+
+\subsection{Utility Functions and Structs}
+
+\begin{lstlisting}
+template <typename PropertyMap1,
+ typename PropertyMap2>
+property_map_compatible<PropertyMap1, PropertyMap2>
+make_property_map_compatible(const PropertyMap1 property_map1,
+ const PropertyMap2 property_map2)
+\end{lstlisting}
+Returns a binary predicate function object \\
+(\verb+property_map_compatible<PropertyMap1, PropertyMap2>+) that compares
+vertices or edges between graphs using property maps.
+
+
+\begin{lstlisting}
+struct always_compatible
+\end{lstlisting}
+A binary function object that returns true for any pair of items.
+
+
+\begin{lstlisting}
+template <typename Graph1,
+ typename Graph2>
+struct vf2_print_callback
+\end{lstlisting}
+Callback function object that prints out the correspondences between vertices
+of \verb+Graph1+ and \verb+Graph2+. The constructor takes the two graphs $G_1$
+and $G_2$ and an optional \verb+bool+ parameter as arguments. If the latter is
+set to \verb+true+, the callback function will verify the mapping before outputting
+it to standard output.
+
+\begin{lstlisting}
+// Verifies a graph (sub)graph isomorphism map
+template<typename Graph1,
+ typename Graph2,
+ typename CorresponenceMap1To2,
+ typename EdgeCompatibilityPredicate,
+ typename VertexCompatibilityPredicate>
+inline bool verify_vf2_sub_graph_iso(const Graph1& graph1,
+ const Graph2& graph2,
+ const CorresponenceMap1To2 f,
+ EdgeCompatibilityPredicate edge_comp,
+ VertexCompatibilityPredicate vertex_comp)
+\end{lstlisting}
+
+
+\begin{lstlisting}
+// Variant of verify_sub_graph_iso with all default parameters
+template<typename Graph1,
+ typename Graph2,
+ typename CorresponenceMap1To2>
+inline bool verify_vf2_sub_graph_iso(const Graph1& graph1,
+ const Graph2& graph2,
+ const CorresponenceMap1To2 f)
+\end{lstlisting}
+
+This function can be used to verify a (sub)graph isomorphism mapping {\em f}.
+The parameters are akin to function \verb+vf2_sub_graph_iso+
+(\verb+vf2_graph_iso+).
+
+
+\subsection{Complexity}
+
+Spatial and time complexity are given in \cite{cordella+2004}. The spatial
+complexity of {\sc VF2} is of order $O(V)$, where $V$ is the (maximum) number
+of vertices of the two graphs. Time complexity is $O(V^2)$ in the best case and
+$O(V!V)$ in the worst case.
+
+\subsection{A Graph Sub-Graph Isomorphism Example}
+
+In the example below, a small graph \verb+graph1+ and a larger graph
+\verb+graph2+ are defined. \\ \verb+vf2_sub_graph_iso+ computes all the
+mappings between the two graphs and outputs them via \verb+callback+.
+
+
+\begin{lstlisting}
+typedef adjacency_list<vecS, vecS, bidirectionalS> graph_type;
+
+// Build graph1
+int num_vertices1 = 8; graph_type graph1(num_vertices1);
+add_edge(0, 6, graph1); add_edge(0, 7, graph1);
+add_edge(1, 5, graph1); add_edge(1, 7, graph1);
+add_edge(2, 4, graph1); add_edge(2, 5, graph1); add_edge(2, 6, graph1);
+add_edge(3, 4, graph1);
+
+// Build graph2
+int num_vertices2 = 9; graph_type graph2(num_vertices2);
+add_edge(0, 6, graph2); add_edge(0, 8, graph2);
+add_edge(1, 5, graph2); add_edge(1, 7, graph2);
+add_edge(2, 4, graph2); add_edge(2, 7, graph2); add_edge(2, 8, graph2);
+add_edge(3, 4, graph2); add_edge(3, 5, graph2); add_edge(3, 6, graph2);
+
+// true instructs callback to verify a map using
+// verify_vf2_sub_graph_iso
+vf2_print_callback<graph_type, graph_type> callback(graph1, graph2, true);
+
+bool ret = vf2_sub_graph_iso(graph1, graph2, callback);
+\end{lstlisting}
+
+\appendix
+\section{Testing}
+
+Also included are \verb+vf2_sub_graph_iso_gviz_example.cpp+ and a Scilab \newline
+(\verb+http://www.scilab.org/+) script \verb+vf2_random_graphs.sce+ for testing the
+implementation. The script generates pairs of simple graphs of (possibly) different
+size, such that there exists at least one (sub)graph isomorphism mapping
+between the two graphs. The graphs are written to files \verb+graph_small.dot+
+and \verb+graph_large.dot+ using the Graphviz {\em DOT} language
+(\verb+http://www.graphviz.org+). The following parameters can be used to
+control the output:
+
+\begin{itemize}
+
+\item \verb+nbig+ Dimension of the large adjacency matrix
+\item \verb+nsmall+ Dimension of the small adjacency matrix
+\item \verb+density+ Density of the non-zero entries (of an initial square
+matrix with dimension \verb+nbig+)
+\item \verb+directed+ If set to one, a pair of directed graphs is generated,
+otherwise undirected graphs are produced.
+\item \verb+loops+ If set to one, self-loops are allowed, otherwise self-loops
+are excluded.
+\end{itemize}
+
+The generated dot-files specifying the graphs can be given as command line
+arguments to the executable test program, which uses boost's GraphViz input
+parser to build the graphs. The graphs are then tested for (sub)graph
+isomorphism. The isomorphism mappings are verified and written to standard
+output.
+
+To build the test executable, you will need to build and link against the
+"boost\_graph" and "boost\_regex" libraries, \cf also \verb+read_graphviz+.
+
+%%%%%%%%%%%%%%%
+% Bibliography
+%%%%%%%%%%%%%%
+\begin{thebibliography}{10}
+
+\bibitem{cordella+2001} L. P. Cordella, P. Foggia, C. Sansone, and M. Vento,
+ ``An improved algorithm for matching large graphs,'' \emph{In: 3rd IAPR-TC15
+ Workshop on Graph-based Representations in Pattern Recognition, Cuen},
+ pp. 149--159, 2001.
+
+\bibitem{cordella+2004} L. P. Cordella, P. Foggia, C. Sansone, and M. Vento,
+ ``A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs,''
+ \emph{IEEE Trans. Pattern Anal. Mach. Intell.}, vol. 26, no. 10,
+ pp. 1367--1372, 2004
+
+\end{thebibliography}
+
+
+\end{document}

Modified: trunk/libs/graph/example/Jamfile.v2
==============================================================================
--- trunk/libs/graph/example/Jamfile.v2 (original)
+++ trunk/libs/graph/example/Jamfile.v2 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -44,3 +44,10 @@
exe strong-components : strong-components.cpp ;
exe subgraph : subgraph.cpp ;
exe subgraph_properties : subgraph_properties.cpp ;
+exe vf2_sub_graph_iso_csr_example : vf2_sub_graph_iso_csr_example.cpp ;
+exe vf2_sub_graph_iso_example : vf2_sub_graph_iso_example.cpp ;
+exe vf2_sub_graph_iso_grd_example : vf2_sub_graph_iso_grd_example.cpp ;
+exe vf2_sub_graph_iso_gviz_example : vf2_sub_graph_iso_gviz_example.cpp ../build//boost_graph ;
+exe vf2_sub_graph_iso_multi_example : vf2_sub_graph_iso_multi_example.cpp ;
+exe vf2_sub_graph_iso_undir_example : vf2_sub_graph_iso_undir_example.cpp ;
+

Added: trunk/libs/graph/example/vf2_random_graphs.sce
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/vf2_random_graphs.sce 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -0,0 +1,96 @@
+//=======================================================================
+// Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi_at_[hidden])
+//
+// 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)
+//=======================================================================
+
+// A script to generate simple pairs of graphs of (possibly) different
+// size, such that there exists (at least) one (sub)graph isomorphism mapping
+// between the two graphs. The graphs are written to files graph_small.dot
+// and graph_large.dot using the Graphviz DOT language http://www.graphviz.org.
+// The following parameters can be used to control the output:
+//
+// - nbig: Dimension of the large adjacency matrix
+// - nsmall: Dimension of the small adjacency matrix
+// - density: Density of the non-zero entries (of an initial square
+// matrix with dimension nbig)
+// - directed: If set to one, a pair of directed graphs is generated,
+// otherwise undirected graphs are produced.
+// - loops: If set to one, self-loops are allowed, otherwise self-loops
+// are excluded.
+//
+// The generated dot-files specifying the graphs can be given as command line
+// arguments to the executable test program (vf2_sub_graph_iso_gviz_example.cpp),
+// which uses boost's GraphViz input parser to build the graphs.
+
+clear;
+
+directed=0; // Set to 1 to generate a directed graph, otherwise an
+ // undirected graph is generated
+
+loops=1; // Set to 1 to allow self-loops, otherwise loops are excluded
+
+nbig=6; density=0.4; // Size and density of non-zero elements of the large matrix
+nsmall=4; // Size of the small matrix: nsmall<=nbig
+
+// Create a matrix with ~density * nbig^2 non-zero elements
+M=full(sprand(nbig, nbig, density, "uniform"));
+NZ=find(M<>0);
+M(NZ)=1;
+
+if directed <> 1 then
+ M=triu(M);
+end
+
+if loops <> 1 then
+ M=M-eye(M).*M
+end
+
+indices=linspace(1, nbig, nbig)';
+
+// Random row and column permutations
+indices_perm=grand(1, 'prm', indices);
+
+M_perm=M(indices_perm, indices_perm);
+M_perm=M_perm(1:nsmall, 1:nsmall);
+
+function write_digraph(file_name, Mat)
+ fd = mopen(file_name, "w");
+ n = size(Mat, "r");
+ mfprintf(fd, "digraph G {\n");
+ for i = 1:n
+ for j = 1:n
+ if Mat(i,j)<>0 then
+ mfprintf(fd, "node%u -> node%u;\n", i, j);
+ end
+ end
+ end
+ mfprintf(fd, "}\n");
+ mclose(fd);
+endfunction
+
+function write_graph(file_name, Mat)
+ fd = mopen(file_name, "w");
+ n = size(Mat, "r");
+ mfprintf(fd, "graph G {\n");
+ for i = 1:n
+ for j = 1:n
+ if Mat(i,j)<>0 then
+ mfprintf(fd, "node%u -- node%u;\n", i, j);
+ end
+ end
+ end
+ mfprintf(fd, "}\n");
+ mclose(fd);
+endfunction
+
+// Write graphs:
+if directed <> 1 then
+ write_graph("graph_large.dot", M);
+ write_graph("graph_small.dot", M_perm);
+else
+ write_digraph("graph_large.dot", M);
+ write_digraph("graph_small.dot", M_perm);
+end

Added: trunk/libs/graph/example/vf2_sub_graph_iso_csr_example.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/vf2_sub_graph_iso_csr_example.cpp 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -0,0 +1,45 @@
+//=======================================================================
+// Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi_at_[hidden])
+//
+// 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)
+//=======================================================================
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/compressed_sparse_row_graph.hpp>
+#include <boost/graph/vf2_sub_graph_iso.hpp>
+using namespace boost;
+
+
+int main() {
+ typedef adjacency_list<vecS, vecS, bidirectionalS> graph_raw_t;
+
+ // Build graph_raw1
+ int num_vertices1 = 8; graph_raw_t graph_raw1(num_vertices1);
+ add_edge(0, 6, graph_raw1); add_edge(0, 7, graph_raw1);
+ add_edge(1, 5, graph_raw1); add_edge(1, 7, graph_raw1);
+ add_edge(2, 4, graph_raw1); add_edge(2, 5, graph_raw1); add_edge(2, 6, graph_raw1);
+ add_edge(3, 4, graph_raw1);
+
+ // Build graph_raw2
+ int num_vertices2 = 9; graph_raw_t graph_raw2(num_vertices2);
+ add_edge(0, 6, graph_raw2); add_edge(0, 8, graph_raw2);
+ add_edge(1, 5, graph_raw2); add_edge(1, 7, graph_raw2);
+ add_edge(2, 4, graph_raw2); add_edge(2, 7, graph_raw2); add_edge(2, 8, graph_raw2);
+ add_edge(3, 4, graph_raw2); add_edge(3, 5, graph_raw2); add_edge(3, 6, graph_raw2);
+
+ typedef compressed_sparse_row_graph<bidirectionalS> graph_csr_t;
+
+ graph_csr_t graph1(graph_raw1);
+ graph_csr_t graph2(graph_raw2);
+
+ // true instructs callback to verify a map using
+ // verify_vf2_sub_graph_iso
+ vf2_print_callback<graph_csr_t, graph_csr_t> callback(graph1, graph2, true);
+
+ bool ret = vf2_sub_graph_iso(graph1, graph2, callback);
+ (void)ret;
+
+ return 0;
+}

Added: trunk/libs/graph/example/vf2_sub_graph_iso_example.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/vf2_sub_graph_iso_example.cpp 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -0,0 +1,39 @@
+//=======================================================================
+// Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi_at_[hidden])
+//
+// 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)
+//=======================================================================
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/vf2_sub_graph_iso.hpp>
+using namespace boost;
+
+
+int main() {
+ typedef adjacency_list<vecS, vecS, bidirectionalS> graph_type;
+
+ // Build graph1
+ int num_vertices1 = 8; graph_type graph1(num_vertices1);
+ add_edge(0, 6, graph1); add_edge(0, 7, graph1);
+ add_edge(1, 5, graph1); add_edge(1, 7, graph1);
+ add_edge(2, 4, graph1); add_edge(2, 5, graph1); add_edge(2, 6, graph1);
+ add_edge(3, 4, graph1);
+
+ // Build graph2
+ int num_vertices2 = 9; graph_type graph2(num_vertices2);
+ add_edge(0, 6, graph2); add_edge(0, 8, graph2);
+ add_edge(1, 5, graph2); add_edge(1, 7, graph2);
+ add_edge(2, 4, graph2); add_edge(2, 7, graph2); add_edge(2, 8, graph2);
+ add_edge(3, 4, graph2); add_edge(3, 5, graph2); add_edge(3, 6, graph2);
+
+ // true instructs callback to verify a map using
+ // verify_vf2_sub_graph_iso
+ vf2_print_callback<graph_type, graph_type> callback(graph1, graph2, true);
+
+ bool ret = vf2_sub_graph_iso(graph1, graph2, callback);
+ (void)ret;
+
+ return 0;
+}

Added: trunk/libs/graph/example/vf2_sub_graph_iso_grd_example.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/vf2_sub_graph_iso_grd_example.cpp 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -0,0 +1,36 @@
+//=======================================================================
+// Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi_at_[hidden])
+//
+// 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)
+//=======================================================================
+
+#include <boost/array.hpp>
+#include <boost/graph/grid_graph.hpp>
+#include <boost/graph/vf2_sub_graph_iso.hpp>
+using namespace boost;
+
+
+int main() {
+
+ typedef grid_graph<2> graph_type;
+ // Build graph1
+ // Define dimension lengths, a 2x2 in this case
+ boost::array<std::size_t, 2> lengths1 = { { 2, 2 } };
+ graph_type graph1(lengths1);
+
+ // Build graph2
+ // Define dimension lengths, a 2x3 in this case
+ boost::array<std::size_t, 2> lengths2 = { { 2, 3 } };
+ graph_type graph2(lengths2);
+
+ // true instructs callback to verify a map using
+ // verify_vf2_sub_graph_iso
+ vf2_print_callback<graph_type, graph_type> callback(graph1, graph2, true);
+
+ bool ret = vf2_sub_graph_iso(graph1, graph2, callback);
+ (void)ret;
+
+ return 0;
+}

Added: trunk/libs/graph/example/vf2_sub_graph_iso_gviz_example.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/vf2_sub_graph_iso_gviz_example.cpp 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -0,0 +1,143 @@
+//=======================================================================
+// Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi_at_[hidden])
+//
+// 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)
+//=======================================================================
+
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <vector>
+using namespace std;
+
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/graphviz.hpp>
+#include <boost/graph/vf2_sub_graph_iso.hpp>
+using namespace boost;
+
+
+// Define a print_callback
+template <typename Graph1,
+ typename Graph2,
+ typename PropertyMap1,
+ typename PropertyMap2>
+struct print_callback {
+
+ print_callback(const Graph1& graph1, const Graph2& graph2,
+ PropertyMap1 p_map1, PropertyMap2 p_map2,
+ bool verify = false)
+ : graph1_(graph1), graph2_(graph2),
+ p_map1_(p_map1), p_map2_(p_map2),
+ verify_(verify) {}
+
+ template <typename CorrespondenceMap1To2,
+ typename CorrespondenceMap2To1>
+ bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {
+
+ if (verify_)
+ std::cout << "Verify: " << std::boolalpha
+ << verify_vf2_sub_graph_iso(graph1_, graph2_, f)
+ << std::endl;
+
+ // Print sub graph isomorphism map
+ BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
+ std::cout << '(' << get(p_map1_,v) << ", "
+ << get(p_map2_, get(f, v)) << ") ";
+
+ std::cout << std::endl;
+
+ return true;
+ }
+
+private:
+ const Graph1& graph1_;
+ const Graph2& graph2_;
+
+ const PropertyMap1& p_map1_;
+ const PropertyMap2& p_map2_;
+
+ const bool verify_;
+};
+
+
+int main(int argc, char** argv) {
+
+ if (argc != 3) {
+ cerr << "usage: " << argv[0] << " graph_small graph_large" << endl;
+ return EXIT_FAILURE;
+ }
+ ifstream graph_small_file(argv[1]);
+ ifstream graph_large_file(argv[2]);
+ if (!graph_small_file || !graph_large_file) {
+ cerr << "Files not found" << endl;
+ return EXIT_FAILURE;
+ }
+
+
+ // Vertex properties
+ typedef property <vertex_name_t, std::string> vertex_p;
+ // adjacency_list-based type
+#if 0
+ typedef adjacency_list <vecS, vecS, bidirectionalS, vertex_p> graph_t;
+#else
+ typedef adjacency_list <vecS, vecS, undirectedS, vertex_p> graph_t;
+#endif
+
+ // Construct an empty graph_small and prepare the dynamic_property_maps.
+ graph_t graph_small(0);
+ dynamic_properties dp_small;
+
+ property_map<graph_t, vertex_name_t>::type name_small =
+ get(vertex_name, graph_small);
+ dp_small.property("node_id", name_small);
+
+ // Read graph_small
+ bool status = read_graphviz(graph_small_file, graph_small, dp_small, "node_id");
+ (void)status;
+
+ // Construct an empty graph_large and prepare the dynamic_property_maps,
+ // following the read_graphviz example
+ graph_t graph_large(0);
+ dynamic_properties dp_large;
+
+ property_map<graph_t, vertex_name_t>::type name_large =
+ get(vertex_name, graph_large);
+ dp_large.property("node_id", name_large);
+
+ // Read graph_large
+ status = read_graphviz(graph_large_file, graph_large, dp_large, "node_id");
+
+
+ // Create the call_back function
+ typedef property_map<graph_t, vertex_name_t>::type p_map_t;
+ print_callback<graph_t, graph_t, p_map_t, p_map_t> callback(graph_small, graph_large,
+ name_small, name_large, true);
+
+ // Compute the sub-graph isomorphism mappings
+#if 1
+ bool ret = vf2_sub_graph_iso(graph_small, graph_large, callback);
+ //bool ret = vf2_graph_iso(graph_small, graph_large, callback);
+#else
+ typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
+ typedef property_map<graph_t, vertex_index_t>::type index_map_t;
+
+ index_map_t index_small = get(vertex_index, graph_small);
+ index_map_t index_large = get(vertex_index, graph_large);
+
+ graph_traits<graph_t>::vertex_iterator vi, vi_end;
+
+ vector<vertex_t> vertex_order1;
+ for (tie(vi, vi_end) = vertices(graph_small); vi != vi_end; ++vi)
+ vertex_order1.push_back(*vi);
+
+ bool ret = vf2_sub_graph_iso(graph_small, graph_large, callback, vertex_order1,
+ vertex_index1_map(index_small).vertex_index2_map(index_large));
+
+#endif
+ (void)ret;
+
+ return 0;
+}

Added: trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -0,0 +1,145 @@
+//=======================================================================
+// Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi_at_[hidden])
+//
+// 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)
+//=======================================================================
+
+#include <string>
+#include <vector>
+#include <utility>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/vf2_sub_graph_iso.hpp>
+using namespace boost;
+
+
+template <typename Graph1,
+ typename Graph2,
+ typename EdgeCompatibilityPredicate,
+ typename VertexCompatibilityPredicate>
+struct my_print_callback {
+
+ my_print_callback(const Graph1& graph1, const Graph2& graph2,
+ EdgeCompatibilityPredicate edge_comp,
+ VertexCompatibilityPredicate vertex_comp)
+ : graph1_(graph1), graph2_(graph2), edge_comp_(edge_comp), vertex_comp_(vertex_comp) {}
+
+ template <typename CorrespondenceMap1To2,
+ typename CorrespondenceMap2To1>
+ bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {
+
+ std::cout << "Verify: " << std::boolalpha
+ << verify_vf2_sub_graph_iso(graph1_, graph2_, f, edge_comp_, vertex_comp_)
+ << std::endl;
+
+ // Print sub graph isomorphism map
+ BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
+ std::cout << '(' << v << ", " << get(f, v) << ") ";
+
+ std::cout << std::endl;
+
+ return true;
+ }
+
+private:
+ const Graph1& graph1_;
+ const Graph2& graph2_;
+ EdgeCompatibilityPredicate edge_comp_;
+ VertexCompatibilityPredicate vertex_comp_;
+};
+
+
+
+
+int main() {
+ typedef property<edge_name_t, char> edge_property;
+ typedef property<vertex_name_t, char> vertex_property;
+
+ //typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph_type;
+ typedef adjacency_list<vecS, vecS, undirectedS, vertex_property, edge_property> graph_type;
+ //typedef adjacency_list<setS, vecS, bidirectionalS, vertex_property, edge_property> graph_type;
+ //typedef adjacency_list<setS, vecS, undirectedS, vertex_property, edge_property> graph_type;
+
+ // Build graph1
+ graph_type graph1;
+
+ add_vertex(vertex_property('a'), graph1);
+ add_vertex(vertex_property('a'), graph1);
+ add_vertex(vertex_property('a'), graph1);
+
+ add_edge(0, 1, edge_property('b'), graph1);
+ add_edge(0, 1, edge_property('b'), graph1);
+ add_edge(0, 1, edge_property('d'), graph1);
+
+ add_edge(1, 2, edge_property('s'), graph1);
+
+ add_edge(2, 2, edge_property('l'), graph1);
+ add_edge(2, 2, edge_property('l'), graph1);
+
+
+ // Build graph2
+ graph_type graph2;
+
+ add_vertex(vertex_property('a'), graph2);
+ add_vertex(vertex_property('a'), graph2);
+ add_vertex(vertex_property('a'), graph2);
+ add_vertex(vertex_property('a'), graph2);
+ add_vertex(vertex_property('a'), graph2);
+ add_vertex(vertex_property('a'), graph2);
+
+ add_edge(0, 1, edge_property('a'), graph2);
+ add_edge(0, 1, edge_property('a'), graph2);
+ add_edge(0, 1, edge_property('b'), graph2);
+
+
+ add_edge(1, 2, edge_property('s'), graph2);
+
+ add_edge(2, 3, edge_property('b'), graph2);
+ add_edge(2, 3, edge_property('d'), graph2);
+ add_edge(2, 3, edge_property('b'), graph2);
+
+ add_edge(3, 4, edge_property('s'), graph2);
+
+ add_edge(4, 4, edge_property('l'), graph2);
+ add_edge(4, 4, edge_property('l'), graph2);
+
+ add_edge(4, 5, edge_property('c'), graph2);
+ add_edge(4, 5, edge_property('c'), graph2);
+ add_edge(4, 5, edge_property('c'), graph2);
+
+ add_edge(5, 0, edge_property('s'), graph2);
+
+ // create predicates
+ typedef property_map<graph_type, vertex_name_t>::type vertex_name_map_t;
+
+ typedef property_map_compatible<vertex_name_map_t, vertex_name_map_t> vertex_comp_t;
+ vertex_comp_t vertex_comp =
+ make_property_map_compatible(get(vertex_name, graph1), get(vertex_name, graph2));
+
+ typedef property_map<graph_type, edge_name_t>::type edge_name_map_t;
+
+ typedef property_map_compatible<edge_name_map_t, edge_name_map_t> edge_comp_t;
+ edge_comp_t edge_comp =
+ make_property_map_compatible(get(edge_name, graph1), get(edge_name, graph2));
+
+
+ graph_traits<graph_type>::vertex_iterator vi, vi_end;
+
+ // define the order in whcih vertices of graph1 are examined
+ std::vector<graph_traits<graph_type>::vertex_descriptor> vertex_order1;
+ for (tie(vi, vi_end) = vertices(graph1); vi != vi_end; ++vi)
+ vertex_order1.push_back(*vi);
+
+ // true instructs callback to verify a map using
+ // verify_vf2_sub_graph_iso
+ my_print_callback<graph_type, graph_type, edge_comp_t, vertex_comp_t>
+ callback(graph1, graph2, edge_comp, vertex_comp);
+
+ bool ret = vf2_sub_graph_iso(graph1, graph2, callback, vertex_order1,
+ edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
+
+ (void)ret;
+
+ return 0;
+}

Added: trunk/libs/graph/example/vf2_sub_graph_iso_undir_example.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/vf2_sub_graph_iso_undir_example.cpp 2012-12-05 14:28:12 EST (Wed, 05 Dec 2012)
@@ -0,0 +1,73 @@
+//=======================================================================
+// Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi_at_[hidden])
+//
+// 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)
+//=======================================================================
+
+#include <iostream>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/vf2_sub_graph_iso.hpp>
+using namespace boost;
+
+
+int main() {
+ typedef adjacency_list<vecS, vecS, bidirectionalS> graph_bidir_t;
+
+ // Build graph1
+ int num_vertices1 = 8; graph_bidir_t graph1(num_vertices1);
+ add_edge(0, 6, graph1); add_edge(0, 7, graph1);
+ add_edge(1, 5, graph1); add_edge(1, 7, graph1);
+ add_edge(2, 4, graph1); add_edge(2, 5, graph1); add_edge(2, 6, graph1);
+ add_edge(3, 4, graph1);
+ // reversed edges
+ add_edge(6, 0, graph1); add_edge(7, 0, graph1);
+ add_edge(5, 1, graph1); add_edge(7, 1, graph1);
+ add_edge(4, 2, graph1); add_edge(5, 2, graph1); add_edge(6, 2, graph1);
+ add_edge(4, 3, graph1);
+
+ add_edge(7, 7, graph1);
+ add_edge(7, 7, graph1);
+
+
+ // Build graph2
+ int num_vertices2 = 9; graph_bidir_t graph2(num_vertices2);
+ add_edge(0, 6, graph2); add_edge(0, 8, graph2);
+ add_edge(1, 5, graph2); add_edge(1, 7, graph2);
+ add_edge(2, 4, graph2); add_edge(2, 7, graph2); add_edge(2, 8, graph2);
+ add_edge(3, 4, graph2); add_edge(3, 5, graph2); add_edge(3, 6, graph2);
+ // reversed edges
+ add_edge(6, 0, graph2); add_edge(8, 0, graph2);
+ add_edge(5, 1, graph2); add_edge(7, 1, graph2);
+ add_edge(4, 2, graph2); add_edge(7, 2, graph2); add_edge(8, 2, graph2);
+ add_edge(4, 3, graph2); add_edge(5, 3, graph2); add_edge(6, 3, graph2);
+
+ add_edge(5, 5, graph2);
+ add_edge(5, 5, graph2);
+
+ // Build graph3
+ typedef adjacency_list<vecS, vecS, undirectedS> graph_undir_t;
+
+ int num_vertices3 = 9; graph_undir_t graph3(num_vertices3);
+ add_edge(0, 6, graph3); add_edge(0, 8, graph3);
+ add_edge(1, 5, graph3); add_edge(1, 7, graph3);
+ add_edge(2, 4, graph3); add_edge(2, 7, graph3); add_edge(2, 8, graph3);
+ add_edge(3, 4, graph3); add_edge(3, 5, graph3); add_edge(3, 6, graph3);
+
+ add_edge(5, 5, graph3);
+
+ // true instructs callback to verify a map using
+ // verify_vf2_sub_graph_iso
+ vf2_print_callback<graph_bidir_t, graph_bidir_t> callback12(graph1, graph2, true);
+
+ bool ret = vf2_sub_graph_iso(graph1, graph2, callback12);
+ std::cout << std::endl;
+ std::cout << std::endl;
+
+ vf2_print_callback<graph_bidir_t, graph_undir_t> callback13(graph1, graph3, true);
+ ret = vf2_sub_graph_iso(graph1, graph3, callback13);
+ (void)ret;
+
+ return 0;
+}

Next message: dnljms_at_[hidden]: "[Boost-commit] svn:boost r81726 - trunk/libs/context/doc"
Previous message: jewillco_at_[hidden]: "[Boost-commit] svn:boost r81724 - trunk/boost/graph/detail"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk