1 /*
2 IGraph library.
3 Copyright (C) 2021 The igraph development team <igraph@igraph.org>
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>.
17 */
18
19 #include <igraph.h>
20
21 #include "test_utilities.inc"
22
main()23 int main() {
24 igraph_t graph;
25 igraph_vector_ptr_t paths;
26 igraph_vector_t nrgeo, weights;
27 igraph_integer_t from, to;
28 long int i;
29
30 igraph_vector_ptr_init(&paths, 0);
31 IGRAPH_VECTOR_PTR_SET_ITEM_DESTRUCTOR(&paths, igraph_vector_destroy);
32 igraph_vector_init(&nrgeo, 0);
33
34 igraph_vector_init(&weights, 0);
35
36 /* Note on the output:
37 * get_all_shortest_paths functions sort their output based on the
38 * last vertex only. Thus the ordering is not fully defined.
39 *
40 * This test does not currently canonicalize (i.e. sort)
41 * the result before printing it.
42 */
43
44 printf("Singleton graph\n");
45 igraph_empty(&graph, 1, IGRAPH_UNDIRECTED);
46
47 from = 0; to = 0;
48
49 igraph_get_all_shortest_paths(&graph, &paths, &nrgeo, from, igraph_vss_1(to), IGRAPH_ALL);
50
51 for (i=0; i < igraph_vector_ptr_size(&paths); ++i) {
52 print_vector(VECTOR(paths)[i]);
53 }
54 IGRAPH_ASSERT(igraph_vector_ptr_size(&paths) == VECTOR(nrgeo)[to]);
55
56 igraph_vector_ptr_free_all(&paths);
57
58 printf("\nSingleton graph, weighted\n");
59 igraph_vector_resize(&weights, igraph_ecount(&graph));
60 igraph_vector_fill(&weights, 1);
61 igraph_get_all_shortest_paths_dijkstra(&graph, &paths, &nrgeo, from, igraph_vss_1(to), &weights, IGRAPH_ALL);
62
63 for (i=0; i < igraph_vector_ptr_size(&paths); ++i) {
64 print_vector(VECTOR(paths)[i]);
65 }
66 IGRAPH_ASSERT(igraph_vector_ptr_size(&paths) == VECTOR(nrgeo)[to]);
67
68 igraph_vector_ptr_free_all(&paths);
69
70 igraph_destroy(&graph);
71
72 printf("\nNo paths\n");
73 igraph_empty(&graph, 2, IGRAPH_UNDIRECTED);
74
75 from = 0; to = 1;
76
77 igraph_get_all_shortest_paths(&graph, &paths, &nrgeo, from, igraph_vss_1(to), IGRAPH_ALL);
78
79 for (i=0; i < igraph_vector_ptr_size(&paths); ++i) {
80 print_vector(VECTOR(paths)[i]);
81 }
82 IGRAPH_ASSERT(igraph_vector_ptr_size(&paths) == VECTOR(nrgeo)[to]);
83
84 igraph_vector_ptr_free_all(&paths);
85
86 igraph_destroy(&graph);
87
88 /* This graph has multi-edges (which induce multiple paths of the
89 * same length) as well as more paths of the same length between
90 * vertices 0 and 4. */
91 igraph_small(&graph, 0, IGRAPH_ADJ_UNDIRECTED,
92 0, 1, 1, 2, 2, 3, 3, 4, 0, 1, 2, 5, 4, 5, 1, 6, 6, 7, 3, 7,
93 -1);
94
95 from = 0; to = 4;
96
97 printf("\nUnweighted\n");
98 igraph_get_all_shortest_paths(&graph, &paths, &nrgeo, from, igraph_vss_1(to), IGRAPH_ALL);
99
100 for (i=0; i < igraph_vector_ptr_size(&paths); ++i) {
101 print_vector(VECTOR(paths)[i]);
102 }
103 IGRAPH_ASSERT(igraph_vector_ptr_size(&paths) == VECTOR(nrgeo)[to]);
104
105 igraph_vector_ptr_free_all(&paths);
106
107 printf("\nWeighted, uniform weights\n");
108 igraph_vector_resize(&weights, igraph_ecount(&graph));
109 igraph_vector_fill(&weights, 1.5); /* constant weights */
110
111 igraph_get_all_shortest_paths_dijkstra(&graph, &paths, &nrgeo, from, igraph_vss_1(to), &weights, IGRAPH_ALL);
112
113 for (i=0; i < igraph_vector_ptr_size(&paths); ++i) {
114 print_vector(VECTOR(paths)[i]);
115 }
116 IGRAPH_ASSERT(igraph_vector_ptr_size(&paths) == VECTOR(nrgeo)[to]);
117
118 igraph_vector_ptr_free_all(&paths);
119
120 printf("\nWeighted, multiple weighted shortest paths\n");
121 VECTOR(weights)[1] = 3.0; /* create path with one more hop, but equal weighted length */
122 VECTOR(weights)[4] = 2.0; /* break symmetry on pair of parallel edges */
123
124 igraph_get_all_shortest_paths_dijkstra(&graph, &paths, &nrgeo, from, igraph_vss_1(to), &weights, IGRAPH_ALL);
125
126 for (i=0; i < igraph_vector_ptr_size(&paths); ++i) {
127 print_vector(VECTOR(paths)[i]);
128 }
129 IGRAPH_ASSERT(igraph_vector_ptr_size(&paths) == VECTOR(nrgeo)[to]);
130
131 igraph_vector_ptr_destroy_all(&paths);
132
133 igraph_vector_destroy(&weights);
134 igraph_vector_destroy(&nrgeo);
135 igraph_destroy(&graph);
136
137 VERIFY_FINALLY_STACK();
138
139 return 0;
140 }
141