| 1 | /* |
| 2 | * Edmonds-Karp algorithm for finding a maximum flow and minimum |
| 3 | * cut in a network. Almost identical to the Ford-Fulkerson |
| 4 | * algorithm, but apparently using breadth-first search to find the |
| 5 | * _shortest_ augmenting path is a good way to guarantee |
| 6 | * termination and ensure the time complexity is not dependent on |
| 7 | * the actual value of the maximum flow. I don't understand why |
| 8 | * that should be, but it's claimed on the Internet that it's been |
| 9 | * proved, and that's good enough for me. I prefer BFS to DFS |
| 10 | * anyway :-) |
| 11 | */ |
| 12 | |
| 13 | #ifndef MAXFLOW_MAXFLOW_H |
| 14 | #define MAXFLOW_MAXFLOW_H |
| 15 | |
| 16 | /* |
| 17 | * The actual algorithm. |
| 18 | * |
| 19 | * Inputs: |
| 20 | * |
| 21 | * - `scratch' is previously allocated scratch space of a size |
| 22 | * previously determined by calling `maxflow_scratch_size'. |
| 23 | * |
| 24 | * - `nv' is the number of vertices. Vertices are assumed to be |
| 25 | * numbered from 0 to nv-1. |
| 26 | * |
| 27 | * - `source' and `sink' are the distinguished source and sink |
| 28 | * vertices. |
| 29 | * |
| 30 | * - `ne' is the number of edges in the graph. |
| 31 | * |
| 32 | * - `edges' is an array of 2*ne integers, giving a (source, dest) |
| 33 | * pair for each network edge. Edge pairs are expected to be |
| 34 | * sorted in lexicographic order. |
| 35 | * |
| 36 | * - `backedges' is an array of `ne' integers, each a distinct |
| 37 | * index into `edges'. The edges in `edges', if permuted as |
| 38 | * specified by this array, should end up sorted in the _other_ |
| 39 | * lexicographic order, i.e. dest taking priority over source. |
| 40 | * |
| 41 | * - `capacity' is an array of `ne' integers, giving a maximum |
| 42 | * flow capacity for each edge. A negative value is taken to |
| 43 | * indicate unlimited capacity on that edge, but note that there |
| 44 | * may not be any unlimited-capacity _path_ from source to sink |
| 45 | * or an assertion will be failed. |
| 46 | * |
| 47 | * Output: |
| 48 | * |
| 49 | * - `flow' must be non-NULL. It is an array of `ne' integers, |
| 50 | * each giving the final flow along each edge. |
| 51 | * |
| 52 | * - `cut' may be NULL. If non-NULL, it is an array of `nv' |
| 53 | * integers, which will be set to zero or one on output, in such |
| 54 | * a way that: |
| 55 | * + the set of zero vertices includes the source |
| 56 | * + the set of one vertices includes the sink |
| 57 | * + the maximum flow capacity between the zero and one vertex |
| 58 | * sets is achieved (i.e. all edges from a zero vertex to a |
| 59 | * one vertex are at full capacity, while all edges from a |
| 60 | * one vertex to a zero vertex have no flow at all). |
| 61 | * |
| 62 | * - the returned value from the function is the total flow |
| 63 | * achieved. |
| 64 | */ |
| 65 | int maxflow_with_scratch(void *scratch, int nv, int source, int sink, |
| 66 | int ne, const int *edges, const int *backedges, |
| 67 | const int *capacity, int *flow, int *cut); |
| 68 | |
| 69 | /* |
| 70 | * The above function expects its `scratch' and `backedges' |
| 71 | * parameters to have already been set up. This allows you to set |
| 72 | * them up once and use them in multiple invocates of the |
| 73 | * algorithm. Now I provide functions to actually do the setting |
| 74 | * up. |
| 75 | */ |
| 76 | int maxflow_scratch_size(int nv); |
| 77 | void maxflow_setup_backedges(int ne, const int *edges, int *backedges); |
| 78 | |
| 79 | /* |
| 80 | * Simplified version of the above function. All parameters are the |
| 81 | * same, except that `scratch' and `backedges' are constructed |
| 82 | * internally. This is the simplest way to call the algorithm as a |
| 83 | * one-off; however, if you need to call it multiple times on the |
| 84 | * same network, it is probably better to call the above version |
| 85 | * directly so that you only construct `scratch' and `backedges' |
| 86 | * once. |
| 87 | * |
| 88 | * Additional return value is now -1, meaning that scratch space |
| 89 | * could not be allocated. |
| 90 | */ |
| 91 | int maxflow(int nv, int source, int sink, |
| 92 | int ne, const int *edges, const int *capacity, |
| 93 | int *flow, int *cut); |
| 94 | |
| 95 | #endif /* MAXFLOW_MAXFLOW_H */ |