1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #include "config.h"
4 #include <stdbool.h>
5 #include <stdlib.h>
6 #include <assert.h>
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>
14 #include "private.h"
16 /*
17  * Dijkstra's algorithm
18  */
20 static void candidate_path(struct aga_graph *g, struct aga_node *node,
21                            aga_icost_t distance,
22                            struct aga_node *prev, const void *prevedge)
23 {
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);
40         }
41 }
43 int aga_dijkstra_start(struct aga_graph *g, struct aga_node *source)
44 {
45         total_order_by_field(order, long_reverse,
46                              struct aga_node, u.dijkstra.distance);
47         int rc;
49         /* Make sure we're actually using the right ordering for
50          * aga_icost_t */
51         BUILD_ASSERT(check_types_match(long, aga_icost_t) == 0);
53         rc = aga_start(g);
54         if (rc < 0)
55                 return rc;
57         lpq_init(&g->state.dijkstra, order.cb, order.ctx);
59         candidate_path(g, source, 0, NULL, NULL);
61         return 0;
62 }
64 struct aga_node *aga_dijkstra_step(struct aga_graph *g)
65 {
66         struct aga_node *n = lpq_dequeue(&g->state.dijkstra);
67         const void *e;
68         struct aga_edge_info ei;
69         int err;
71         if (!aga_check_state(g))
72                 return NULL;
74         if (!n)
75                 return NULL;
77         aga_for_each_edge_info(e, ei, err, g, n) {
78                 if (ei.icost < 0) {
79                         aga_fail(g, AGA_ERR_NEGATIVE_COST);
80                         return NULL;
81                 }
82                 candidate_path(g, ei.to,
83                                n->u.dijkstra.distance + ei.icost, n, e);
84         }
85         if (err) {
86                 aga_fail(g, err);
87                 return NULL;
88         }
90         n->u.dijkstra.complete = true;
92         return n;
93 }
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)
98 {
99         if (!aga_check_state(g))
100                 return false;
102         while (aga_node_needs_update(g, node) || !node->u.dijkstra.complete) {
103                 if (!aga_dijkstra_step(g))
104                         return false;
105         };
107         if (total_cost)
108                 *total_cost = node->u.dijkstra.distance;
109         if (prev)
110                 *prev = node->u.dijkstra.prev;
111         if (prevedge)
112                 *prevedge = node->u.dijkstra.prevedge;
114         return true;
115 }
117 void aga_dijkstra_all_paths(struct aga_graph *g)
118 {
119         if (!aga_check_state(g))
120                 return;
122         while (aga_dijkstra_step(g))
123                 ;
124 }