Get the max amount of flow one can send from source to target along the path * encoded in `prev`. */
| 880 | /* Get the max amount of flow one can send from source to target along the path |
| 881 | * encoded in `prev`. */ |
| 882 | static s64 get_augmenting_flow( |
| 883 | const struct linear_network* linear_network, |
| 884 | const struct residual_network *residual_network, |
| 885 | const u32 source, |
| 886 | const u32 target, |
| 887 | const struct arc *prev) |
| 888 | { |
| 889 | s64 flow = INFINITE; |
| 890 | |
| 891 | u32 cur = target; |
| 892 | while(cur!=source) |
| 893 | { |
| 894 | assert(cur<tal_count(prev)); |
| 895 | const struct arc arc = prev[cur]; |
| 896 | flow = MIN(flow , residual_network->cap[arc.idx]); |
| 897 | |
| 898 | // we are traversing in the opposite direction to the flow, |
| 899 | // hence the next node is at the tail of the arc. |
| 900 | cur = arc_tail(linear_network,arc); |
| 901 | } |
| 902 | |
| 903 | assert(flow<INFINITE && flow>0); |
| 904 | return flow; |
| 905 | } |
| 906 | |
| 907 | /* Augment a `flow` amount along the path defined by `prev`.*/ |
| 908 | static void augment_flow( |
no test coverage detected