86e60e3d |
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 */ |