1 // (C) Copyright David Gleich 2007
2 //
3 // Use, modification and distribution are subject to the
4 // Boost Software License, Version 1.0 (See accompanying file
5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
6
7 #include <vector>
8 #include <boost/graph/adjacency_list.hpp>
9 #include <boost/graph/core_numbers.hpp>
10 #include <boost/property_map/property_map.hpp>
11 #include <stdio.h>
12
13 using namespace boost;
14
15 const char* errstr = "";
16
test_1()17 int test_1()
18 {
19 // core numbers of sample graph
20 typedef adjacency_list< vecS, vecS, undirectedS > Graph;
21
22 Graph G(21);
23 add_edge(0, 1, G);
24 add_edge(1, 2, G);
25 add_edge(1, 3, G);
26 add_edge(2, 3, G);
27 add_edge(1, 4, G);
28 add_edge(3, 4, G);
29 add_edge(4, 5, G);
30 add_edge(4, 6, G);
31 add_edge(5, 6, G);
32 add_edge(4, 7, G);
33 add_edge(5, 7, G);
34 add_edge(6, 7, G);
35 add_edge(7, 8, G);
36 add_edge(3, 9, G);
37 add_edge(8, 9, G);
38 add_edge(8, 10, G);
39 add_edge(9, 10, G);
40 add_edge(10, 11, G);
41 add_edge(10, 12, G);
42 add_edge(3, 13, G);
43 add_edge(9, 13, G);
44 add_edge(3, 14, G);
45 add_edge(9, 14, G);
46 add_edge(13, 14, G);
47 add_edge(16, 17, G);
48 add_edge(16, 18, G);
49 add_edge(17, 19, G);
50 add_edge(18, 19, G);
51 add_edge(19, 20, G);
52
53 std::vector< int > core_nums(num_vertices(G));
54 core_numbers(
55 G, make_iterator_property_map(core_nums.begin(), get(vertex_index, G)));
56
57 for (size_t i = 0; i < num_vertices(G); ++i)
58 {
59 printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
60 }
61
62 int correct[21]
63 = { 1, 2, 2, 3, 3, 3, 3, 3, 2, 3, 2, 1, 1, 3, 3, 0, 2, 2, 2, 2, 1 };
64 for (size_t i = 0; i < num_vertices(G); ++i)
65 {
66 if (core_nums[i] != correct[i])
67 {
68 return 1; // error!
69 }
70 }
71 return 0;
72 }
73
test_2()74 int test_2()
75 {
76 // core numbers of sample graph
77 typedef adjacency_list< listS, vecS, undirectedS, no_property,
78 property< edge_weight_t, int > >
79 graph_t;
80 int num_nodes = 3;
81 typedef std::pair< int, int > Edge;
82
83 Edge edge_array[] = { Edge(0, 1), Edge(0, 2), Edge(1, 2) };
84 int weights[] = { -1, -2, -2 };
85 int num_arcs = sizeof(edge_array) / sizeof(Edge);
86
87 graph_t G(edge_array, edge_array + num_arcs, weights, num_nodes);
88
89 std::vector< int > core_nums(num_vertices(G));
90 weighted_core_numbers(
91 G, make_iterator_property_map(core_nums.begin(), get(vertex_index, G)));
92
93 for (size_t i = 0; i < num_vertices(G); ++i)
94 {
95 printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
96 }
97
98 int correct[3] = { -1, -1, -4 };
99 for (size_t i = 0; i < num_vertices(G); ++i)
100 {
101 if (core_nums[i] != correct[i])
102 {
103 return 1; // error!
104 }
105 }
106 return 0;
107 }
108
test_3()109 int test_3()
110 {
111 // core numbers of a directed graph, the core numbers of a directed
112 // cycle are always one
113 typedef adjacency_list< vecS, vecS, directedS > graph_t;
114 int num_nodes = 5;
115 typedef std::pair< int, int > Edge;
116
117 Edge edge_array[]
118 = { Edge(0, 1), Edge(1, 2), Edge(2, 3), Edge(3, 4), Edge(4, 0) };
119 int num_arcs = sizeof(edge_array) / sizeof(Edge);
120
121 graph_t G(edge_array, edge_array + num_arcs, num_nodes);
122
123 std::vector< int > core_nums(num_vertices(G));
124 core_numbers(
125 G, make_iterator_property_map(core_nums.begin(), get(vertex_index, G)));
126
127 for (size_t i = 0; i < num_vertices(G); ++i)
128 {
129 printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
130 }
131
132 int correct[5] = { 1, 1, 1, 1, 1 };
133 for (size_t i = 0; i < num_vertices(G); ++i)
134 {
135 if (core_nums[i] != correct[i])
136 {
137 return 1; // error!
138 }
139 }
140 return 0;
141 }
142
main(int,char **)143 int main(int, char**)
144 {
145 int nfail = 0, ntotal = 0;
146 int rval;
147
148 const char* name;
149
150 name = "core_numbers";
151 rval = test_1();
152 ntotal++;
153 if (rval != 0)
154 {
155 nfail++;
156 printf("%20s %50s\n", name, errstr);
157 }
158 else
159 {
160 printf("%20s success\n", name);
161 }
162
163 name = "weighted_core_numbers";
164 rval = test_2();
165 ntotal++;
166 if (rval != 0)
167 {
168 nfail++;
169 printf("%20s %50s\n", name, errstr);
170 }
171 else
172 {
173 printf("%20s success\n", name);
174 }
175
176 name = "directed_corenums";
177 rval = test_3();
178 ntotal++;
179 if (rval != 0)
180 {
181 nfail++;
182 printf("%20s %50s\n", name, errstr);
183 }
184 else
185 {
186 printf("%20s success\n", name);
187 }
188
189 printf("\n");
190 printf("Total tests : %3i\n", ntotal);
191 printf("Total failed : %3i\n", nfail);
192
193 return nfail != 0;
194 }
195