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 // core numbers of sample graph
19 typedef adjacency_list<vecS,vecS,undirectedS> Graph;
20
21 Graph G(21);
22 add_edge(0,1,G);
23 add_edge(1,2,G);
24 add_edge(1,3,G);
25 add_edge(2,3,G);
26 add_edge(1,4,G);
27 add_edge(3,4,G);
28 add_edge(4,5,G);
29 add_edge(4,6,G);
30 add_edge(5,6,G);
31 add_edge(4,7,G);
32 add_edge(5,7,G);
33 add_edge(6,7,G);
34 add_edge(7,8,G);
35 add_edge(3,9,G);
36 add_edge(8,9,G);
37 add_edge(8,10,G);
38 add_edge(9,10,G);
39 add_edge(10,11,G);
40 add_edge(10,12,G);
41 add_edge(3,13,G);
42 add_edge(9,13,G);
43 add_edge(3,14,G);
44 add_edge(9,14,G);
45 add_edge(13,14,G);
46 add_edge(16,17,G);
47 add_edge(16,18,G);
48 add_edge(17,19,G);
49 add_edge(18,19,G);
50 add_edge(19,20,G);
51
52 std::vector<int> core_nums(num_vertices(G));
53 core_numbers(G,
54 make_iterator_property_map(core_nums.begin(), get(vertex_index,G)));
55
56 for (size_t i=0; i<num_vertices(G); ++i) {
57 printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
58 }
59
60 int correct[21]={1,2,2,3,3,3,3,3,2,3,2,1,1,3,3,0,2,2,2,2,1};
61 for (size_t i=0; i<num_vertices(G); ++i) {
62 if (core_nums[i] != correct[i]) {
63 return 1; // error!
64 }
65 }
66 return 0;
67 }
68
test_2()69 int test_2() {
70 // core numbers of sample graph
71 typedef adjacency_list < listS, vecS, undirectedS,
72 no_property, property < edge_weight_t, int > > graph_t;
73 int num_nodes = 3;
74 typedef std::pair<int,int> Edge;
75
76 Edge edge_array[] = { Edge(0,1), Edge(0,2), Edge(1,2) };
77 int weights[] = {-1, -2, -2};
78 int num_arcs = sizeof(edge_array) / sizeof(Edge);
79
80 graph_t G(edge_array, edge_array + num_arcs, weights, num_nodes);
81
82 std::vector<int> core_nums(num_vertices(G));
83 weighted_core_numbers(G,
84 make_iterator_property_map(core_nums.begin(), get(vertex_index,G)));
85
86 for (size_t i=0; i<num_vertices(G); ++i) {
87 printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
88 }
89
90 int correct[3]={-1,-1,-4};
91 for (size_t i=0; i<num_vertices(G); ++i) {
92 if (core_nums[i] != correct[i]) {
93 return 1; // error!
94 }
95 }
96 return 0;
97 }
98
test_3()99 int test_3() {
100 // core numbers of a directed graph, the core numbers of a directed
101 // cycle are always one
102 typedef adjacency_list < vecS, vecS, directedS > graph_t;
103 int num_nodes = 5;
104 typedef std::pair<int,int> Edge;
105
106 Edge edge_array[] = { Edge(0,1),Edge(1,2),Edge(2,3),Edge(3,4),Edge(4,0) };
107 int num_arcs = sizeof(edge_array) / sizeof(Edge);
108
109 graph_t G(edge_array, edge_array + num_arcs, num_nodes);
110
111 std::vector<int> core_nums(num_vertices(G));
112 core_numbers(G,
113 make_iterator_property_map(core_nums.begin(), get(vertex_index,G)));
114
115 for (size_t i=0; i<num_vertices(G); ++i) {
116 printf("vertex %3lu : %i\n", (unsigned long)i, core_nums[i]);
117 }
118
119 int correct[5]={1,1,1,1,1};
120 for (size_t i=0; i<num_vertices(G); ++i) {
121 if (core_nums[i] != correct[i]) {
122 return 1; // error!
123 }
124 }
125 return 0;
126 }
127
main(int,char **)128 int main(int, char **) {
129 int nfail = 0, ntotal = 0;
130 int rval;
131
132 const char* name;
133
134 name= "core_numbers";
135 rval= test_1(); ntotal++;
136 if (rval!= 0) { nfail++; printf("%20s %50s\n", name, errstr); }
137 else { printf("%20s success\n", name); }
138
139 name= "weighted_core_numbers";
140 rval= test_2(); ntotal++;
141 if (rval!= 0) { nfail++; printf("%20s %50s\n", name, errstr); }
142 else { printf("%20s success\n", name); }
143
144 name= "directed_corenums";
145 rval= test_3(); ntotal++;
146 if (rval!= 0) { nfail++; printf("%20s %50s\n", name, errstr); }
147 else { printf("%20s success\n", name); }
148
149 printf("\n");
150 printf("Total tests : %3i\n", ntotal);
151 printf("Total failed : %3i\n", nfail);
152
153 return nfail!=0;
154 }
155