1 /* -*- mode: C -*- */
2 /* vim:set ts=4 sw=4 sts=4 et: */
3 /*
4 IGraph library.
5 Copyright (C) 2005-2021 The igraph development team
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, see <https://www.gnu.org/licenses/>.
19 */
20
21 #include "igraph_paths.h"
22
23 #include "igraph_adjlist.h"
24 #include "igraph_dqueue.h"
25 #include "igraph_interface.h"
26 #include "igraph_memory.h"
27 #include "igraph_stack.h"
28
29 #include "core/indheap.h"
30 #include "core/interruption.h"
31
32 #include <string.h>
33
34 /**
35 * \function igraph_shortest_paths_bellman_ford
36 * \brief Weighted shortest path lengths between vertices, allowing negative weights.
37 *
38 * This function implements the Bellman-Ford algorithm to find the weighted
39 * shortest paths to all vertices from a single source, allowing negative weights.
40 * It is run independently for the given sources. If there are no negative
41 * weights, you are better off with \ref igraph_shortest_paths_dijkstra() .
42 *
43 * \param graph The input graph, can be directed.
44 * \param res The result, a matrix. A pointer to an initialized matrix
45 * should be passed here, the matrix will be resized if needed.
46 * Each row contains the distances from a single source, to all
47 * vertices in the graph, in the order of vertex ids. For unreachable
48 * vertices the matrix contains \c IGRAPH_INFINITY.
49 * \param from The source vertices.
50 * \param to The target vertices. It is not allowed to include a
51 * vertex twice or more.
52 * \param weights The edge weights. There mustn't be any closed loop in
53 * the graph that has a negative total weight (since this would allow
54 * us to decrease the weight of any path containing at least a single
55 * vertex of this loop infinitely). Additionally, no edge weight may
56 * be NaN. If either case does not hold, an error is returned. If this
57 * is a null pointer, then the unweighted version,
58 * \ref igraph_shortest_paths() is called.
59 * \param mode For directed graphs; whether to follow paths along edge
60 * directions (\c IGRAPH_OUT), or the opposite (\c IGRAPH_IN), or
61 * ignore edge directions completely (\c IGRAPH_ALL). It is ignored
62 * for undirected graphs.
63 * \return Error code.
64 *
65 * Time complexity: O(s*|E|*|V|), where |V| is the number of
66 * vertices, |E| the number of edges and s the number of sources.
67 *
68 * \sa \ref igraph_shortest_paths() for a faster unweighted version
69 * or \ref igraph_shortest_paths_dijkstra() if you do not have negative
70 * edge weights.
71 *
72 * \example examples/simple/bellman_ford.c
73 */
igraph_shortest_paths_bellman_ford(const igraph_t * graph,igraph_matrix_t * res,const igraph_vs_t from,const igraph_vs_t to,const igraph_vector_t * weights,igraph_neimode_t mode)74 int igraph_shortest_paths_bellman_ford(const igraph_t *graph,
75 igraph_matrix_t *res,
76 const igraph_vs_t from,
77 const igraph_vs_t to,
78 const igraph_vector_t *weights,
79 igraph_neimode_t mode) {
80 long int no_of_nodes = igraph_vcount(graph);
81 long int no_of_edges = igraph_ecount(graph);
82 igraph_lazy_inclist_t inclist;
83 long int i, j, k;
84 long int no_of_from, no_of_to;
85 igraph_dqueue_t Q;
86 igraph_vector_t clean_vertices;
87 igraph_vector_t num_queued;
88 igraph_vit_t fromvit, tovit;
89 igraph_real_t my_infinity = IGRAPH_INFINITY;
90 igraph_bool_t all_to;
91 igraph_vector_t dist;
92
93 /*
94 - speedup: a vertex is marked clean if its distance from the source
95 did not change during the last phase. Neighbors of a clean vertex
96 are not relaxed again, since it would mean no change in the
97 shortest path values. Dirty vertices are queued. Negative loops can
98 be detected by checking whether a vertex has been queued at least
99 n times.
100 */
101 if (!weights) {
102 return igraph_shortest_paths(graph, res, from, to, mode);
103 }
104
105 if (igraph_vector_size(weights) != no_of_edges) {
106 IGRAPH_ERROR("Weight vector length does not match", IGRAPH_EINVAL);
107 }
108 if (no_of_edges > 0 && igraph_vector_is_any_nan(weights)) {
109 IGRAPH_ERROR("Weight vector must not contain NaN values", IGRAPH_EINVAL);
110 }
111
112 IGRAPH_CHECK(igraph_vit_create(graph, from, &fromvit));
113 IGRAPH_FINALLY(igraph_vit_destroy, &fromvit);
114 no_of_from = IGRAPH_VIT_SIZE(fromvit);
115
116 IGRAPH_DQUEUE_INIT_FINALLY(&Q, no_of_nodes);
117 IGRAPH_VECTOR_INIT_FINALLY(&clean_vertices, no_of_nodes);
118 IGRAPH_VECTOR_INIT_FINALLY(&num_queued, no_of_nodes);
119 IGRAPH_CHECK(igraph_lazy_inclist_init(graph, &inclist, mode, IGRAPH_LOOPS));
120 IGRAPH_FINALLY(igraph_lazy_inclist_destroy, &inclist);
121
122 all_to = igraph_vs_is_all(&to);
123 if (all_to) {
124 no_of_to = no_of_nodes;
125 } else {
126 IGRAPH_CHECK(igraph_vit_create(graph, to, &tovit));
127 IGRAPH_FINALLY(igraph_vit_destroy, &tovit);
128 no_of_to = IGRAPH_VIT_SIZE(tovit);
129 }
130
131 IGRAPH_VECTOR_INIT_FINALLY(&dist, no_of_nodes);
132 IGRAPH_CHECK(igraph_matrix_resize(res, no_of_from, no_of_to));
133
134 for (IGRAPH_VIT_RESET(fromvit), i = 0;
135 !IGRAPH_VIT_END(fromvit);
136 IGRAPH_VIT_NEXT(fromvit), i++) {
137 long int source = IGRAPH_VIT_GET(fromvit);
138
139 igraph_vector_fill(&dist, my_infinity);
140 VECTOR(dist)[source] = 0;
141 igraph_vector_null(&clean_vertices);
142 igraph_vector_null(&num_queued);
143
144 /* Fill the queue with vertices to be checked */
145 for (j = 0; j < no_of_nodes; j++) {
146 IGRAPH_CHECK(igraph_dqueue_push(&Q, j));
147 }
148
149 while (!igraph_dqueue_empty(&Q)) {
150 igraph_vector_int_t *neis;
151 long int nlen;
152
153 j = (long int) igraph_dqueue_pop(&Q);
154 VECTOR(clean_vertices)[j] = 1;
155 VECTOR(num_queued)[j] += 1;
156 if (VECTOR(num_queued)[j] > no_of_nodes) {
157 IGRAPH_ERROR("cannot run Bellman-Ford algorithm", IGRAPH_ENEGLOOP);
158 }
159
160 /* If we cannot get to j in finite time yet, there is no need to relax
161 * its edges */
162 if (!IGRAPH_FINITE(VECTOR(dist)[j])) {
163 continue;
164 }
165
166 neis = igraph_lazy_inclist_get(&inclist, (igraph_integer_t) j);
167 nlen = igraph_vector_int_size(neis);
168
169 for (k = 0; k < nlen; k++) {
170 long int nei = (long int) VECTOR(*neis)[k];
171 long int target = IGRAPH_OTHER(graph, nei, j);
172 if (VECTOR(dist)[target] > VECTOR(dist)[j] + VECTOR(*weights)[nei]) {
173 /* relax the edge */
174 VECTOR(dist)[target] = VECTOR(dist)[j] + VECTOR(*weights)[nei];
175 if (VECTOR(clean_vertices)[target]) {
176 VECTOR(clean_vertices)[target] = 0;
177 IGRAPH_CHECK(igraph_dqueue_push(&Q, target));
178 }
179 }
180 }
181 }
182
183 /* Copy it to the result */
184 if (all_to) {
185 igraph_matrix_set_row(res, &dist, i);
186 } else {
187 for (IGRAPH_VIT_RESET(tovit), j = 0; !IGRAPH_VIT_END(tovit);
188 IGRAPH_VIT_NEXT(tovit), j++) {
189 long int v = IGRAPH_VIT_GET(tovit);
190 MATRIX(*res, i, j) = VECTOR(dist)[v];
191 }
192 }
193 }
194
195 igraph_vector_destroy(&dist);
196 IGRAPH_FINALLY_CLEAN(1);
197
198 if (!all_to) {
199 igraph_vit_destroy(&tovit);
200 IGRAPH_FINALLY_CLEAN(1);
201 }
202
203 igraph_vit_destroy(&fromvit);
204 igraph_dqueue_destroy(&Q);
205 igraph_vector_destroy(&clean_vertices);
206 igraph_vector_destroy(&num_queued);
207 igraph_lazy_inclist_destroy(&inclist);
208 IGRAPH_FINALLY_CLEAN(5);
209
210 return 0;
211 }
212
213
214 /**
215 * \ingroup structural
216 * \function igraph_get_shortest_paths_bellman_ford
217 * \brief Weighted shortest paths from a vertex, allowing negative weights.
218 *
219 * This function calculates weighted shortest paths from or to a single vertex,
220 * and allows negative weights. When there is more than one shortest path between
221 * two vertices, only one of them is returned.
222 *
223 * If there are no negative weights, you are better off with
224 * \ref igraph_get_shortest_paths_dijkstra() .
225 *
226 * \param graph The input graph, can be directed.
227 * \param vertices The result, the ids of the vertices along the paths.
228 * This is a pointer vector, each element points to a vector
229 * object. These should be initialized before passing them to
230 * the function, which will properly clear and/or resize them
231 * and fill the ids of the vertices along the geodesics from/to
232 * the vertices. Supply a null pointer here if you don't need
233 * these vectors. Normally, either this argument, or the \c
234 * edges should be non-null, but no error or warning is given
235 * if they are both null pointers.
236 * \param edges The result, the ids of the edges along the paths.
237 * This is a pointer vector, each element points to a vector
238 * object. These should be initialized before passing them to
239 * the function, which will properly clear and/or resize them
240 * and fill the ids of the vertices along the geodesics from/to
241 * the vertices. Supply a null pointer here if you don't need
242 * these vectors. Normally, either this argument, or the \c
243 * vertices should be non-null, but no error or warning is given
244 * if they are both null pointers.
245 * \param from The id of the vertex from/to which the geodesics are
246 * calculated.
247 * \param to Vertex sequence with the ids of the vertices to/from which the
248 * shortest paths will be calculated. A vertex might be given multiple
249 * times.
250 * \param weights The edge weights. There mustn't be any closed loop in
251 * the graph that has a negative total weight (since this would allow
252 * us to decrease the weight of any path containing at least a single
253 * vertex of this loop infinitely). If this is a null pointer, then the
254 * unweighted version, \ref igraph_shortest_paths() is called.
255 * \param mode For directed graphs; whether to follow paths along edge
256 * directions (\c IGRAPH_OUT), or the opposite (\c IGRAPH_IN), or
257 * ignore edge directions completely (\c IGRAPH_ALL). It is ignored
258 * for undirected graphs.
259 * \param predecessors A pointer to an initialized igraph vector or null.
260 * If not null, a vector containing the predecessor of each vertex in
261 * the single source shortest path tree is returned here. The
262 * predecessor of vertex i in the tree is the vertex from which vertex i
263 * was reached. The predecessor of the start vertex (in the \c from
264 * argument) is itself by definition. If the predecessor is -1, it means
265 * that the given vertex was not reached from the source during the
266 * search. Note that the search terminates if all the vertices in
267 * \c to are reached.
268 * \param inbound_edges A pointer to an initialized igraph vector or null.
269 * If not null, a vector containing the inbound edge of each vertex in
270 * the single source shortest path tree is returned here. The
271 * inbound edge of vertex i in the tree is the edge via which vertex i
272 * was reached. The start vertex and vertices that were not reached
273 * during the search will have -1 in the corresponding entry of the
274 * vector. Note that the search terminates if all the vertices in
275 * \c to are reached.
276 * \return Error code:
277 * \clist
278 * \cli IGRAPH_ENOMEM
279 * Not enough memory for temporary data.
280 * \cli IGRAPH_EINVAL
281 * The weight vector doesn't math the number of edges.
282 * \cli IGRAPH_EINVVID
283 * \p from is invalid vertex id, or the length of \p to is
284 * not the same as the length of \p vertices or \p edges.
285 * \cli IGRAPH_ENEGLOOP
286 * Bellman-ford algorithm encounted a negative loop.
287 * \endclist
288 *
289 * Time complexity: O(|E|*|V|), where |V| is the number of
290 * vertices, |E| the number of edges.
291 *
292 * \sa \ref igraph_shortest_paths() for a faster unweighted version
293 * or \ref igraph_shortest_paths_dijkstra() if you do not have negative
294 * edge weights.
295 */
296
igraph_get_shortest_paths_bellman_ford(const igraph_t * graph,igraph_vector_ptr_t * vertices,igraph_vector_ptr_t * edges,igraph_integer_t from,igraph_vs_t to,const igraph_vector_t * weights,igraph_neimode_t mode,igraph_vector_long_t * predecessors,igraph_vector_long_t * inbound_edges)297 int igraph_get_shortest_paths_bellman_ford(const igraph_t *graph,
298 igraph_vector_ptr_t *vertices,
299 igraph_vector_ptr_t *edges,
300 igraph_integer_t from,
301 igraph_vs_t to,
302 const igraph_vector_t *weights,
303 igraph_neimode_t mode,
304 igraph_vector_long_t *predecessors,
305 igraph_vector_long_t *inbound_edges) {
306 long int no_of_nodes = igraph_vcount(graph);
307 long int no_of_edges = igraph_ecount(graph);
308 long int *parents;
309 igraph_lazy_inclist_t inclist;
310 long int i, j, k;
311 igraph_dqueue_t Q;
312 igraph_vector_t clean_vertices;
313 igraph_vector_t num_queued;
314 igraph_vit_t tovit;
315 igraph_real_t my_infinity = IGRAPH_INFINITY;
316 igraph_vector_t dist;
317
318 if (!weights) {
319 return igraph_get_shortest_paths(graph, vertices, edges, from, to, mode,
320 predecessors, inbound_edges);
321 }
322
323 if (igraph_vector_size(weights) != no_of_edges) {
324 IGRAPH_ERROR("Weight vector length must match number of edges.", IGRAPH_EINVAL);
325 }
326
327 IGRAPH_DQUEUE_INIT_FINALLY(&Q, no_of_nodes);
328 IGRAPH_VECTOR_INIT_FINALLY(&clean_vertices, no_of_nodes);
329 IGRAPH_VECTOR_INIT_FINALLY(&num_queued, no_of_nodes);
330 IGRAPH_CHECK(igraph_lazy_inclist_init(graph, &inclist, mode, IGRAPH_LOOPS));
331 IGRAPH_FINALLY(igraph_lazy_inclist_destroy, &inclist);
332
333 IGRAPH_CHECK(igraph_vit_create(graph, to, &tovit));
334 IGRAPH_FINALLY(igraph_vit_destroy, &tovit);
335
336 if (vertices && IGRAPH_VIT_SIZE(tovit) != igraph_vector_ptr_size(vertices)) {
337 IGRAPH_ERROR("Size of `vertices' and `to' should match.", IGRAPH_EINVAL);
338 }
339 if (edges && IGRAPH_VIT_SIZE(tovit) != igraph_vector_ptr_size(edges)) {
340 IGRAPH_ERROR("Size of `edges' and `to' should match.", IGRAPH_EINVAL);
341 }
342
343 parents = IGRAPH_CALLOC(no_of_nodes, long int);
344 if (parents == 0) {
345 IGRAPH_ERROR("Insufficient memory for shortest paths with Bellman-Ford.", IGRAPH_ENOMEM);
346 }
347 IGRAPH_FINALLY(igraph_free, parents);
348 IGRAPH_VECTOR_INIT_FINALLY(&dist, no_of_nodes);
349
350 igraph_vector_fill(&dist, my_infinity);
351 VECTOR(dist)[from] = 0;
352 igraph_vector_null(&clean_vertices);
353 igraph_vector_null(&num_queued);
354
355 /* Fill the queue with vertices to be checked */
356 for (j = 0; j < no_of_nodes; j++) {
357 IGRAPH_CHECK(igraph_dqueue_push(&Q, j));
358 }
359
360 while (!igraph_dqueue_empty(&Q)) {
361 igraph_vector_int_t *neis;
362 long int nlen;
363
364 j = (long int) igraph_dqueue_pop(&Q);
365 VECTOR(clean_vertices)[j] = 1;
366 VECTOR(num_queued)[j] += 1;
367 if (VECTOR(num_queued)[j] > no_of_nodes) {
368 IGRAPH_ERROR("cannot run Bellman-Ford algorithm", IGRAPH_ENEGLOOP);
369 }
370
371 /* If we cannot get to j in finite time yet, there is no need to relax
372 * its edges */
373 if (!IGRAPH_FINITE(VECTOR(dist)[j])) {
374 continue;
375 }
376
377 neis = igraph_lazy_inclist_get(&inclist, (igraph_integer_t) j);
378 nlen = igraph_vector_int_size(neis);
379
380 for (k = 0; k < nlen; k++) {
381 long int nei = (long int) VECTOR(*neis)[k];
382 long int target = IGRAPH_OTHER(graph, nei, j);
383 if (VECTOR(dist)[target] > VECTOR(dist)[j] + VECTOR(*weights)[nei]) {
384 /* relax the edge */
385 VECTOR(dist)[target] = VECTOR(dist)[j] + VECTOR(*weights)[nei];
386 parents[target] = nei + 1;
387 if (VECTOR(clean_vertices)[target]) {
388 VECTOR(clean_vertices)[target] = 0;
389 IGRAPH_CHECK(igraph_dqueue_push(&Q, target));
390 }
391 }
392 }
393 }
394
395 /* Create `predecessors' if needed */
396 if (predecessors) {
397 IGRAPH_CHECK(igraph_vector_long_resize(predecessors, no_of_nodes));
398
399 for (i = 0; i < no_of_nodes; i++) {
400 if (i == from) {
401 /* i is the start vertex */
402 VECTOR(*predecessors)[i] = i;
403 } else if (parents[i] <= 0) {
404 /* i was not reached */
405 VECTOR(*predecessors)[i] = -1;
406 } else {
407 /* i was reached via the edge with ID = parents[i] - 1 */
408 VECTOR(*predecessors)[i] = IGRAPH_OTHER(graph, parents[i] - 1, i);
409 }
410 }
411 }
412
413 /* Create `inbound_edges' if needed */
414 if (inbound_edges) {
415 IGRAPH_CHECK(igraph_vector_long_resize(inbound_edges, no_of_nodes));
416
417 for (i = 0; i < no_of_nodes; i++) {
418 if (parents[i] <= 0) {
419 /* i was not reached */
420 VECTOR(*inbound_edges)[i] = -1;
421 } else {
422 /* i was reached via the edge with ID = parents[i] - 1 */
423 VECTOR(*inbound_edges)[i] = parents[i] - 1;
424 }
425 }
426 }
427
428 /* Reconstruct the shortest paths based on vertex and/or edge IDs */
429 if (vertices || edges) {
430 for (IGRAPH_VIT_RESET(tovit), i = 0; !IGRAPH_VIT_END(tovit); IGRAPH_VIT_NEXT(tovit), i++) {
431 long int node = IGRAPH_VIT_GET(tovit);
432 long int size, act, edge;
433 igraph_vector_t *vvec = 0, *evec = 0;
434 if (vertices) {
435 vvec = VECTOR(*vertices)[i];
436 igraph_vector_clear(vvec);
437 }
438 if (edges) {
439 evec = VECTOR(*edges)[i];
440 igraph_vector_clear(evec);
441 }
442
443 IGRAPH_ALLOW_INTERRUPTION();
444
445 size = 0;
446 act = node;
447 while (parents[act]) {
448 size++;
449 edge = parents[act] - 1;
450 act = IGRAPH_OTHER(graph, edge, act);
451 }
452 if (vvec && (size > 0 || node == from)) {
453 IGRAPH_CHECK(igraph_vector_resize(vvec, size + 1));
454 VECTOR(*vvec)[size] = node;
455 }
456 if (evec) {
457 IGRAPH_CHECK(igraph_vector_resize(evec, size));
458 }
459 act = node;
460 while (parents[act]) {
461 edge = parents[act] - 1;
462 act = IGRAPH_OTHER(graph, edge, act);
463 size--;
464 if (vvec) {
465 VECTOR(*vvec)[size] = act;
466 }
467 if (evec) {
468 VECTOR(*evec)[size] = edge;
469 }
470 }
471 }
472 }
473
474 igraph_vector_destroy(&dist);
475 IGRAPH_FINALLY_CLEAN(1);
476
477 igraph_vit_destroy(&tovit);
478 IGRAPH_FINALLY_CLEAN(1);
479
480 IGRAPH_FREE(parents);
481 igraph_dqueue_destroy(&Q);
482 igraph_vector_destroy(&clean_vertices);
483 igraph_vector_destroy(&num_queued);
484 igraph_lazy_inclist_destroy(&inclist);
485 IGRAPH_FINALLY_CLEAN(5);
486
487 return IGRAPH_SUCCESS;
488 }
489
490 /**
491 * \function igraph_get_shortest_path_bellman_ford
492 * \brief Weighted shortest path from one vertex to another one.
493 *
494 * Calculates a single (positively) weighted shortest path from
495 * a single vertex to another one, using Bellman-Ford algorithm.
496 *
497 * </para><para>
498 * This function is a special case (and a wrapper) to
499 * \ref igraph_get_shortest_paths_bellman_ford().
500 *
501 * \param graph The input graph, it can be directed or undirected.
502 * \param vertices Pointer to an initialized vector or a null
503 * pointer. If not a null pointer, then the vertex ids along
504 * the path are stored here, including the source and target
505 * vertices.
506 * \param edges Pointer to an uninitialized vector or a null
507 * pointer. If not a null pointer, then the edge ids along the
508 * path are stored here.
509 * \param from The id of the source vertex.
510 * \param to The id of the target vertex.
511 * \param weights The edge weights. There mustn't be any closed loop in
512 * the graph that has a negative total weight (since this would allow
513 * us to decrease the weight of any path containing at least a single
514 * vertex of this loop infinitely). If this is a null pointer, then the
515 * unweighted version is called.
516 * \param mode A constant specifying how edge directions are
517 * considered in directed graphs. \c IGRAPH_OUT follows edge
518 * directions, \c IGRAPH_IN follows the opposite directions,
519 * and \c IGRAPH_ALL ignores edge directions. This argument is
520 * ignored for undirected graphs.
521 * \return Error code.
522 *
523 * Time complexity: O(|E|log|E|+|V|), |V| is the number of vertices,
524 * |E| is the number of edges in the graph.
525 *
526 * \sa \ref igraph_get_shortest_paths_bellman_ford() for the version with
527 * more target vertices.
528 */
529
igraph_get_shortest_path_bellman_ford(const igraph_t * graph,igraph_vector_t * vertices,igraph_vector_t * edges,igraph_integer_t from,igraph_integer_t to,const igraph_vector_t * weights,igraph_neimode_t mode)530 int igraph_get_shortest_path_bellman_ford(const igraph_t *graph,
531 igraph_vector_t *vertices,
532 igraph_vector_t *edges,
533 igraph_integer_t from,
534 igraph_integer_t to,
535 const igraph_vector_t *weights,
536 igraph_neimode_t mode) {
537
538 igraph_vector_ptr_t vertices2, *vp = &vertices2;
539 igraph_vector_ptr_t edges2, *ep = &edges2;
540
541 if (vertices) {
542 IGRAPH_CHECK(igraph_vector_ptr_init(&vertices2, 1));
543 IGRAPH_FINALLY(igraph_vector_ptr_destroy, &vertices2);
544 VECTOR(vertices2)[0] = vertices;
545 } else {
546 vp = NULL;
547 }
548 if (edges) {
549 IGRAPH_CHECK(igraph_vector_ptr_init(&edges2, 1));
550 IGRAPH_FINALLY(igraph_vector_ptr_destroy, &edges2);
551 VECTOR(edges2)[0] = edges;
552 } else {
553 ep = NULL;
554 }
555
556 IGRAPH_CHECK(igraph_get_shortest_paths_bellman_ford(graph, vp, ep,
557 from, igraph_vss_1(to),
558 weights, mode, NULL, NULL));
559
560 if (edges) {
561 igraph_vector_ptr_destroy(&edges2);
562 IGRAPH_FINALLY_CLEAN(1);
563 }
564 if (vertices) {
565 igraph_vector_ptr_destroy(&vertices2);
566 IGRAPH_FINALLY_CLEAN(1);
567 }
568
569 return IGRAPH_SUCCESS;
570 }
571