1 /* Licensed under LGPLv2+ - see LICENSE file for details */
8 #include <ccan/build_assert/build_assert.h>
9 #include <ccan/check_type/check_type.h>
10 #include <ccan/order/order.h>
12 #include <ccan/aga/aga.h>
16 * The Bellman-Ford algorithm
19 static bool candidate_path(struct aga_graph *g, struct aga_node *node,
21 struct aga_node *prev, const void *prevedge)
23 if (aga_update_node(g, node)) {
24 /* New node, treat as having infinite distance */
25 node->u.bellman_ford.distance = distance;
26 node->u.bellman_ford.prev = prev;
27 node->u.bellman_ford.prevedge = prevedge;
29 node->u.bellman_ford.list = g->state.bellman_ford.nodelist;
30 g->state.bellman_ford.nodelist = node;
31 g->state.bellman_ford.nnodes++;
34 } else if (distance < node->u.bellman_ford.distance) {
35 node->u.bellman_ford.distance = distance;
36 node->u.bellman_ford.prev = prev;
37 node->u.bellman_ford.prevedge = prevedge;
42 int aga_bellman_ford_start(struct aga_graph *g, struct aga_node *source)
46 /* Make sure we're actually using the right ordering for
48 BUILD_ASSERT(check_types_match(long, aga_icost_t) == 0);
54 g->state.bellman_ford.nodelist = NULL;
55 g->state.bellman_ford.nnodes = 0;
56 g->state.bellman_ford.npasses = 0;
58 candidate_path(g, source, 0, NULL, NULL);
63 static bool aga_bellman_ford_step(struct aga_graph *g)
67 struct aga_edge_info ei;
71 if (!aga_check_state(g))
74 for (n = g->state.bellman_ford.nodelist;
75 n; n = n->u.bellman_ford.list) {
76 aga_for_each_edge_info(e, ei, err, g, n) {
77 aga_icost_t dist = n->u.bellman_ford.distance
79 newnode = newnode || candidate_path(g, ei.to, dist, n, e);
86 g->state.bellman_ford.npasses++;
87 return newnode || (g->state.bellman_ford.npasses
88 < g->state.bellman_ford.nnodes);
91 void aga_bellman_ford_complete(struct aga_graph *g)
95 struct aga_edge_info ei;
98 if (!aga_check_state(g))
101 while (aga_bellman_ford_step(g))
104 /* Check for negative cycles */
105 for (n = g->state.bellman_ford.nodelist;
106 n; n = n->u.bellman_ford.list) {
107 aga_for_each_edge_info(e, ei, err, g, n) {
108 if ((n->u.bellman_ford.distance + ei.icost)
109 < ei.to->u.bellman_ford.distance) {
110 aga_fail(g, AGA_ERR_NEGATIVE_COST);
121 bool aga_bellman_ford_path(struct aga_graph *g, struct aga_node *node,
122 aga_icost_t *total_cost,
123 struct aga_node **prev, const void **prevedge)
125 aga_bellman_ford_complete(g);
127 if (!aga_check_state(g))
130 if (aga_node_needs_update(g, node))
134 *total_cost = node->u.bellman_ford.distance;
136 *prev = node->u.bellman_ford.prev;
138 *prevedge = node->u.bellman_ford.prevedge;