|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r82007 - in trunk: boost/graph libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2012-12-15 20:51:53
Author: jewillco
Date: 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
New Revision: 82007
URL: http://svn.boost.org/trac/boost/changeset/82007
Log:
Added updates from Flavio De Lorenzi to vf2_sub_graph_iso code
Added:
trunk/libs/graph/test/vf2_sub_graph_iso_test.cpp (contents, props changed)
Removed:
trunk/libs/graph/doc/vf2_sub_graph_iso_impl.pdf
trunk/libs/graph/doc/vf2_sub_graph_iso_impl.tex
trunk/libs/graph/example/vf2_random_graphs.sce
trunk/libs/graph/example/vf2_sub_graph_iso_csr_example.cpp
trunk/libs/graph/example/vf2_sub_graph_iso_grd_example.cpp
trunk/libs/graph/example/vf2_sub_graph_iso_gviz_example.cpp
trunk/libs/graph/example/vf2_sub_graph_iso_undir_example.cpp
Text files modified:
trunk/boost/graph/vf2_sub_graph_iso.hpp | 357 ++++++++++++++++--------------------
trunk/libs/graph/doc/vf2_sub_graph_iso.html | 391 +++++++++++++++------------------------
trunk/libs/graph/example/Jamfile.v2 | 4
trunk/libs/graph/example/vf2_sub_graph_iso_example.cpp | 13
trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp | 92 +-------
trunk/libs/graph/test/Jamfile.v2 | 1
6 files changed, 338 insertions(+), 520 deletions(-)
Modified: trunk/boost/graph/vf2_sub_graph_iso.hpp
==============================================================================
--- trunk/boost/graph/vf2_sub_graph_iso.hpp (original)
+++ trunk/boost/graph/vf2_sub_graph_iso.hpp 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
@@ -24,7 +24,9 @@
#include <boost/concept_check.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/mcgregor_common_subgraphs.hpp> // for always_equivalent
#include <boost/graph/named_function_params.hpp>
+#include <boost/type_traits/has_less.hpp>
#include <boost/mpl/int.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/tuple/tuple.hpp>
@@ -36,73 +38,23 @@
#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) {}
+ vf2_print_callback(const Graph1& graph1, const Graph2& graph2)
+ : graph1_(graph1), graph2_(graph2) {}
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
+ // 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 << '(' << get(vertex_index_t(), graph1_, v) << ", "
+ << get(vertex_index_t(), graph1_, get(f, v)) << ") ";
std::cout << std::endl;
@@ -112,8 +64,6 @@
private:
const Graph1& graph1_;
const Graph2& graph2_;
-
- const bool verify_;
};
namespace detail {
@@ -332,25 +282,44 @@
};
+ // Used for bookkeeping of matched edges in equivalent_edge_exists
+ // (when dealing with multi-graphs)
+ template <typename Item, typename Enable = void>
+ struct memory {
+ void store(Item item) { items_.push_back(item); }
+ bool exists(Item item) const {
+ return (std::find(items_.begin(), items_.end(), item) != items_.end());
+ }
+
+ std::vector<Item> items_;
+ };
+
+
+ template <typename Item>
+ struct memory<Item, typename boost::enable_if<has_less<Item> >::type> {
+ void store(Item item) { items_.insert(item); }
+ bool exists(Item item) const {
+ return (items_.find(item) != items_.end());
+ }
+
+ std::set<Item> items_;
+ };
+
+
// 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;
+ struct equivalent_edge_exists {
+ typedef typename boost::graph_traits<Graph>::edge_descriptor edge_type;
template<typename EdgePredicate>
bool operator()(typename graph_traits<Graph>::vertex_descriptor s,
typename graph_traits<Graph>::vertex_descriptor t,
EdgePredicate is_valid_edge, const Graph& g) {
- 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);
+ BGL_FORALL_OUTEDGES_T(s, e, g, Graph) {
+ if ((target(e, g) == t) && is_valid_edge(e) && !edge_memory_.exists(e)) {
+ edge_memory_.store(e);
return true;
}
}
@@ -360,14 +329,11 @@
private:
- std::set<edge_iterator_type> matched_edges_;
+ memory<edge_type> edge_memory_;
};
template <typename Graph>
- struct compatible_edge_exists<Graph, typename boost::disable_if<is_multigraph<Graph> >::type> {
-
- compatible_edge_exists() {};
-
+ struct equivalent_edge_exists<Graph, typename boost::disable_if<is_multigraph<Graph> >::type> {
template<typename EdgePredicate>
bool operator()(typename graph_traits<Graph>::vertex_descriptor s,
typename graph_traits<Graph>::vertex_descriptor t,
@@ -391,18 +357,18 @@
// fixed edge e2
template <typename Graph1,
typename Graph2,
- typename EdgeCompatibilityPredicate>
+ typename EdgeEquivalencePredicate>
struct edge1_predicate {
- edge1_predicate(EdgeCompatibilityPredicate edge_comp,
+ edge1_predicate(EdgeEquivalencePredicate edge_comp,
typename graph_traits<Graph2>::edge_descriptor e2)
: edge_comp_(edge_comp), e2_(e2) {}
- bool operator()(typename graph_traits<Graph1>::edge_descriptor e1) const {
+ bool operator()(typename graph_traits<Graph1>::edge_descriptor e1) {
return edge_comp_(e1, e2_);
}
- EdgeCompatibilityPredicate edge_comp_;
+ EdgeEquivalencePredicate edge_comp_;
typename graph_traits<Graph2>::edge_descriptor e2_;
};
@@ -411,32 +377,32 @@
// fixed edge e1
template <typename Graph1,
typename Graph2,
- typename EdgeCompatibilityPredicate>
+ typename EdgeEquivalencePredicate>
struct edge2_predicate {
- edge2_predicate(EdgeCompatibilityPredicate edge_comp,
+ edge2_predicate(EdgeEquivalencePredicate edge_comp,
typename graph_traits<Graph1>::edge_descriptor e1)
: edge_comp_(edge_comp), e1_(e1) {}
- bool operator()(typename graph_traits<Graph2>::edge_descriptor e2) const {
+ bool operator()(typename graph_traits<Graph2>::edge_descriptor e2) {
return edge_comp_(e1_, e2);
}
- EdgeCompatibilityPredicate edge_comp_;
+ EdgeEquivalencePredicate edge_comp_;
typename graph_traits<Graph1>::edge_descriptor e1_;
};
- enum problem_selector { sub_graph_iso, isomorphism };
+ enum problem_selector { subgraph_iso, isomorphism };
// The actual state associated with both graphs
template<typename Graph1,
typename Graph2,
typename IndexMap1,
typename IndexMap2,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate,
- typename SubGraphIsoMapCallBack,
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename SubGraphIsoMapCallback,
problem_selector problem_selection>
class state {
@@ -454,8 +420,8 @@
IndexMap1 index_map1_;
- EdgeCompatibilityPredicate edge_comp_;
- VertexCompatibilityPredicate vertex_comp_;
+ EdgeEquivalencePredicate edge_comp_;
+ VertexEquivalencePredicate vertex_comp_;
base_state<Graph1, Graph2, IndexMap1, IndexMap2> state1_;
base_state<Graph2, Graph1, IndexMap2, IndexMap1> state2_;
@@ -465,7 +431,7 @@
// - 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 {
+ boost::mpl::int_<subgraph_iso>) const {
return a <= b;
}
@@ -484,8 +450,8 @@
state(const Graph1& graph1, const Graph2& graph2,
IndexMap1 index_map1, IndexMap2 index_map2,
- EdgeCompatibilityPredicate edge_comp,
- VertexCompatibilityPredicate vertex_comp)
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp)
: graph1_(graph1), graph2_(graph2),
index_map1_(index_map1),
edge_comp_(edge_comp), vertex_comp_(vertex_comp),
@@ -514,7 +480,7 @@
graph1_size_type term_in1_count = 0, term_out1_count = 0, rest1_count = 0;
{
- compatible_edge_exists<Graph2> edge2_exists;
+ equivalent_edge_exists<Graph2> edge2_exists;
BGL_FORALL_INEDGES_T(v_new, e1, graph1_, Graph1) {
vertex1_type v = source(e1, graph1_);
@@ -524,7 +490,7 @@
if (v != v_new)
w = state1_.core(v);
if (!edge2_exists(w, w_new,
- edge2_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(edge_comp_, e1),
+ edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e1),
graph2_))
return false;
@@ -540,7 +506,7 @@
}
{
- compatible_edge_exists<Graph2> edge2_exists;
+ equivalent_edge_exists<Graph2> edge2_exists;
BGL_FORALL_OUTEDGES_T(v_new, e1, graph1_, Graph1) {
vertex1_type v = target(e1, graph1_);
@@ -550,7 +516,7 @@
w = state1_.core(v);
if (!edge2_exists(w_new, w,
- edge2_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(edge_comp_, e1),
+ edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e1),
graph2_))
return false;
@@ -569,7 +535,7 @@
graph2_size_type term_out2_count = 0, term_in2_count = 0, rest2_count = 0;
{
- compatible_edge_exists<Graph1> edge1_exists;
+ equivalent_edge_exists<Graph1> edge1_exists;
BGL_FORALL_INEDGES_T(w_new, e2, graph2_, Graph2) {
vertex2_type w = source(e2, graph2_);
@@ -579,7 +545,7 @@
v = state2_.core(w);
if (!edge1_exists(v, v_new,
- edge1_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(edge_comp_, e2),
+ edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2),
graph1_))
return false;
@@ -595,7 +561,7 @@
}
{
- compatible_edge_exists<Graph1> edge1_exists;
+ equivalent_edge_exists<Graph1> edge1_exists;
BGL_FORALL_OUTEDGES_T(w_new, e2, graph2_, Graph2) {
vertex2_type w = target(e2, graph2_);
@@ -605,7 +571,7 @@
v = state2_.core(w);
if (!edge1_exists(v_new, v,
- edge1_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(edge_comp_, e2),
+ edge1_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp_, e2),
graph1_))
return false;
@@ -676,7 +642,7 @@
}
// Calls the user_callback with a graph (sub)graph mapping
- bool call_back(SubGraphIsoMapCallBack user_callback) const {
+ bool call_back(SubGraphIsoMapCallback user_callback) const {
return user_callback(state1_.get_map(), state2_.get_map());
}
@@ -705,15 +671,15 @@
typename IndexMap1,
typename IndexMap2,
typename VertexOrder1,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate,
- typename SubGraphIsoMapCallBack,
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename SubGraphIsoMapCallback,
problem_selector problem_selection>
bool match(const Graph1& graph1, const Graph2& graph2,
- SubGraphIsoMapCallBack user_callback, const VertexOrder1& vertex_order1,
+ SubGraphIsoMapCallback user_callback, const VertexOrder1& vertex_order1,
state<Graph1, Graph2, IndexMap1, IndexMap2,
- EdgeCompatibilityPredicate, VertexCompatibilityPredicate,
- SubGraphIsoMapCallBack, problem_selection>& s) {
+ EdgeEquivalencePredicate, VertexEquivalencePredicate,
+ SubGraphIsoMapCallback, problem_selection>& s) {
typename VertexOrder1::const_iterator graph1_verts_iter;
@@ -783,20 +749,19 @@
// 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_;
+ const Graph& graph_;
};
- // Used to sort nodes by frequency/degrees
+ // Used to sort nodes by multiplicity of in/out degrees
template<typename Graph,
typename FrequencyMap>
struct vertex_frequency_degree_cmp {
typedef typename graph_traits<Graph>::vertex_descriptor vertex_type;
- vertex_frequency_degree_cmp(const Graph& graph, const FrequencyMap& freq)
+ vertex_frequency_degree_cmp(const Graph& graph, FrequencyMap freq)
: graph_(graph), freq_(freq) {}
bool operator()(const vertex_type& v, const vertex_type& w) const {
@@ -807,17 +772,17 @@
}
const Graph& graph_;
- const FrequencyMap& freq_;
+ FrequencyMap freq_;
};
- // Sorts vertices of a graph by frequency/degree
+ // Sorts vertices of a graph by multiplicity of in/out degrees
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);
@@ -849,6 +814,19 @@
} // namespace detail
+
+ // Returns vertex order (vertices sorted by multiplicity of in/out degrees)
+ template<typename Graph>
+ std::vector<typename graph_traits<Graph>::vertex_descriptor>
+ vertex_order_by_mult(const Graph& graph) {
+
+ std::vector<typename graph_traits<Graph>::vertex_descriptor> vertex_order;
+ std::copy(vertices(graph).first, vertices(graph).second, std::back_inserter(vertex_order));
+
+ detail::sort_vertices(graph, get(vertex_index, graph), vertex_order);
+ return vertex_order;
+ }
+
// Enumerates all graph sub-graph isomorphism mappings between graphs
// graph_small and graph_large. Continues until user_callback returns true or the
@@ -858,15 +836,15 @@
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) {
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename SubGraphIsoMapCallback>
+ bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ IndexMapSmall index_map_small, IndexMapLarge index_map_large,
+ const VertexOrderSmall& vertex_order_small,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp) {
// Graph requirements
BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<GraphSmall> ));
@@ -894,14 +872,14 @@
typedef typename property_traits<IndexMapLarge>::value_type IndexMapLargeValue;
BOOST_STATIC_ASSERT(( is_convertible<IndexMapLargeValue, size_type_large>::value ));
- // Edge & vertex compatibility requirements
+ // Edge & vertex requirements
typedef typename graph_traits<GraphSmall>::edge_descriptor edge_small_type;
typedef typename graph_traits<GraphLarge>::edge_descriptor edge_large_type;
- BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeCompatibilityPredicate,
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeEquivalencePredicate,
edge_small_type, edge_large_type> ));
- BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexCompatibilityPredicate,
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexEquivalencePredicate,
vertex_small_type, vertex_large_type> ));
// Vertex order requirements
@@ -927,60 +905,54 @@
return true;
detail::state<GraphSmall, GraphLarge, IndexMapSmall, IndexMapLarge,
- EdgeCompatibilityPredicate, VertexCompatibilityPredicate,
- SubGraphIsoMapCallBack, detail::sub_graph_iso>
+ EdgeEquivalencePredicate, VertexEquivalencePredicate,
+ SubGraphIsoMapCallback, detail::subgraph_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
+ // All default interface for vf2_subgraph_iso
template <typename GraphSmall,
typename GraphLarge,
- typename SubGraphIsoMapCallBack>
- bool vf2_sub_graph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
- SubGraphIsoMapCallBack user_callback) {
+ typename SubGraphIsoMapCallback>
+ bool vf2_subgraph_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());
+ return vf2_subgraph_iso(graph_small, graph_large, user_callback,
+ get(vertex_index, graph_small), get(vertex_index, graph_large),
+ vertex_order_by_mult(graph_small),
+ always_equivalent(), always_equivalent());
}
- // Named parameter interface of vf2_sub_graph_iso
+ // Named parameter interface of vf2_subgraph_iso
template <typename GraphSmall,
typename GraphLarge,
typename VertexOrderSmall,
- typename SubGraphIsoMapCallBack,
+ 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())
- );
+ bool vf2_subgraph_iso(const GraphSmall& graph_small, const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ const VertexOrderSmall& vertex_order_small,
+ const bgl_named_params<Param, Tag, Rest>& params) {
+
+ return vf2_subgraph_iso(graph_small, graph_large, user_callback,
+ choose_const_pmap(get_param(params, vertex_index1),
+ graph_small, vertex_index),
+ choose_const_pmap(get_param(params, vertex_index2),
+ graph_large, vertex_index),
+ vertex_order_small,
+ choose_param(get_param(params, edges_equivalent_t()),
+ always_equivalent()),
+ choose_param(get_param(params, vertices_equivalent_t()),
+ always_equivalent())
+ );
}
@@ -993,15 +965,15 @@
typename IndexMap1,
typename IndexMap2,
typename VertexOrder1,
- typename EdgeCompatibilityPredicate,
- typename VertexCompatibilityPredicate,
- typename GraphIsoMapCallBack>
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename GraphIsoMapCallback>
bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2,
- GraphIsoMapCallBack user_callback,
+ GraphIsoMapCallback user_callback,
IndexMap1 index_map1, IndexMap2 index_map2,
const VertexOrder1& vertex_order1,
- EdgeCompatibilityPredicate edge_comp,
- VertexCompatibilityPredicate vertex_comp) {
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp) {
// Graph requirements
BOOST_CONCEPT_ASSERT(( BidirectionalGraphConcept<Graph1> ));
@@ -1030,14 +1002,14 @@
typedef typename property_traits<IndexMap2>::value_type IndexMap2Value;
BOOST_STATIC_ASSERT(( is_convertible<IndexMap2Value, size_type2>::value ));
- // Edge & vertex compatibility requirements
+ // Edge & vertex requirements
typedef typename graph_traits<Graph1>::edge_descriptor edge1_type;
typedef typename graph_traits<Graph2>::edge_descriptor edge2_type;
- BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeCompatibilityPredicate,
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<EdgeEquivalencePredicate,
edge1_type, edge2_type> ));
- BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexCompatibilityPredicate,
+ BOOST_CONCEPT_ASSERT(( BinaryPredicateConcept<VertexEquivalencePredicate,
vertex1_type, vertex2_type> ));
// Vertex order requirements
@@ -1046,7 +1018,6 @@
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;
@@ -1064,8 +1035,8 @@
return true;
detail::state<Graph1, Graph2, IndexMap1, IndexMap2,
- EdgeCompatibilityPredicate, VertexCompatibilityPredicate,
- GraphIsoMapCallBack, detail::isomorphism>
+ EdgeEquivalencePredicate, VertexEquivalencePredicate,
+ GraphIsoMapCallback, detail::isomorphism>
s(graph1, graph2, index_map1, index_map2, edge_comp, vertex_comp);
return detail::match(graph1, graph2, user_callback, vertex_order1, s);
@@ -1075,22 +1046,16 @@
// All default interface for vf2_graph_iso
template <typename Graph1,
typename Graph2,
- typename GraphIsoMapCallBack>
+ typename GraphIsoMapCallback>
bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2,
- GraphIsoMapCallBack user_callback) {
+ 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());
+ vertex_order_by_mult(graph1),
+ always_equivalent(), always_equivalent());
}
@@ -1098,12 +1063,12 @@
template <typename Graph1,
typename Graph2,
typename VertexOrder1,
- typename GraphIsoMapCallBack,
+ typename GraphIsoMapCallback,
typename Param,
typename Tag,
typename Rest>
bool vf2_graph_iso(const Graph1& graph1, const Graph2& graph2,
- GraphIsoMapCallBack user_callback,
+ GraphIsoMapCallback user_callback,
const VertexOrder1& vertex_order1,
const bgl_named_params<Param, Tag, Rest>& params) {
@@ -1114,9 +1079,9 @@
graph2, vertex_index),
vertex_order1,
choose_param(get_param(params, edges_equivalent_t()),
- always_compatible()),
+ always_equivalent()),
choose_param(get_param(params, vertices_equivalent_t()),
- always_compatible())
+ always_equivalent())
);
}
@@ -1126,17 +1091,17 @@
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) {
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate>
+ inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp) {
BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph1> ));
BOOST_CONCEPT_ASSERT(( AdjacencyMatrixConcept<Graph2> ));
- detail::compatible_edge_exists<Graph2> edge2_exists;
+ detail::equivalent_edge_exists<Graph2> edge2_exists;
BGL_FORALL_EDGES_T(e1, graph1, Graph1) {
typename graph_traits<Graph1>::vertex_descriptor s1, t1;
@@ -1151,7 +1116,7 @@
typename graph_traits<Graph2>::edge_descriptor e2;
if (!edge2_exists(s2, t2,
- detail::edge2_predicate<Graph1, Graph2, EdgeCompatibilityPredicate>(edge_comp, e1),
+ detail::edge2_predicate<Graph1, Graph2, EdgeEquivalencePredicate>(edge_comp, e1),
graph2))
return false;
@@ -1160,14 +1125,14 @@
return true;
}
- // Variant of verify_sub_graph_iso with all default parameters
+ // Variant of verify_subgraph_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());
+ inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f) {
+ return verify_vf2_subgraph_iso(graph1, graph2, f,
+ always_equivalent(), always_equivalent());
}
Modified: trunk/libs/graph/doc/vf2_sub_graph_iso.html
==============================================================================
--- trunk/libs/graph/doc/vf2_sub_graph_iso.html (original)
+++ trunk/libs/graph/doc/vf2_sub_graph_iso.html 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
@@ -34,31 +34,31 @@
<img src="../../../boost.png" alt="C++ Boost" width="277" height="86" />
<br />
<h1>
- <tt>vf2_sub_graph_iso</tt>
+ <tt>vf2_subgraph_iso</tt>
</h1>
<pre>
<em class="comment">// all defaults interface</em>
template <typename GraphSmall,
typename GraphLarge,
- typename SubGraphIsoMapCallBack>
-bool vf2_sub_graph_iso(const GraphSmall& graph_small,
- const GraphLarge& graph_large,
- SubGraphIsoMapCallBack user_callback)
+ typename SubGraphIsoMapCallback>
+bool vf2_subgraph_iso(const GraphSmall& graph_small,
+ const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback)
<em class="comment">// named parameter version</em>
template <typename GraphSmall,
typename GraphLarge,
typename VertexOrderSmall,
- typename SubGraphIsoMapCallBack,
+ 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)
+bool vf2_subgraph_iso(const GraphSmall& graph_small,
+ const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ const VertexOrderSmall& vertex_order_small,
+ const bgl_named_params<Param, Tag, Rest>& params)
<em class="comment">// non-named parameter version</em>
@@ -67,17 +67,17 @@
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)
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate,
+ typename SubGraphIsoMapCallback>
+bool vf2_subgraph_iso(const GraphSmall& graph_small,
+ const GraphLarge& graph_large,
+ SubGraphIsoMapCallback user_callback,
+ IndexMapSmall index_map_small,
+ IndexMapLarge index_map_large,
+ const VertexOrderSmall& vertex_order_small,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp)
</pre>
<p>
An isomorphism between two graphs <em>G<sub>1</sub>=(V<sub>1</sub>, E<sub>1</sub>)</em>
@@ -91,14 +91,17 @@
<p>
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,
+ <tt>user_callback</tt>. It continues until <tt>user_callback</tt>
+ returns true or the search space has been fully explored. <tt>vf2_subgraph_iso</tt>
+ returns true if a graph-subgraph isomorphism exists and false otherwise.
+ <tt>EdgeEquivalencePredicate</tt> and
+ <tt>VertexEquivalencePredicate</tt> predicates are used to test whether
+ edges and vertices are equivalent. 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
+ <tt><a href="./mcgregor_common_subgraphs.html#make_property_map_equivalent">
+ make_property_map_equivalent</a></tt>
+ function. By default <tt><a href="./mcgregor_common_subgraphs.html#always_equivalent">
+ always_equivalent</a></tt> is used, which returns
true for any pair of vertices or edges.
</p>
<p>
@@ -116,9 +119,7 @@
the vertex pairs that are candidates to be added to the current state
<em>s</em>. If a pair of vertices (<em>v, w</em>) is feasible, the mapping
is extended and the associated successor state <em>s'</em> is computed.
- The whole procedure is then repeated for state <em>s'</em>. A somewhat more
- detailed description of the current implementation is given in the file
- vf2_sub_graph_iso_impl.pdf.
+ The whole procedure is then repeated for state <em>s'</em>.
</p>
<h3>Where Defined</h3>
@@ -134,7 +135,7 @@
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
+ Vertex List Graph,
<a href="./EdgeListGraph.html">Edge List Graph</a>,
<a href="./BidirectionalGraph.html">Bidirectional Graph</a> and
<a href="./AdjacencyMatrix.html">Adjacency Matrix</a>.
@@ -144,13 +145,13 @@
<blockquote>
The (second) larger graph to be tested.
Type <tt>GraphLarge</tt> must be a model of
- Vertex List Graph
+ Vertex List Graph,
<a href="./EdgeListGraph.html">Edge List Graph</a>,
<a href="./BidirectionalGraph.html">Bidirectional Graph</a> and
<a href="./AdjacencyMatrix.html">Adjacency Matrix</a>.
</blockquote>
- OUT: <tt>SubGraphIsoMapCallBack user_callback</tt>
+ 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:
@@ -163,7 +164,7 @@
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
+ graphs given to <tt>vf2_subgraph_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,
@@ -176,8 +177,7 @@
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.
+ is provided as a utility function.
</blockquote>
IN: <tt>const VertexOrderSmall& vertex_order_small</tt>
@@ -189,7 +189,7 @@
with value type
<tt>graph_traits<GraphSmall>::vertex_descriptor</tt>.
<br />
- <b>Default</b> The vertices are ordered by multiplicity of in/out degree.
+ <b>Default</b> The vertices are ordered by multiplicity of in/out degrees.
</blockquote>
<h3>Named Parameters</h3>
@@ -212,32 +212,32 @@
<b>Default:</b> <tt>get(vertex_index, graph_large)</tt>
</blockquote>
- IN: <tt>edges_equivalent(EdgeCompatibilityPredicate edge_comp)</tt>
+ IN: <tt>edges_equivalent(EdgeEquivalencePredicate 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
+ <tt>graph_small</tt> and <tt>graph_large</tt> are equivalent.
+ Type <tt>EdgeEquivalencePredicate</tt> must be a model 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.
+ indicates that the edges are equivalent.
<br />
- <b>Default:</b> <tt>always_compatible</tt>
+ <b>Default:</b> <tt>always_equivalent</tt>
</blockquote>
- IN: <tt>vertices_equivalent(VertexCompatibilityPredicate vertex_comp)</tt>
+ IN: <tt>vertices_equivalent(VertexEquivalencePredicate 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
+ <tt>graph_small</tt> and <tt>graph_large</tt> are equivalent.
+ Type <tt>VertexEquivalencePredicate</tt> must be a model of
<a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary Predicate</a>
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.
+ indicates that the vertices are equivalent.
<br />
- <b>Default:</b> <tt>always_compatible</tt>
+ <b>Default:</b> <tt>always_equivalent</tt>
</blockquote>
<h3>Related Functions</h3>
@@ -245,77 +245,66 @@
Non-named parameter, named-parameter and all default parameter versions of
function
</p>
- <pre>
+ <tt>
vf2_graph_iso(...)
- </pre>
+ </tt>
<p>
for isomorphism testing take the same parameters as the corresponding
- functions <tt>vf2_sub_graph_iso</tt> for sub-graph isomorphism testing.
+ functions <tt>vf2_subgraph_iso</tt> for subgraph 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.
+ <tt>EdgeEquivalencePredicate</tt> and
+ <tt>VertexEquivalencePredicate</tt> predicates are used to test
+ whether edges and vertices are equivalent. By default
+ <tt>always_equivalent</tt> as used.
</p>
<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,
+ <tt id="vf2_callback">
+template<typename Graph1,
typename Graph2>
struct vf2_print_callback
- </pre>
+ </tt>
<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 <em>G<sub>1</sub></em>
- and <em>G<sub>2</sub></em> 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.
+ and <em>G<sub>2</sub></em>.
+ </blockquote>
+
+ <pre>
+template<typename Graph>
+std::vector<typename graph_traits<Graph>::vertex_descriptor>
+ vertex_order_by_mult(const Graph& graph)
+ </pre>
+ <blockquote>
+ Returns a vector containing the vertices of a graph, sorted by multiplicity of in/out degrees.
</blockquote>
<pre>
-<em class="comment">// Variant of verify_sub_graph_iso with all default parameters</em>
+<em class="comment">// Variant of verify_subgraph_iso with all default parameters</em>
template<typename Graph1,
typename Graph2,
typename CorresponenceMap1To2>
-inline bool verify_vf2_sub_graph_iso(const Graph1& graph1, const Graph2& graph2,
- const CorresponenceMap1To2 f)
+inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f)
<em class="comment">// Verifies a graph (sub)graph isomorphism map</em>
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)
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate>
+inline bool verify_vf2_subgraph_iso(const Graph1& graph1, const Graph2& graph2,
+ const CorresponenceMap1To2 f,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp)
</pre>
<blockquote>
This function can be used to verify a (sub)graph isomorphism mapping <em>f</em>. The parameters are
-akin to function <tt>vf2_sub_graph_iso</tt> (<tt>vf2_graph_iso</tt>).
+analogous to function <tt>vf2_subgraph_iso</tt> (<tt>vf2_graph_iso</tt>).
</blockquote>
@@ -333,12 +322,12 @@
<p>
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
+ vertices of the graphs. <tt>vf2_subgraph_iso</tt> computes all the
+ subgraph isomorphism mappings between the two graphs and outputs them
via <tt>callback</tt>.
</p>
<pre>
-typedef adjacency_list<vecS, vecS, bidirectionalS> graph_type;
+typedef adjacency_list<setS, vecS, bidirectionalS> graph_type;
<em class="comment">// Build graph1</em>
int num_vertices1 = 8; graph_type graph1(num_vertices1);
@@ -353,12 +342,14 @@
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);
-
-<em class="comment">// true instructs callback to verify a map using
-// verify_vf2_sub_graph_iso</em>
-vf2_print_callback<graph_type, graph_type> callback(graph1, graph2, true);
-
-bool ret = vf2_sub_graph_iso(graph1, graph2, callback);
+<em class="comment">
+// Create callback to print mappings</em>
+vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
+
+<em class="comment">
+// Print out all subgraph isomorphism mappings between graph1 and graph2.
+// Vertices and edges are assumed to be always equivalent.</em>
+vf2_subgraph_iso(graph1, graph2, callback);
</pre>
<p>
The complete example can be found under
@@ -368,160 +359,80 @@
<h4>Example 2</h4>
- This example uses the GraphViz input parser, i.e. read_graphviz
- function to interpret the two graphs specified in files <em>graph_small.dot</em> and <em>graph_large.dot</em>
- 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>.
+ <p>
+ In this example, the subgraph isomorphism mappings between multi-graphs are computed. The vertices
+ and edges of the multi-graphs are differentiated using property maps.
+ </p>
<pre>
-std::ifstream graph_small_file("graph_small.dot");
-std::ifstream graph_large_file("graph_large.dot");
-
-<em class="comment">// Vertex properties</em>
-typedef property <vertex_name_t, std::string> vertex_p;
+<em class="comment">// Define edge and vertex properties</em>
+typedef property<edge_name_t, char> edge_property;
+typedef property<vertex_name_t, char, property<vertex_index_t, int> > vertex_property;
+
+<em class="comment">// Using a vecS graphs => the index maps are implicit.</em>
+typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph_type;
+
+<em class="comment">// Create graph1</em>
+graph_type graph1;
+<em class="comment">// Add vertices... </em>
+add_vertex(vertex_property('a'), graph1);
+...
+<em class="comment">//... and edges </em>
+add_edge(0, 1, edge_property('b'), graph1);
+add_edge(0, 1, edge_property('b'), graph1);
+...
+
+<em class="comment">// Create graph2 </em>
+graph_type graph2;
+add_vertex(vertex_property('a'), graph2);
+...
+add_edge(0, 1, edge_property('a'), graph2);
+...
+ </pre>
-<em class="comment">// adjacency_list-based type</em>
-typedef adjacency_list <vecS, vecS, undirectedS, vertex_p> graph_t;
-
-<em class="comment">// Construct an empty graph_small and prepare the dynamic_property_maps.</em>
-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);
-
-<em class="comment">// Read graph_small</em>
-bool status = read_graphviz(graph_small_file, graph_small, dp_small, "node_id");
-
-<em class="comment">// Construct an empty graph_large and prepare the dynamic_property_maps,
-// following the read_graphviz example</em>
-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);
-
-<em class="comment">// Read graph_large</em>
-status = read_graphviz(graph_large_file, graph_large, dp_large, "node_id");
-
-<em class="comment">// Create the call_back function</em>
-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);
-<em class="comment"> // Compute the sub-graph isomorphism mappings</em>
-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:
+ <p>
+ To differentiate vertices and edges with property maps, binary predicates are created using the
+ <tt><a href="./mcgregor_common_subgraphs.html#make_property_map_equivalent">
+ make_property_map_equivalent</a></tt> function:
+ </p>
<pre>
-<em id="example_callback" class="comment">// Define a print_callback</em>
-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;
-
-<em class="comment">// Print sub graph isomorphism map</em>
- 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_;
-};
+<em class="comment">// Create the vertex binary predicate</em>
+typedef property_map<graph_type, vertex_name_t>::type vertex_name_map_t;
+typedef property_map_equivalent<vertex_name_map_t, vertex_name_map_t> vertex_comp_t;
+vertex_comp_t vertex_comp =
+ make_property_map_equivalent(get(vertex_name, graph1), get(vertex_name, graph2));
+
+<em class="comment">// Create the vertex binary predicate</em>
+typedef property_map<graph_type, edge_name_t>::type edge_name_map_t;
+typedef property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
+edge_comp_t edge_comp =
+ make_property_map_equivalent(get(edge_name, graph1), get(edge_name, graph2));
</pre>
- Using the sample DOT-files <em>graph_small.dot</em>:
-
- <pre id="dot_files">
-graph G_small {
-node1 -- node2;
-node1 -- node3;
-node3 -- node3;
-node4 -- node1;
-node4 -- node3;
-}
- </pre>
-
- and <em>graph_large.dot</em>:
-
+ <p>
+ Finally, a callback function object is created and the subgraph isomorphism mappings are
+ computed:
+ </p>
<pre>
-graph G_large {
-node1 -- node3;
-node1 -- node4;
-node1 -- node6;
-node2 -- node4;
-node2 -- node5;
-node3 -- node3;
-node4 -- node5;
-node4 -- node6;
-node6 -- node6;
-}
- </pre>
+<em class="comment">// Create callback</em>
+vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
- <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).
+<em class="comment">
+// Print out all subgraph isomorphism mappings between graph1 and graph2.
+// Function vertex_order_by_mult is used to compute the order of
+// vertices of graph1. That's the order in which the vertices are examined
+// during the matching process.</em>
+vf2_subgraph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
+ edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
+ </pre>
<p>
-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.
+For the complete example, see
+examples/vf2_sub_graph_iso_multi_example.cpp.
<br>
<p>
-<h4>Additional Examples</h4>
-
-<p>
-These are: a multi-graph example
-examples/vf2_sub_graph_iso_multi_example.cpp,
-<br>
-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,
-<br>
-one putting a grid_graph
-examples/vf2_sub_graph_iso_grd_example.cpp
-<br>
-and one matching bidirectional und undirected graphs
-examples/vf2_sub_graph_iso_undir_example.cpp.
-<br>
-<p>
-
<h3>Bibliography</h3>
<dl>
Deleted: trunk/libs/graph/doc/vf2_sub_graph_iso_impl.pdf
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/graph/doc/vf2_sub_graph_iso_impl.tex
==============================================================================
--- trunk/libs/graph/doc/vf2_sub_graph_iso_impl.tex 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
+++ (empty file)
@@ -1,474 +0,0 @@
-\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-15 20:51:51 EST (Sat, 15 Dec 2012)
@@ -44,10 +44,6 @@
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 ;
Deleted: trunk/libs/graph/example/vf2_random_graphs.sce
==============================================================================
--- trunk/libs/graph/example/vf2_random_graphs.sce 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
+++ (empty file)
@@ -1,96 +0,0 @@
-//=======================================================================
-// 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
Deleted: trunk/libs/graph/example/vf2_sub_graph_iso_csr_example.cpp
==============================================================================
--- trunk/libs/graph/example/vf2_sub_graph_iso_csr_example.cpp 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
+++ (empty file)
@@ -1,45 +0,0 @@
-//=======================================================================
-// 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;
-}
Modified: trunk/libs/graph/example/vf2_sub_graph_iso_example.cpp
==============================================================================
--- trunk/libs/graph/example/vf2_sub_graph_iso_example.cpp (original)
+++ trunk/libs/graph/example/vf2_sub_graph_iso_example.cpp 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
@@ -12,7 +12,8 @@
int main() {
- typedef adjacency_list<vecS, vecS, bidirectionalS> graph_type;
+
+ typedef adjacency_list<setS, vecS, bidirectionalS> graph_type;
// Build graph1
int num_vertices1 = 8; graph_type graph1(num_vertices1);
@@ -28,12 +29,12 @@
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);
+ // Create callback to print mappings
+ vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
- bool ret = vf2_sub_graph_iso(graph1, graph2, callback);
- (void)ret;
+ // Print out all subgraph isomorphism mappings between graph1 and graph2.
+ // Vertices and edges are assumed to be always equivalent.
+ vf2_subgraph_iso(graph1, graph2, callback);
return 0;
}
Deleted: trunk/libs/graph/example/vf2_sub_graph_iso_grd_example.cpp
==============================================================================
--- trunk/libs/graph/example/vf2_sub_graph_iso_grd_example.cpp 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
+++ (empty file)
@@ -1,36 +0,0 @@
-//=======================================================================
-// 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;
-}
Deleted: trunk/libs/graph/example/vf2_sub_graph_iso_gviz_example.cpp
==============================================================================
--- trunk/libs/graph/example/vf2_sub_graph_iso_gviz_example.cpp 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
+++ (empty file)
@@ -1,143 +0,0 @@
-//=======================================================================
-// 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;
-}
Modified: trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp
==============================================================================
--- trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp (original)
+++ trunk/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
@@ -6,60 +6,16 @@
// 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;
+ typedef property<vertex_name_t, char, property<vertex_index_t, int> > vertex_property;
+
+ // Using a vecS graphs => the index maps are implicit.
+ typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph_type;
// Build graph1
graph_type graph1;
@@ -77,7 +33,6 @@
add_edge(2, 2, edge_property('l'), graph1);
add_edge(2, 2, edge_property('l'), graph1);
-
// Build graph2
graph_type graph2;
@@ -92,7 +47,6 @@
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);
@@ -112,34 +66,24 @@
// 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;
+ typedef property_map_equivalent<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));
+ make_property_map_equivalent(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;
+ typedef property_map_equivalent<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;
+ make_property_map_equivalent(get(edge_name, graph1), get(edge_name, graph2));
+
+ // Create callback
+ vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
+
+ // Print out all subgraph isomorphism mappings between graph1 and graph2.
+ // Function vertex_order_by_mult is used to compute the order of
+ // vertices of graph1. That's the order in which the vertices are examined
+ // during the matching process.
+ vf2_subgraph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
+ edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
return 0;
}
Deleted: trunk/libs/graph/example/vf2_sub_graph_iso_undir_example.cpp
==============================================================================
--- trunk/libs/graph/example/vf2_sub_graph_iso_undir_example.cpp 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
+++ (empty file)
@@ -1,73 +0,0 @@
-//=======================================================================
-// 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;
-}
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
@@ -125,6 +125,7 @@
[ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ]
[ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
[ compile filtered_graph_properties_dijkstra.cpp ]
+ [ run vf2_sub_graph_iso_test.cpp ]
;
# Run SDB tests only when -sSDB= is set.
Added: trunk/libs/graph/test/vf2_sub_graph_iso_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/vf2_sub_graph_iso_test.cpp 2012-12-15 20:51:51 EST (Sat, 15 Dec 2012)
@@ -0,0 +1,293 @@
+//=======================================================================
+// Boost.Graph library vf2_sub_graph_iso test
+// Adapted from isomorphism.cpp and mcgregor_subgraphs_test.cpp
+//
+// 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 <map>
+#include <algorithm>
+#include <cstdlib>
+#include <time.h>
+#include <boost/test/minimal.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/vf2_sub_graph_iso.hpp>
+#include <boost/graph/random.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/random.hpp>
+#include <boost/random/variate_generator.hpp>
+#include <boost/random/uniform_real.hpp>
+#include <boost/random/uniform_int.hpp>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/graph/graphviz.hpp>
+
+using namespace boost;
+
+
+template <typename Generator>
+struct random_functor {
+ random_functor(Generator& g) : g(g) { }
+ std::size_t operator()(std::size_t n) {
+ boost::uniform_int<std::size_t> distrib(0, n-1);
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<std::size_t> >
+ x(g, distrib);
+ return x();
+ }
+ Generator& g;
+};
+
+
+template<typename Graph1, typename Graph2>
+void randomly_permute_graph(Graph1& g1, const Graph2& g2) {
+ BOOST_REQUIRE(num_vertices(g1) <= num_vertices(g2));
+ BOOST_REQUIRE(num_edges(g1) == 0);
+
+ typedef typename graph_traits<Graph1>::vertex_descriptor vertex1;
+ typedef typename graph_traits<Graph2>::vertex_descriptor vertex2;
+ typedef typename graph_traits<Graph1>::vertex_iterator vertex_iterator;
+ typedef typename graph_traits<Graph2>::edge_iterator edge_iterator;
+
+ boost::mt19937 gen;
+ random_functor<boost::mt19937> rand_fun(gen);
+
+ // Decide new order
+ std::vector<vertex2> orig_vertices;
+ std::copy(vertices(g2).first, vertices(g2).second, std::back_inserter(orig_vertices));
+ std::random_shuffle(orig_vertices.begin(), orig_vertices.end(), rand_fun);
+ std::map<vertex2, vertex1> vertex_map;
+
+ std::size_t i = 0;
+ for (vertex_iterator vi = vertices(g1).first;
+ vi != vertices(g1).second; ++i, ++vi) {
+ vertex_map[orig_vertices[i]] = *vi;
+ put(vertex_name_t(), g1, *vi, get(vertex_name_t(), g2, orig_vertices[i]));
+ }
+
+ for (edge_iterator ei = edges(g2).first; ei != edges(g2).second; ++ei) {
+ typename std::map<vertex2, vertex1>::iterator si = vertex_map.find(source(*ei, g2)),
+ ti = vertex_map.find(target(*ei, g2));
+ if ((si != vertex_map.end()) && (ti != vertex_map.end()))
+ add_edge(si->second, ti->second, get(edge_name_t(), g2, *ei), g1);
+ }
+}
+
+
+template<typename Graph>
+void generate_random_digraph(Graph& g, double edge_probability,
+ int max_parallel_edges, double parallel_edge_probability,
+ int max_edge_name, int max_vertex_name) {
+
+ BOOST_REQUIRE((0 <= edge_probability) && (edge_probability <= 1));
+ BOOST_REQUIRE((0 <= parallel_edge_probability) && (parallel_edge_probability <= 1));
+ BOOST_REQUIRE(0 <= max_parallel_edges);
+ BOOST_REQUIRE(0 <= max_edge_name);
+ BOOST_REQUIRE(0 <= max_vertex_name);
+
+ typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
+ boost::mt19937 random_gen;
+ boost::uniform_real<double> dist_real(0.0, 1.0);
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<double> >
+ random_real_dist(random_gen, dist_real);
+
+ for (vertex_iterator u = vertices(g).first; u != vertices(g).second; ++u) {
+ for (vertex_iterator v = vertices(g).first; v != vertices(g).second; ++v) {
+ if (random_real_dist() <= edge_probability) {
+ add_edge(*u, *v, g);
+ for (int i = 0; i < max_parallel_edges; ++i) {
+ if (random_real_dist() <= parallel_edge_probability)
+ add_edge(*u, *v, g);
+ }
+ }
+ }
+ }
+
+ {
+ boost::uniform_int<int> dist_int(0, max_edge_name);
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<int> >
+ random_int_dist(random_gen, dist_int);
+ randomize_property<vertex_name_t>(g, random_int_dist);
+ }
+
+ {
+ boost::uniform_int<int> dist_int(0, max_vertex_name);
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<int> >
+ random_int_dist(random_gen, dist_int);
+
+ randomize_property<edge_name_t>(g, random_int_dist);
+ }
+
+}
+
+
+template <typename Graph1,
+ typename Graph2,
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate>
+struct test_callback {
+
+ test_callback(const Graph1& graph1, const Graph2& graph2,
+ EdgeEquivalencePredicate edge_comp,
+ VertexEquivalencePredicate vertex_comp, bool output)
+ : graph1_(graph1), graph2_(graph2), edge_comp_(edge_comp), vertex_comp_(vertex_comp),
+ output_(output) {}
+
+ template <typename CorrespondenceMap1To2,
+ typename CorrespondenceMap2To1>
+ bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) {
+
+ bool verified;
+ BOOST_CHECK(verified = verify_vf2_subgraph_iso(graph1_, graph2_, f, edge_comp_, vertex_comp_));
+
+ // Output (sub)graph isomorphism map
+ if (!verified || output_) {
+ std::cout << "Verfied: " << std::boolalpha << verified << std::endl;
+ std::cout << "Num vertices: " << num_vertices(graph1_) << ' ' << num_vertices(graph2_) << std::endl;
+ BGL_FORALL_VERTICES_T(v, graph1_, Graph1)
+ std::cout << '(' << get(vertex_index_t(), graph1_, v) << ", "
+ << get(vertex_index_t(), graph2_, get(f, v)) << ") ";
+
+ std::cout << std::endl;
+ }
+
+ return true;
+ }
+
+private:
+ const Graph1& graph1_;
+ const Graph2& graph2_;
+ EdgeEquivalencePredicate edge_comp_;
+ VertexEquivalencePredicate vertex_comp_;
+ bool output_;
+};
+
+
+void test_vf2_sub_graph_iso(int n1, int n2, double edge_probability,
+ int max_parallel_edges, double parallel_edge_probability,
+ int max_edge_name, int max_vertex_name, bool output) {
+
+ typedef property<edge_name_t, int> edge_property;
+ typedef property<vertex_name_t, int, property<vertex_index_t, int> > vertex_property;
+
+ typedef adjacency_list<listS, listS, bidirectionalS, vertex_property, edge_property> graph1;
+ typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_property, edge_property> graph2;
+
+ graph1 g1(n1);
+ graph2 g2(n2);
+ generate_random_digraph(g2, edge_probability, max_parallel_edges, parallel_edge_probability,
+ max_edge_name, max_vertex_name);
+ randomly_permute_graph(g1, g2);
+
+ int v_idx = 0;
+ for (graph_traits<graph1>::vertex_iterator vi = vertices(g1).first;
+ vi != vertices(g1).second; ++vi) {
+ put(vertex_index_t(), g1, *vi, v_idx++);
+ }
+
+
+ // Create vertex and edge predicates
+ typedef property_map<graph1, vertex_name_t>::type vertex_name_map1;
+ typedef property_map<graph2, vertex_name_t>::type vertex_name_map2;
+
+ typedef property_map_equivalent<vertex_name_map1, vertex_name_map2> vertex_predicate;
+ vertex_predicate vertex_comp =
+ make_property_map_equivalent(get(vertex_name, g1), get(vertex_name, g2));
+
+ typedef property_map<graph1, edge_name_t>::type edge_name_map1;
+ typedef property_map<graph2, edge_name_t>::type edge_name_map2;
+
+ typedef property_map_equivalent<edge_name_map1, edge_name_map2> edge_predicate;
+ edge_predicate edge_comp =
+ make_property_map_equivalent(get(edge_name, g1), get(edge_name, g2));
+
+
+ std::clock_t start = std::clock();
+
+ // Create callback
+ test_callback<graph1, graph2, edge_predicate, vertex_predicate>
+ callback(g1, g2, edge_comp, vertex_comp, output);
+
+ std::cout << std::endl;
+ BOOST_CHECK(vf2_subgraph_iso(g1, g2, callback, vertex_order_by_mult(g1),
+ edges_equivalent(edge_comp).vertices_equivalent(vertex_comp)));
+
+ std::clock_t end1 = std::clock();
+ std::cout << "vf2_subgraph_iso: elapsed time (clock cycles): " << (end1 - start) << std::endl;
+
+ if (num_vertices(g1) == num_vertices(g2)) {
+ std::cout << std::endl;
+ BOOST_CHECK(vf2_graph_iso(g1, g2, callback, vertex_order_by_mult(g1),
+ edges_equivalent(edge_comp).vertices_equivalent(vertex_comp)));
+
+ std::clock_t end2 = std::clock();
+ std::cout << "vf2_graph_iso: elapsed time (clock cycles): " << (end2 - end1) << std::endl;
+ }
+
+ if (output) {
+ std::fstream file_graph1("graph1.dot", std::fstream::out);
+ write_graphviz(file_graph1, g1,
+ make_label_writer(get(boost::vertex_name, g1)),
+ make_label_writer(get(boost::edge_name, g1)));
+
+ std::fstream file_graph2("graph2.dot", std::fstream::out);
+ write_graphviz(file_graph2, g2,
+ make_label_writer(get(boost::vertex_name, g2)),
+ make_label_writer(get(boost::edge_name, g2)));
+ }
+}
+
+int test_main(int argc, char* argv[]) {
+
+ int num_vertices_g1 = 10;
+ int num_vertices_g2 = 20;
+ double edge_probability = 0.4;
+ int max_parallel_edges = 2;
+ double parallel_edge_probability = 0.4;
+ int max_edge_name = 5;
+ int max_vertex_name = 5;
+ bool output = false;
+
+ if (argc > 1) {
+ num_vertices_g1 = boost::lexical_cast<int>(argv[1]);
+ }
+
+ if (argc > 2) {
+ num_vertices_g2 = boost::lexical_cast<int>(argv[2]);
+ }
+
+ if (argc > 3) {
+ edge_probability = boost::lexical_cast<double>(argv[3]);
+ }
+
+ if (argc > 4) {
+ max_parallel_edges = boost::lexical_cast<int>(argv[4]);
+ }
+
+ if (argc > 5) {
+ parallel_edge_probability = boost::lexical_cast<double>(argv[5]);
+ }
+
+ if (argc > 6) {
+ max_edge_name = boost::lexical_cast<int>(argv[6]);
+ }
+
+ if (argc > 7) {
+ max_vertex_name = boost::lexical_cast<int>(argv[7]);
+ }
+
+ if (argc > 8) {
+ output = boost::lexical_cast<bool>(argv[8]);
+ }
+
+ test_vf2_sub_graph_iso(num_vertices_g1, num_vertices_g2, edge_probability,
+ max_parallel_edges, parallel_edge_probability,
+ max_edge_name, max_vertex_name, output);
+
+ return 0;
+}
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