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 | |
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(u: 0, v: 1, g_&: G); |
24 | add_edge(u: 1, v: 2, g_&: G); |
25 | add_edge(u: 1, v: 3, g_&: G); |
26 | add_edge(u: 2, v: 3, g_&: G); |
27 | add_edge(u: 1, v: 4, g_&: G); |
28 | add_edge(u: 3, v: 4, g_&: G); |
29 | add_edge(u: 4, v: 5, g_&: G); |
30 | add_edge(u: 4, v: 6, g_&: G); |
31 | add_edge(u: 5, v: 6, g_&: G); |
32 | add_edge(u: 4, v: 7, g_&: G); |
33 | add_edge(u: 5, v: 7, g_&: G); |
34 | add_edge(u: 6, v: 7, g_&: G); |
35 | add_edge(u: 7, v: 8, g_&: G); |
36 | add_edge(u: 3, v: 9, g_&: G); |
37 | add_edge(u: 8, v: 9, g_&: G); |
38 | add_edge(u: 8, v: 10, g_&: G); |
39 | add_edge(u: 9, v: 10, g_&: G); |
40 | add_edge(u: 10, v: 11, g_&: G); |
41 | add_edge(u: 10, v: 12, g_&: G); |
42 | add_edge(u: 3, v: 13, g_&: G); |
43 | add_edge(u: 9, v: 13, g_&: G); |
44 | add_edge(u: 3, v: 14, g_&: G); |
45 | add_edge(u: 9, v: 14, g_&: G); |
46 | add_edge(u: 13, v: 14, g_&: G); |
47 | add_edge(u: 16, v: 17, g_&: G); |
48 | add_edge(u: 16, v: 18, g_&: G); |
49 | add_edge(u: 17, v: 19, g_&: G); |
50 | add_edge(u: 18, v: 19, g_&: G); |
51 | add_edge(u: 19, v: 20, g_&: G); |
52 | |
53 | std::vector< int > core_nums(num_vertices(g_: G)); |
54 | core_numbers( |
55 | g&: G, c: make_iterator_property_map(iter: core_nums.begin(), id: get(p: vertex_index, g&: G))); |
56 | |
57 | for (size_t i = 0; i < num_vertices(g_: G); ++i) |
58 | { |
59 | printf(format: "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_: G); ++i) |
65 | { |
66 | if (core_nums[i] != correct[i]) |
67 | { |
68 | return 1; // error! |
69 | } |
70 | } |
71 | return 0; |
72 | } |
73 | |
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_: G)); |
90 | weighted_core_numbers( |
91 | g&: G, c: make_iterator_property_map(iter: core_nums.begin(), id: get(p: vertex_index, g&: G))); |
92 | |
93 | for (size_t i = 0; i < num_vertices(g_: G); ++i) |
94 | { |
95 | printf(format: "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_: G); ++i) |
100 | { |
101 | if (core_nums[i] != correct[i]) |
102 | { |
103 | return 1; // error! |
104 | } |
105 | } |
106 | return 0; |
107 | } |
108 | |
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_: G)); |
124 | core_numbers( |
125 | g&: G, c: make_iterator_property_map(iter: core_nums.begin(), id: get(p: vertex_index, g&: G))); |
126 | |
127 | for (size_t i = 0; i < num_vertices(g_: G); ++i) |
128 | { |
129 | printf(format: "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_: G); ++i) |
134 | { |
135 | if (core_nums[i] != correct[i]) |
136 | { |
137 | return 1; // error! |
138 | } |
139 | } |
140 | return 0; |
141 | } |
142 | |
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(format: "%20s %50s\n" , name, errstr); |
157 | } |
158 | else |
159 | { |
160 | printf(format: "%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(format: "%20s %50s\n" , name, errstr); |
170 | } |
171 | else |
172 | { |
173 | printf(format: "%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(format: "%20s %50s\n" , name, errstr); |
183 | } |
184 | else |
185 | { |
186 | printf(format: "%20s success\n" , name); |
187 | } |
188 | |
189 | printf(format: "\n" ); |
190 | printf(format: "Total tests : %3i\n" , ntotal); |
191 | printf(format: "Total failed : %3i\n" , nfail); |
192 | |
193 | return nfail != 0; |
194 | } |
195 | |