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
21 #define STATE_INFINITE 0
22 #define STATE_FINITE 1
23 #define STATE_COMPLETE 2
26 static void candidate_path(struct aga_graph *g, struct aga_node *node,
28 struct aga_node *prev, const void *prevedge)
30 if (aga_update_node(g, node)) {
31 /* New node, treat has having infinite distance */
32 node->u.dijkstra.distance = distance;
33 node->u.dijkstra.prev = prev;
34 node->u.dijkstra.prevedge = prevedge;
35 node->u.dijkstra.complete = false;
37 lpq_enqueue(&g->state.dijkstra, node);
38 } else if (distance < node->u.dijkstra.distance) {
39 assert(!node->u.dijkstra.complete);
41 node->u.dijkstra.distance = distance;
42 node->u.dijkstra.prev = prev;
43 node->u.dijkstra.prevedge = prevedge;
45 lpq_reorder(&g->state.dijkstra, node);
49 int aga_dijkstra_start(struct aga_graph *g, struct aga_node *source)
51 total_order_by_field(order, long_reverse,
52 struct aga_node, u.dijkstra.distance);
55 /* Make sure we're actually using the right ordering for
57 BUILD_ASSERT(check_types_match(long, aga_icost_t) == 0);
63 lpq_init(&g->state.dijkstra, order.cb, order.ctx);
65 candidate_path(g, source, 0, NULL, NULL);
70 struct aga_node *aga_dijkstra_step(struct aga_graph *g)
72 struct aga_node *n = lpq_dequeue(&g->state.dijkstra);
74 struct aga_edge_info ei;
77 if (!aga_check_state(g))
83 aga_for_each_edge_info(e, ei, err, g, n) {
85 aga_fail(g, AGA_ERR_NEGATIVE_COST);
88 candidate_path(g, ei.to,
89 n->u.dijkstra.distance + ei.icost, n, e);
96 n->u.dijkstra.complete = true;
101 bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *node,
102 aga_icost_t *total_cost,
103 struct aga_node **prev, const void **prevedge)
105 if (!aga_check_state(g))
108 while (aga_node_needs_update(g, node) || !node->u.dijkstra.complete) {
109 if (!aga_dijkstra_step(g))
114 *total_cost = node->u.dijkstra.distance;
116 *prev = node->u.dijkstra.prev;
118 *prevedge = node->u.dijkstra.prevedge;
123 void aga_dijkstra_all_paths(struct aga_graph *g)
125 if (!aga_check_state(g))
128 while (aga_dijkstra_step(g))