maxflow.h

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