90 lines
3.3 KiB
C++
90 lines
3.3 KiB
C++
//=======================================================================
|
|
// Copyright (C) 2012 Flavio De Lorenzi (fdlorenzi@gmail.com)
|
|
//
|
|
// Distributed under the Boost Software License, Version 1.0. (See
|
|
// accompanying file LICENSE_1_0.txt or copy at
|
|
// http://www.boost.org/LICENSE_1_0.txt)
|
|
//=======================================================================
|
|
|
|
#include <boost/graph/adjacency_list.hpp>
|
|
#include <boost/graph/vf2_sub_graph_iso.hpp>
|
|
using namespace boost;
|
|
|
|
int main() {
|
|
typedef property<edge_name_t, char> edge_property;
|
|
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;
|
|
|
|
add_vertex(vertex_property('a'), graph1);
|
|
add_vertex(vertex_property('a'), graph1);
|
|
add_vertex(vertex_property('a'), graph1);
|
|
|
|
add_edge(0, 1, edge_property('b'), graph1);
|
|
add_edge(0, 1, edge_property('b'), graph1);
|
|
add_edge(0, 1, edge_property('d'), graph1);
|
|
|
|
add_edge(1, 2, edge_property('s'), graph1);
|
|
|
|
add_edge(2, 2, edge_property('l'), graph1);
|
|
add_edge(2, 2, edge_property('l'), graph1);
|
|
|
|
// Build graph2
|
|
graph_type graph2;
|
|
|
|
add_vertex(vertex_property('a'), graph2);
|
|
add_vertex(vertex_property('a'), graph2);
|
|
add_vertex(vertex_property('a'), graph2);
|
|
add_vertex(vertex_property('a'), graph2);
|
|
add_vertex(vertex_property('a'), graph2);
|
|
add_vertex(vertex_property('a'), graph2);
|
|
|
|
add_edge(0, 1, edge_property('a'), graph2);
|
|
add_edge(0, 1, edge_property('a'), graph2);
|
|
add_edge(0, 1, edge_property('b'), graph2);
|
|
|
|
add_edge(1, 2, edge_property('s'), graph2);
|
|
|
|
add_edge(2, 3, edge_property('b'), graph2);
|
|
add_edge(2, 3, edge_property('d'), graph2);
|
|
add_edge(2, 3, edge_property('b'), graph2);
|
|
|
|
add_edge(3, 4, edge_property('s'), graph2);
|
|
|
|
add_edge(4, 4, edge_property('l'), graph2);
|
|
add_edge(4, 4, edge_property('l'), graph2);
|
|
|
|
add_edge(4, 5, edge_property('c'), graph2);
|
|
add_edge(4, 5, edge_property('c'), graph2);
|
|
add_edge(4, 5, edge_property('c'), graph2);
|
|
|
|
add_edge(5, 0, edge_property('s'), graph2);
|
|
|
|
// create predicates
|
|
typedef property_map<graph_type, vertex_name_t>::type vertex_name_map_t;
|
|
typedef property_map_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));
|
|
|
|
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));
|
|
|
|
// 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. This is 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;
|
|
}
|