1 |
|
---|
2 | #include <boost/graph/adjacency_list.hpp>
|
---|
3 | #include <boost/graph/directed_graph.hpp>
|
---|
4 | #include <boost/graph/compressed_sparse_row_graph.hpp>
|
---|
5 | #include <stdio.h>
|
---|
6 | typedef size_t mbglIndex;
|
---|
7 |
|
---|
8 | #ifndef MYISO
|
---|
9 | #include <boost/graph/isomorphism.hpp>
|
---|
10 | #else
|
---|
11 | #include "isomorphism_fixed.hpp"
|
---|
12 | #endif
|
---|
13 |
|
---|
14 | int test_isomorphism_boost() {
|
---|
15 | using namespace boost;
|
---|
16 | const mbglIndex n=10;
|
---|
17 | mbglIndex rp1[] = {0,4,8,12,16,20,24,28,32,36,40};
|
---|
18 | mbglIndex ci1[] = {1,3,6,7,0,2,3,4,9,4,5,1,0,1,6,7,9,2,5,1,8,2,4,7,8,9,3,0,0,8,3,5,9,5,6,7,8,2,4,6};
|
---|
19 |
|
---|
20 | mbglIndex rp2[] = {0,4,8,12,16,20,24,28,32,36,40};
|
---|
21 | mbglIndex ci2[] = {1,3,5,7,0,2,3,4,9,4,6,1,0,1,6,7,1,2,5,9,8,9,4,0,8,2,3,7,0,8,3,6,9,5,6,7,8,2,4,5};
|
---|
22 |
|
---|
23 | typedef adjacency_list<vecS,vecS,bidirectionalS> RawGraph;
|
---|
24 | RawGraph G(n), H(n);
|
---|
25 |
|
---|
26 | for (size_t i=0; i<n; ++i) {
|
---|
27 | for (mbglIndex nzi=rp1[i]; nzi<rp1[i+1]; ++nzi) {
|
---|
28 | boost::add_edge(i,ci1[nzi],G);
|
---|
29 | }
|
---|
30 | }
|
---|
31 |
|
---|
32 | for (size_t i=0; i<n; ++i) {
|
---|
33 | for (mbglIndex nzi=rp2[i]; nzi<rp2[i+1]; ++nzi) {
|
---|
34 | boost::add_edge(i,ci2[nzi],H);
|
---|
35 | }
|
---|
36 | }
|
---|
37 |
|
---|
38 |
|
---|
39 | typedef compressed_sparse_row_graph<bidirectionalS> Graph;
|
---|
40 | Graph G1(G), H1(H);
|
---|
41 |
|
---|
42 |
|
---|
43 |
|
---|
44 | typedef boost::graph_traits<Graph>::vertex_descriptor vertex;
|
---|
45 | vertex map[n];
|
---|
46 |
|
---|
47 | printf("isomorphism(G,H): Correct initial output on different pair!\n");
|
---|
48 | if (isomorphism(G1,H1, isomorphism_map(
|
---|
49 | make_iterator_property_map(map,get(vertex_index,G1))))==true) {
|
---|
50 | printf("Isomorphic (incorrect)\n");
|
---|
51 | } else {
|
---|
52 | printf("Not isomorphic (correct)\n");
|
---|
53 | }
|
---|
54 |
|
---|
55 | printf("isomorphism(G,G): Correct initial output on exact pair!\n");
|
---|
56 | if (isomorphism(G1,G1, isomorphism_map(
|
---|
57 | make_iterator_property_map(map,get(vertex_index,G1))))==true) {
|
---|
58 | printf("Isomorphic (correct)\n");
|
---|
59 | } else {
|
---|
60 | printf("Not isomorphic (incorrect)\n");
|
---|
61 | }
|
---|
62 |
|
---|
63 | printf("isomorphism(G,H): INCORRECT output on the same first pair\n");
|
---|
64 | if (isomorphism(G1,H1, isomorphism_map(
|
---|
65 | make_iterator_property_map(map,get(vertex_index,G1))))==true) {
|
---|
66 | printf("Isomorphic (incorrect)\n");
|
---|
67 | } else {
|
---|
68 | printf("Not isomorphic (correct)\n");
|
---|
69 | }
|
---|
70 |
|
---|
71 | printf("isomorphism(G,H): Persists after a function call...\n");
|
---|
72 | if (isomorphism(G1,H1, isomorphism_map(
|
---|
73 | make_iterator_property_map(map,get(vertex_index,G1))))==true) {
|
---|
74 | printf("Isomorphic (incorrect)\n");
|
---|
75 | } else {
|
---|
76 | printf("Not isomorphic (correct)\n");
|
---|
77 | }
|
---|
78 |
|
---|
79 | printf("isomorphism(G,H): Correct again after reset map\n");
|
---|
80 | for (size_t i=0; i<n; ++i) {
|
---|
81 | map[i] = graph_traits<Graph>::null_vertex();
|
---|
82 | }
|
---|
83 | if (isomorphism(G1,H1, isomorphism_map(
|
---|
84 | make_iterator_property_map(map,get(vertex_index,G1))))==true) {
|
---|
85 | printf("Isomorphic (incorrect)\n");
|
---|
86 | } else {
|
---|
87 | printf("Not isomorphic (correct)\n");
|
---|
88 | }
|
---|
89 | }
|
---|
90 |
|
---|
91 | int main() {
|
---|
92 | test_isomorphism_boost();
|
---|
93 | }
|
---|