git.ozlabs.org Git - ccan/blob - ccan/aga/bellman_ford.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
  12 #include <ccan/aga/aga.h>
  13 #include "private.h"
  14
  15 /*
  16  * The Bellman-Ford algorithm
  17  */
  18
  19 static bool candidate_path(struct aga_graph *g, struct aga_node *node,
  20                            aga_icost_t distance,
  21                            struct aga_node *prev, const void *prevedge)
  22 {
  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;
  28
  29                 node->u.bellman_ford.list = g->state.bellman_ford.nodelist;
  30                 g->state.bellman_ford.nodelist = node;
  31                 g->state.bellman_ford.nnodes++;
  32
  33                 return true;
  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;
  38         }
  39         return false;
  40 }
  41
  42 int aga_bellman_ford_start(struct aga_graph *g, struct aga_node *source)
  43 {
  44         int rc;
  45
  46         /* Make sure we're actually using the right ordering for
  47          * aga_icost_t */
  48         BUILD_ASSERT(check_types_match(long, aga_icost_t) == 0);
  49
  50         rc = aga_start(g);
  51         if (rc < 0)
  52                 return rc;
  53
  54         g->state.bellman_ford.nodelist = NULL;
  55         g->state.bellman_ford.nnodes = 0;
  56         g->state.bellman_ford.npasses = 0;
  57
  58         candidate_path(g, source, 0, NULL, NULL);
  59
  60         return 0;
  61 }
  62
  63 static bool aga_bellman_ford_step(struct aga_graph *g)
  64 {
  65         struct aga_node *n;
  66         const void *e;
  67         struct aga_edge_info ei;
  68         int err;
  69         bool newnode = false;
  70
  71         if (!aga_check_state(g))
  72                 return false;
  73
  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
  78                                 + ei.icost;
  79                         newnode = newnode || candidate_path(g, ei.to, dist, n, e);
  80                 }
  81                 if (err) {
  82                         aga_fail(g, err);
  83                         return false;
  84                 }
  85         }
  86         g->state.bellman_ford.npasses++;
  87         return newnode || (g->state.bellman_ford.npasses
  88                            < g->state.bellman_ford.nnodes);
  89 }
  90
  91 void aga_bellman_ford_complete(struct aga_graph *g)
  92 {
  93         struct aga_node *n;
  94         const void *e;
  95         struct aga_edge_info ei;
  96         int err;
  97
  98         if (!aga_check_state(g))
  99                 return;
 100
 101         while (aga_bellman_ford_step(g))
 102                 ;
 103
 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);
 111                                 return;
 112                         }
 113                 }
 114                 if (err) {
 115                         aga_fail(g, err);
 116                         return;
 117                 }
 118         }
 119 }
 120
 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)
 124 {
 125         aga_bellman_ford_complete(g);
 126
 127         if (!aga_check_state(g))
 128                 return false;
 129
 130         if (aga_node_needs_update(g, node))
 131                 return false;
 132
 133         if (total_cost)
 134                 *total_cost = node->u.bellman_ford.distance;
 135         if (prev)
 136                 *prev = node->u.bellman_ford.prev;
 137         if (prevedge)
 138                 *prevedge = node->u.bellman_ford.prevedge;
 139
 140         return true;
 141 }