1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2008-2012 Gabor Csardi <csardi.gabor@gmail.com>
5 334 Harvard street, Cambridge, MA 02139 USA
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301 USA
21
22 */
23
24 #include <igraph.h>
25 #include "test_utilities.inc"
26
main()27 int main() {
28
29 igraph_t g;
30 igraph_vector_t bet, bet2, weights, edges;
31
32 igraph_real_t cutoff = 0.0;
33
34 igraph_real_t nontriv[] = { 0, 19, 0, 16, 0, 20, 1, 19, 2, 5, 3, 7, 3, 8,
35 4, 15, 4, 11, 5, 8, 5, 19, 6, 7, 6, 10, 6, 8,
36 6, 9, 7, 20, 9, 10, 9, 20, 10, 19,
37 11, 12, 11, 20, 12, 15, 13, 15,
38 14, 18, 14, 16, 14, 17, 15, 16, 17, 18
39 };
40
41 igraph_real_t nontriv_weights[] = { 0.5249, 1, 0.1934, 0.6274, 0.5249,
42 0.0029, 0.3831, 0.05, 0.6274, 0.3831,
43 0.5249, 0.0587, 0.0579, 0.0562, 0.0562,
44 0.1934, 0.6274, 0.6274, 0.6274, 0.0418,
45 0.6274, 0.3511, 0.3511, 0.1486, 1, 1,
46 0.0711, 0.2409
47 };
48
49 igraph_real_t nontriv_res[] = { 20, 0, 0, 0, 0, 19, 80, 85, 32, 0, 10,
50 75, 70, 0, 36, 81, 60, 0, 19, 19, 86
51 };
52
53 /*******************************************************/
54
55 printf("BA graph\n");
56 printf("==========================================================\n");
57 igraph_barabasi_game(/* graph= */ &g,
58 /* n= */ 1000,
59 /* power= */ 1,
60 /* m= */ 3,
61 /* outseq= */ 0,
62 /* outpref= */ 0,
63 /* A= */ 1,
64 /* directed= */ 0,
65 /* algo= */ IGRAPH_BARABASI_BAG,
66 /* start_from= */ 0);
67
68 igraph_simplify(&g, /* multiple= */ 1, /* loops= */ 1, /*edge_comb=*/ 0);
69
70 igraph_vector_init(&bet, 0);
71
72 igraph_betweenness_cutoff(/* graph= */ &g,
73 /* res= */ &bet,
74 /* vids= */ igraph_vss_all(),
75 /* directed = */ 0,
76 /* weights= */ 0,
77 /* cutoff= */ 2);
78
79 igraph_vector_destroy(&bet);
80 igraph_destroy(&g);
81
82 printf("\nTree\n");
83 printf("==========================================================\n");
84 igraph_tree(&g, 20000, 10, IGRAPH_TREE_UNDIRECTED);
85
86 igraph_vector_init(&bet, 0);
87
88 igraph_betweenness_cutoff(/* graph= */ &g,
89 /* res= */ &bet,
90 /* vids= */ igraph_vss_all(),
91 /* directed = */ 0,
92 /* weights= */ 0,
93 /* cutoff= */ 3);
94
95 printf("Max betweenness: %f\n", igraph_vector_max(&bet));
96
97 igraph_vector_init(&bet2, 0);
98 igraph_vector_init(&weights, igraph_ecount(&g));
99 igraph_vector_fill(&weights, 1.0);
100
101 igraph_betweenness_cutoff(/* graph= */ &g,
102 /* res= */ &bet2,
103 /* vids= */ igraph_vss_all(),
104 /* directed = */ 0,
105 /* weights= */ &weights,
106 /* cutoff= */ 3);
107
108 IGRAPH_ASSERT(igraph_vector_all_e(&bet, &bet2));
109
110 igraph_vector_destroy(&bet);
111 igraph_vector_destroy(&bet2);
112 igraph_vector_destroy(&weights);
113 igraph_destroy(&g);
114
115 printf("\nNon-trivial weighted graph\n");
116 printf("==========================================================\n");
117 igraph_vector_view(&edges, nontriv, sizeof(nontriv) / sizeof(igraph_real_t));
118 igraph_create(&g, &edges, 0, /* directed= */ 0);
119 igraph_vector_view(&weights, nontriv_weights,
120 sizeof(nontriv_weights) / sizeof(igraph_real_t));
121 igraph_vector_init(&bet, 0);
122
123 igraph_betweenness(/*graph=*/ &g, /*res=*/ &bet, /*vids=*/ igraph_vss_all(),
124 /*directed=*/0, /*weights=*/ &weights);
125
126 printf("Max betweenness: %f\n", igraph_vector_max(&bet));
127
128 igraph_vector_view(&bet2, nontriv_res,
129 sizeof(nontriv_res) / sizeof(igraph_real_t));
130
131 IGRAPH_ASSERT(igraph_vector_all_e(&bet, &bet2));
132
133 igraph_vector_destroy(&bet);
134 igraph_destroy(&g);
135
136
137 printf("\nCorner case cutoff 0.0\n");
138 printf("==========================================================\n");
139 igraph_tree(&g, 20, 3, IGRAPH_TREE_UNDIRECTED);
140
141 /* unweighted */
142 igraph_vector_init(&bet, 0);
143 igraph_betweenness_cutoff(/* graph= */ &g,
144 /* res= */ &bet,
145 /* vids= */ igraph_vss_all(),
146 /* directed = */ 0,
147 /* weights= */ 0,
148 /* cutoff= */ 0);
149
150 igraph_vector_init(&bet2, 0);
151 igraph_betweenness_cutoff(/* graph= */ &g,
152 /* res= */ &bet2,
153 /* vids= */ igraph_vss_all(),
154 /* directed = */ 0,
155 /* weights= */ 0,
156 /* cutoff= */ -1);
157
158 igraph_vector_print(&bet);
159 igraph_vector_print(&bet2);
160
161 igraph_vector_destroy(&bet);
162 igraph_vector_destroy(&bet2);
163
164 /* weighted */
165 igraph_vector_init(&weights, igraph_ecount(&g));
166 igraph_vector_fill(&weights, 2.0);
167
168 igraph_vector_init(&bet, 0);
169 igraph_betweenness_cutoff(/* graph= */ &g,
170 /* res= */ &bet,
171 /* vids= */ igraph_vss_all(),
172 /* directed = */ 0,
173 /* weights= */ &weights,
174 /* cutoff= */ 0);
175
176 igraph_vector_init(&bet2, 0);
177 igraph_betweenness_cutoff(/* graph= */ &g,
178 /* res= */ &bet2,
179 /* vids= */ igraph_vss_all(),
180 /* directed = */ 0,
181 /* weights= */ &weights,
182 /* cutoff= */ -1);
183
184 igraph_vector_print(&bet);
185 igraph_vector_print(&bet2);
186
187 igraph_vector_destroy(&bet);
188 igraph_vector_destroy(&bet2);
189 igraph_vector_destroy(&weights);
190 igraph_destroy(&g);
191
192 printf("\nSingle path graph\n");
193 printf("==========================================================\n");
194 igraph_small(&g, 5, IGRAPH_UNDIRECTED,
195 0, 1,
196 1, 2,
197 2, 3,
198 3, 4, -1);
199 igraph_vector_init(&bet, igraph_vcount(&g));
200 igraph_vector_init(&bet2, igraph_vcount(&g));
201 igraph_vector_init(&weights, igraph_ecount(&g));
202 igraph_vector_fill(&weights, 1);
203
204 for (cutoff = -1.0; cutoff < 5.0; cutoff += 1)
205 {
206 printf("Cutoff %.0f\n", cutoff);
207 printf("Unweighted\n");
208 igraph_betweenness_cutoff(&g, &bet,
209 igraph_vss_all(), IGRAPH_UNDIRECTED,
210 /* weights */ NULL,
211 /* cutoff */ cutoff);
212 igraph_vector_print(&bet);
213
214 printf("Weighted\n");
215 igraph_betweenness_cutoff(&g, &bet2,
216 igraph_vss_all(), IGRAPH_UNDIRECTED,
217 /* weights */ &weights,
218 /* cutoff */ cutoff);
219 igraph_vector_print(&bet2);
220 printf("\n");
221
222 IGRAPH_ASSERT(igraph_vector_all_e(&bet, &bet2));
223 }
224
225 igraph_vector_destroy(&bet);
226 igraph_vector_destroy(&bet2);
227 igraph_vector_destroy(&weights);
228 igraph_destroy(&g);
229
230 printf("\nCycle graph\n");
231 printf("==========================================================\n");
232 igraph_small(&g, 4, IGRAPH_UNDIRECTED,
233 0, 1,
234 0, 2,
235 1, 3,
236 2, 3, -1);
237 igraph_vector_init(&bet, igraph_vcount(&g));
238 igraph_vector_init(&bet2, igraph_vcount(&g));
239 igraph_vector_init(&weights, igraph_ecount(&g));
240 VECTOR(weights)[0] = 1.01;
241 VECTOR(weights)[1] = 2;
242 VECTOR(weights)[2] = 0.99;
243 VECTOR(weights)[3] = 2;
244
245 for (cutoff = -1.0; cutoff < 5.0; cutoff += 1)
246 {
247 printf("Cutoff %.0f\n", cutoff);
248 printf("Unweighted\n");
249 igraph_betweenness_cutoff(&g, &bet,
250 igraph_vss_all(), IGRAPH_UNDIRECTED,
251 /* weights */ NULL,
252 /* cutoff */ cutoff);
253 igraph_vector_print(&bet);
254
255 printf("Weighted\n");
256 igraph_betweenness_cutoff(&g, &bet2,
257 igraph_vss_all(), IGRAPH_UNDIRECTED,
258 /* weights */ &weights,
259 /* cutoff */ cutoff);
260 igraph_vector_print(&bet2);
261 printf("\n");
262 }
263
264 igraph_vector_destroy(&bet);
265 igraph_vector_destroy(&bet2);
266 igraph_vector_destroy(&weights);
267 igraph_destroy(&g);
268
269 printf("\nNull graph\n");
270 printf("==========================================================\n");
271
272 igraph_empty(&g, 0, IGRAPH_UNDIRECTED);
273 igraph_vector_init(&bet, 3); /* purposefully larger than zero, as igraph_betweenness must resize it */
274 igraph_betweenness(&g, &bet, igraph_vss_all(), IGRAPH_UNDIRECTED, NULL);
275 print_vector(&bet);
276
277 igraph_vector_destroy(&bet);
278 igraph_destroy(&g);
279
280 printf("\nEmpty graph\n");
281 printf("==========================================================\n");
282
283 igraph_empty(&g, 2, IGRAPH_UNDIRECTED);
284 igraph_vector_init(&bet, 0);
285 igraph_betweenness(&g, &bet, igraph_vss_all(), IGRAPH_UNDIRECTED, NULL);
286 print_vector(&bet);
287
288 igraph_vector_destroy(&bet);
289 igraph_destroy(&g);
290
291 printf("\n37x37 grid graph\n");
292 printf("==========================================================\n");
293
294 {
295 igraph_vector_t dims;
296
297 igraph_vector_init(&dims, 2);
298 VECTOR(dims)[0] = 37;
299 VECTOR(dims)[1] = 37;
300
301 igraph_lattice(&g, &dims, 1, IGRAPH_UNDIRECTED, 0, 0);
302
303 igraph_vector_init(&bet, 0);
304 igraph_betweenness(&g, &bet, igraph_vss_all(), IGRAPH_UNDIRECTED, NULL);
305 printf("Max betweenness: %f\n", igraph_vector_max(&bet));
306
307 igraph_vector_destroy(&bet);
308 igraph_destroy(&g);
309 igraph_vector_destroy(&dims);
310 }
311
312 VERIFY_FINALLY_STACK();
313
314 return 0;
315 }
316