1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2009-2021 The igraph development team
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301 USA
20
21 */
22
23 #include <igraph.h>
24
25 #include "test_utilities.inc"
26
bfs_callback(const igraph_t * graph,igraph_integer_t vid,igraph_integer_t pred,igraph_integer_t succ,igraph_integer_t rank,igraph_integer_t dist,void * extra)27 igraph_bool_t bfs_callback(const igraph_t *graph,
28 igraph_integer_t vid,
29 igraph_integer_t pred,
30 igraph_integer_t succ,
31 igraph_integer_t rank,
32 igraph_integer_t dist,
33 void *extra) {
34 printf(" %li", (long int) vid);
35 return 0;
36 }
37
main()38 int main() {
39
40 igraph_t graph, ring;
41 igraph_vector_t order, rank, father, pred, succ, dist;
42 igraph_vector_t restricted;
43 igraph_vector_t roots;
44 long int i;
45
46 igraph_ring(&ring, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
47 igraph_disjoint_union(&graph, &ring, &ring);
48 igraph_destroy(&ring);
49
50 igraph_vector_init(&order, 0);
51 igraph_vector_init(&rank, 0);
52 igraph_vector_init(&father, 0);
53 igraph_vector_init(&pred, 0);
54 igraph_vector_init(&succ, 0);
55 igraph_vector_init(&dist, 0);
56
57 igraph_bfs(&graph, /*root=*/0, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT,
58 /*unreachable=*/ 1, /*restricted=*/ 0,
59 &order, &rank, &father, &pred, &succ, &dist,
60 /*callback=*/ 0, /*extra=*/ 0);
61
62 print_vector_round(&order);
63 print_vector_round(&rank);
64 print_vector_round(&father);
65 print_vector_round(&pred);
66 print_vector_round(&succ);
67 print_vector_round(&dist);
68
69 igraph_vector_destroy(&order);
70 igraph_vector_destroy(&rank);
71 igraph_vector_destroy(&father);
72 igraph_vector_destroy(&pred);
73 igraph_vector_destroy(&succ);
74 igraph_vector_destroy(&dist);
75
76 /* Test the callback */
77
78 printf("(");
79 igraph_bfs(&graph, /*root=*/ 0, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT,
80 /*unreachable=*/ 1, /*restricted=*/ 0,
81 0, 0, 0, 0, 0, 0, &bfs_callback, 0);
82 printf(" )\n");
83
84 /* Test different roots */
85
86 printf("(");
87 igraph_bfs(&graph, /*root=*/ 2, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT,
88 /*unreachable=*/ 1, /*restricted=*/ 0,
89 0, 0, 0, 0, 0, 0, &bfs_callback, 0);
90 printf(" )\n");
91
92 /* Test restricted */
93
94 igraph_vector_init(&restricted, 0);
95 for (i = 5; i < igraph_vcount(&graph); i++) {
96 igraph_vector_push_back(&restricted, i);
97 }
98 printf("(");
99 igraph_bfs(&graph, /*root=*/ 5, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT,
100 /*unreachable=*/ 1, &restricted,
101 0, 0, 0, 0, 0, 0, &bfs_callback, 0);
102 printf(" )\n");
103
104 /* Root not in restricted set */
105
106 printf("(");
107 igraph_bfs(&graph, /*root=*/ 4, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT,
108 /*unreachable=*/ 1, &restricted,
109 0, 0, 0, 0, 0, 0, &bfs_callback, 0);
110 printf(" )\n");
111
112 printf("(");
113 igraph_bfs(&graph, /*root=*/ 3, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT,
114 /*unreachable=*/ 0, &restricted,
115 0, 0, 0, 0, 0, 0, &bfs_callback, 0);
116 printf(" )\n");
117
118 /* Multiple root vertices */
119
120 igraph_vector_init(&roots, 3);
121 VECTOR(roots)[0] = 3;
122 VECTOR(roots)[1] = 4;
123 VECTOR(roots)[2] = 6;
124 printf("(");
125 igraph_bfs(&graph, /*root=*/ -1, &roots, /*neimode=*/ IGRAPH_OUT,
126 /*unreachable=*/ 0, &restricted,
127 0, 0, 0, 0, 0, 0, &bfs_callback, 0);
128 printf(" )\n");
129
130 igraph_vector_destroy(&roots);
131 igraph_vector_destroy(&restricted);
132 igraph_destroy(&graph);
133
134 VERIFY_FINALLY_STACK();
135
136 return 0;
137 }
138