| 72 | } |
| 73 | |
| 74 | bool dijkstra_path(const tal_t *ctx, const struct graph *graph, |
| 75 | const struct node source, const struct node destination, |
| 76 | bool prune, const s64 *capacity, const s64 cap_threshold, |
| 77 | const s64 *cost, const s64 *potential, struct arc *prev, |
| 78 | s64 *distance) |
| 79 | { |
| 80 | bool target_found = false; |
| 81 | assert(graph); |
| 82 | const size_t max_num_arcs = graph_max_num_arcs(graph); |
| 83 | const size_t max_num_nodes = graph_max_num_nodes(graph); |
| 84 | const tal_t *this_ctx = tal(ctx, tal_t); |
| 85 | |
| 86 | /* check preconditions */ |
| 87 | assert(source.idx<max_num_nodes); |
| 88 | assert(cost); |
| 89 | assert(capacity); |
| 90 | assert(prev); |
| 91 | assert(distance); |
| 92 | |
| 93 | /* if prune is true then the destination cannot be invalid */ |
| 94 | assert(destination.idx < max_num_nodes || !prune); |
| 95 | |
| 96 | assert(tal_count(cost) == max_num_arcs); |
| 97 | assert(tal_count(capacity) == max_num_arcs); |
| 98 | assert(tal_count(prev) == max_num_nodes); |
| 99 | assert(tal_count(distance) == max_num_nodes); |
| 100 | |
| 101 | /* FIXME: maybe this is unnecessary */ |
| 102 | bitmap *visited = tal_arrz(this_ctx, bitmap, |
| 103 | BITMAP_NWORDS(max_num_nodes)); |
| 104 | |
| 105 | for (size_t i = 0; i < max_num_nodes; ++i) |
| 106 | prev[i].idx = INVALID_INDEX; |
| 107 | |
| 108 | struct priorityqueue *q; |
| 109 | q = priorityqueue_new(this_ctx, max_num_nodes); |
| 110 | const s64 *const dijkstra_distance = priorityqueue_value(q); |
| 111 | |
| 112 | priorityqueue_init(q); |
| 113 | priorityqueue_update(q, source.idx, 0); |
| 114 | |
| 115 | while (!priorityqueue_empty(q)) { |
| 116 | const u32 cur = priorityqueue_top(q); |
| 117 | priorityqueue_pop(q); |
| 118 | |
| 119 | /* FIXME: maybe this is unnecessary */ |
| 120 | if (bitmap_test_bit(visited, cur)) |
| 121 | continue; |
| 122 | bitmap_set_bit(visited, cur); |
| 123 | |
| 124 | if (cur == destination.idx) { |
| 125 | target_found = true; |
| 126 | if (prune) |
| 127 | break; |
| 128 | } |
| 129 | |
| 130 | for (struct arc arc = |
| 131 | node_adjacency_begin(graph, node_obj(cur)); |