1 | #include <stdio.h>
|
---|
2 | #include <iostream>
|
---|
3 |
|
---|
4 | #include <boost/shared_ptr.hpp>
|
---|
5 |
|
---|
6 | #include <boost/graph/graph_traits.hpp>
|
---|
7 | #include <boost/graph/isomorphism.hpp>
|
---|
8 | #include <boost/graph/graph_utility.hpp>
|
---|
9 | #include <boost/graph/adjacency_list.hpp>
|
---|
10 |
|
---|
11 | using namespace boost;
|
---|
12 |
|
---|
13 | // adjacency_list-based type
|
---|
14 | typedef adjacency_list < vecS, vecS, undirectedS > SimpleGraph;
|
---|
15 |
|
---|
16 | void initializeGraph(int numOfSides, shared_ptr<SimpleGraph> graph)
|
---|
17 | {
|
---|
18 | // "Ridges" connecting the vertices of the upper polygon
|
---|
19 | // with the corresponding vertices of the lower polygon
|
---|
20 | for(int ii = 0; ii < numOfSides; ++ii)
|
---|
21 | add_edge(ii, ii + numOfSides, *graph);
|
---|
22 |
|
---|
23 | // Edges on the lower polygon
|
---|
24 | for(int ii = 0; ii < numOfSides - 1; ++ii)
|
---|
25 | add_edge(ii, ii + 1, *graph);
|
---|
26 | add_edge(numOfSides - 1, 0, *graph);
|
---|
27 |
|
---|
28 | // Edges on the upper polygon
|
---|
29 | for(int ii = numOfSides; ii < 2 * numOfSides - 1; ++ii)
|
---|
30 | add_edge(ii, ii + 1, *graph);
|
---|
31 | add_edge(2 * numOfSides - 1 , numOfSides, *graph);
|
---|
32 | }
|
---|
33 |
|
---|
34 | void isomorphism_test(int numOfSides)
|
---|
35 | {
|
---|
36 | // Create and initialize the graphs
|
---|
37 | shared_ptr<SimpleGraph> g1(new SimpleGraph(2 * numOfSides));
|
---|
38 | shared_ptr<SimpleGraph> g2(new SimpleGraph(2 * numOfSides));
|
---|
39 | initializeGraph(numOfSides, g1);
|
---|
40 | initializeGraph(numOfSides, g2);
|
---|
41 |
|
---|
42 |
|
---|
43 | std::cout << "\n\n GRAPH PROPERTIES \n" << std::endl;
|
---|
44 | std::cout << "num. of vert.: " << num_vertices(*g1) << std::endl;
|
---|
45 | std::cout << "num. of edges: " << num_edges(*g1) << std::endl;
|
---|
46 |
|
---|
47 |
|
---|
48 | // Do some logging
|
---|
49 | int maxDegree = 0;
|
---|
50 | int maxDegreeCount = 1;
|
---|
51 | boost::graph_traits<SimpleGraph>::vertex_iterator vIt,vItEnd;
|
---|
52 | for (tie(vIt, vItEnd) = vertices(*g1); vIt != vItEnd; ++vIt)
|
---|
53 | {
|
---|
54 | int degree = out_degree(*vIt, *g1);
|
---|
55 | if (maxDegree < degree) {
|
---|
56 | maxDegree = degree;
|
---|
57 | maxDegreeCount = 1;
|
---|
58 | }
|
---|
59 | else if (maxDegree == degree)
|
---|
60 | maxDegreeCount++;
|
---|
61 |
|
---|
62 | }
|
---|
63 | std::cout << "max.degree: " << maxDegree << "; num. of vert. with max. degree: " << maxDegreeCount << std::endl;
|
---|
64 |
|
---|
65 |
|
---|
66 | std::cout << "\n\n ISOMOROPHISM TEST \n" << std::endl;
|
---|
67 | boost::property_map<SimpleGraph, boost::vertex_index_t>::type ref_index_map = get(vertex_index, *g1);
|
---|
68 | std::vector<boost::graph_traits<SimpleGraph>::vertex_descriptor> iso(num_vertices(*g2));
|
---|
69 | bool ret = isomorphism(*g1,*g2,
|
---|
70 | isomorphism_map(make_iterator_property_map(iso.begin(), ref_index_map, iso[0])));
|
---|
71 | std::cout << "Is isomorphic: " << ret << std::endl;
|
---|
72 | }
|
---|
73 |
|
---|
74 | int main(int argc, char** argv)
|
---|
75 | {
|
---|
76 | std::cout << "BGLTest" << std::endl;
|
---|
77 | if (2 != argc) {
|
---|
78 | std::cout << "Please give the number of sides as argument." << std::endl;
|
---|
79 | exit(0);
|
---|
80 | }
|
---|
81 |
|
---|
82 | if (getenv("COV_DEBUG_STOP"))
|
---|
83 | {
|
---|
84 | int ii = 0;
|
---|
85 | while (ii != 1);
|
---|
86 | }
|
---|
87 |
|
---|
88 | int numOfSides = atoi(argv[1]);
|
---|
89 | std::cout << "Working with polyhedron, with " << numOfSides << " number of sides." << std::endl;
|
---|
90 |
|
---|
91 | // Test isomorphism
|
---|
92 | isomorphism_test(numOfSides);
|
---|
93 |
|
---|
94 | return 0;
|
---|
95 | }
|
---|