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
13using namespace boost;
14
15const char* errstr = "";
16
17int 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
74int 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
109int 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
143int 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

source code of boost/libs/graph/test/core_numbers_test.cpp