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>
11 #include <ccan/lpq/lpq.h>
13 #include <ccan/aga/aga.h>
17 * Dijkstra's algorithm
20 static void candidate_path(struct aga_graph *g, struct aga_node *node,
22 struct aga_node *prev, const void *prevedge)
24 if (aga_update_node(g, node)) {
25 /* New node, treat has having infinite distance */
26 node->u.dijkstra.distance = distance;
27 node->u.dijkstra.prev = prev;
28 node->u.dijkstra.prevedge = prevedge;
29 node->u.dijkstra.complete = false;
31 lpq_enqueue(&g->state.dijkstra, node);
32 } else if (distance < node->u.dijkstra.distance) {
33 assert(!node->u.dijkstra.complete);
35 node->u.dijkstra.distance = distance;
36 node->u.dijkstra.prev = prev;
37 node->u.dijkstra.prevedge = prevedge;
39 lpq_reorder(&g->state.dijkstra, node);
43 int aga_dijkstra_start(struct aga_graph *g, struct aga_node *source)
45 total_order_by_field(order, long_reverse,
46 struct aga_node, u.dijkstra.distance);
49 /* Make sure we're actually using the right ordering for
51 BUILD_ASSERT(check_types_match(long, aga_icost_t) == 0);
57 lpq_init(&g->state.dijkstra, order.cb, order.ctx);
59 candidate_path(g, source, 0, NULL, NULL);
64 struct aga_node *aga_dijkstra_step(struct aga_graph *g)
66 struct aga_node *n = lpq_dequeue(&g->state.dijkstra);
68 struct aga_edge_info ei;
71 if (!aga_check_state(g))
77 aga_for_each_edge_info(e, ei, err, g, n) {
79 aga_fail(g, AGA_ERR_NEGATIVE_COST);
82 candidate_path(g, ei.to,
83 n->u.dijkstra.distance + ei.icost, n, e);
90 n->u.dijkstra.complete = true;
95 bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *node,
96 aga_icost_t *total_cost,
97 struct aga_node **prev, const void **prevedge)
99 if (!aga_check_state(g))
102 while (aga_node_needs_update(g, node) || !node->u.dijkstra.complete) {
103 if (!aga_dijkstra_step(g))
108 *total_cost = node->u.dijkstra.distance;
110 *prev = node->u.dijkstra.prev;
112 *prevedge = node->u.dijkstra.prevedge;
117 void aga_dijkstra_all_paths(struct aga_graph *g)
119 if (!aga_check_state(g))
122 while (aga_dijkstra_step(g))