1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
//=======================================================================
// 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;
}
|
