| 10 | #define MIN(x, y) (((x) < (y)) ? (x) : (y)) |
| 11 | |
| 12 | bool BFS_path(const tal_t *ctx, const struct graph *graph, |
| 13 | const struct node source, const struct node destination, |
| 14 | const s64 *capacity, const s64 cap_threshold, struct arc *prev) |
| 15 | { |
| 16 | const tal_t *this_ctx = tal(ctx, tal_t); |
| 17 | bool target_found = false; |
| 18 | assert(graph); |
| 19 | const size_t max_num_arcs = graph_max_num_arcs(graph); |
| 20 | const size_t max_num_nodes = graph_max_num_nodes(graph); |
| 21 | |
| 22 | /* check preconditions */ |
| 23 | assert(source.idx < max_num_nodes); |
| 24 | assert(capacity); |
| 25 | assert(prev); |
| 26 | assert(tal_count(capacity) == max_num_arcs); |
| 27 | assert(tal_count(prev) == max_num_nodes); |
| 28 | |
| 29 | for (size_t i = 0; i < max_num_nodes; i++) |
| 30 | prev[i].idx = INVALID_INDEX; |
| 31 | |
| 32 | /* A minimalistic queue is implemented here. Nodes are not visited more |
| 33 | * than once, therefore a maximum size of max_num_nodes is sufficient. |
| 34 | * max_num_arcs would work as well but we expect max_num_arcs to be a |
| 35 | * factor >10 greater than max_num_nodes. */ |
| 36 | u32 *queue = tal_arr(this_ctx, u32, max_num_nodes); |
| 37 | size_t queue_start = 0, queue_end = 0; |
| 38 | |
| 39 | queue[queue_end++] = source.idx; |
| 40 | |
| 41 | while (queue_start < queue_end) { |
| 42 | struct node cur = {.idx = queue[queue_start++]}; |
| 43 | |
| 44 | if (cur.idx == destination.idx) { |
| 45 | target_found = true; |
| 46 | break; |
| 47 | } |
| 48 | |
| 49 | for (struct arc arc = node_adjacency_begin(graph, cur); |
| 50 | !node_adjacency_end(arc); |
| 51 | arc = node_adjacency_next(graph, arc)) { |
| 52 | /* check if this arc is traversable */ |
| 53 | if (capacity[arc.idx] < cap_threshold) |
| 54 | continue; |
| 55 | |
| 56 | const struct node next = arc_head(graph, arc); |
| 57 | |
| 58 | /* if that node has been seen previously */ |
| 59 | if (prev[next.idx].idx != INVALID_INDEX || |
| 60 | next.idx == source.idx) |
| 61 | continue; |
| 62 | |
| 63 | prev[next.idx] = arc; |
| 64 | |
| 65 | assert(queue_end < max_num_nodes); |
| 66 | queue[queue_end++] = next.idx; |
| 67 | } |
| 68 | } |
| 69 | |