git.ozlabs.org Git - ccan/blob - ccan/aga/dijkstra.c

   1 /* Licensed under LGPLv2+ - see LICENSE file for details */
   2 #include "config.h"
   3
   4 #include <stdbool.h>
   5 #include <stdlib.h>
   6 #include <assert.h>
   7
   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>
  12
  13 #include <ccan/aga/aga.h>
  14 #include "private.h"
  15
  16 /*
  17  * Dijkstra's algorithm
  18  */
  19
  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;
  30
  31                 lpq_enqueue(&g->state.dijkstra, node);
  32         } else if (distance < node->u.dijkstra.distance) {
  33                 assert(!node->u.dijkstra.complete);
  34
  35                 node->u.dijkstra.distance = distance;
  36                 node->u.dijkstra.prev = prev;
  37                 node->u.dijkstra.prevedge = prevedge;
  38
  39                 lpq_reorder(&g->state.dijkstra, node);
  40         }
  41 }
  42
  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;
  48
  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);
  52
  53         rc = aga_start(g);
  54         if (rc < 0)
  55                 return rc;
  56
  57         lpq_init(&g->state.dijkstra, order.cb, order.ctx);
  58
  59         candidate_path(g, source, 0, NULL, NULL);
  60
  61         return 0;
  62 }
  63
  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;
  70
  71         if (!aga_check_state(g))
  72                 return NULL;
  73
  74         if (!n)
  75                 return NULL;
  76
  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         }
  89
  90         n->u.dijkstra.complete = true;
  91
  92         return n;
  93 }
  94
  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;
 101
 102         while (aga_node_needs_update(g, node) || !node->u.dijkstra.complete) {
 103                 if (!aga_dijkstra_step(g))
 104                         return false;
 105         };
 106
 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;
 113
 114         return true;
 115 }
 116
 117 void aga_dijkstra_complete(struct aga_graph *g)
 118 {
 119         if (!aga_check_state(g))
 120                 return;
 121
 122         while (aga_dijkstra_step(g))
 123                 ;
 124 }
 125