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 #include "test_utilities.inc"
21
main()22 int main() {
23 igraph_t g_empty, g_empty_dir, g_lm;
24 igraph_matrix_t result;
25 igraph_vs_t vids;
26 igraph_vector_t weights_empty, weights_lm, weights_lm_neg_loop;
27
28 igraph_matrix_init(&result, 0, 0);
29 igraph_vs_all(&vids);
30 igraph_vector_init(&weights_empty, 0);
31 igraph_vector_init_int(&weights_lm_neg_loop, 9, -4, -3, -2, -1, 0, 1, 2, 3, 4);
32 igraph_vector_init_int(&weights_lm, 9, -1, 0, 1, -2, 2, 3, 4, 5, 6);
33 igraph_small(&g_empty, 0, 0, -1);
34 igraph_small(&g_empty_dir, 0, 1, -1);
35 igraph_small(&g_lm, 6, 1, 0,1, 0,2, 1,1, 1,2, 1,3, 2,0, 2,3, 3,4, 3,4, -1);
36
37 igraph_set_error_handler(igraph_error_handler_printignore);
38
39 printf("No vertices, not directed:\n");
40 IGRAPH_ASSERT(igraph_shortest_paths_johnson(&g_empty, &result, vids, vids, &weights_empty) == IGRAPH_SUCCESS);
41 print_matrix(&result);
42
43 printf("No vertices, directed:\n");
44 IGRAPH_ASSERT(igraph_shortest_paths_johnson(&g_empty_dir, &result, vids, vids, &weights_empty) == IGRAPH_SUCCESS);
45 print_matrix(&result);
46
47 printf("Directed graph with loops and multi-edges with negative loop:\n");
48 IGRAPH_ASSERT(igraph_shortest_paths_johnson(&g_lm, &result, vids, vids, &weights_lm_neg_loop) == IGRAPH_ENEGLOOP);
49
50 printf("Directed graph with loops and multi-edges:\n");
51 IGRAPH_ASSERT(igraph_shortest_paths_johnson(&g_lm, &result, vids, vids, &weights_lm) == IGRAPH_SUCCESS);
52 print_matrix(&result);
53
54 printf("Directed graph with loops and multi-edges, select vertices 1 and 2:\n");
55 IGRAPH_ASSERT(igraph_shortest_paths_johnson(&g_lm, &result, igraph_vss_seq(1, 2), igraph_vss_seq(1, 2), &weights_lm) == IGRAPH_SUCCESS);
56 print_matrix(&result);
57
58 printf("Directed graph with loops and multi-edges, select 0 -> 2:\n");
59 IGRAPH_ASSERT(igraph_shortest_paths_johnson(&g_lm, &result, igraph_vss_1(0), igraph_vss_1(2), &weights_lm) == IGRAPH_SUCCESS);
60 print_matrix(&result);
61
62 printf("Directed graph with loops and multi-edges, select none:\n");
63 IGRAPH_ASSERT(igraph_shortest_paths_johnson(&g_lm, &result, igraph_vss_none(), igraph_vss_none(), &weights_lm) == IGRAPH_SUCCESS);
64 print_matrix(&result);
65
66 igraph_matrix_destroy(&result);
67 igraph_destroy(&g_empty);
68 igraph_destroy(&g_empty_dir);
69 igraph_destroy(&g_lm);
70 igraph_vector_destroy(&weights_empty);
71 igraph_vector_destroy(&weights_lm);
72 igraph_vector_destroy(&weights_lm_neg_loop);
73
74 VERIFY_FINALLY_STACK();
75 return 0;
76 }
77