C++ Reference: max_flow
Note: This documentation is automatically generated.
An implementation of a push-relabel algorithm for the max flow problem.In the following, we consider a graph G = (V,E,s,t) where V denotes the set of nodes (vertices) in the graph, E denotes the set of arcs (edges). s and t denote distinguished nodes in G called source and target. n = |V| denotes the number of nodes in the graph, and m = |E| denotes the number of arcs in the graph.
Each arc (v,w) is associated a capacity c(v,w).
A flow is a function from E to R such that:
a) f(v,w) <= c(v,w) for all (v,w) in E (capacity constraint.)
b) f(v,w) = -f(w,v) for all (v,w) in E (flow antisymmetry constraint.)
c) sum on v f(v,w) = 0 (flow conservation.)
The goal of this algorithm is to find the maximum flow from s to t, i.e. for example to maximize sum v f(s,v).
The starting reference for this class of algorithms is: A.V. Goldberg and R.E. Tarjan. A new approach to the maximum flow problem. ACM Symposium on Theory of Computing, pp. 136-146. http://portal.acm.org/citation.cfm?id=12144.
The basic idea of the algorithm is to handle preflows instead of flows, and to refine preflows until a maximum flow is obtained. A preflow is like a flow, except that the inflow can be larger than the outflow. If it is the case at a given node v, it is said that there is an excess at node v, and inflow = outflow + excess.
More formally, a preflow is a function f such that:
1) f(v,w) <= c(v,w) for all (v,w) in E (capacity constraint). c(v,w) is a value representing the maximum capacity for arc (v,w).
2) f(v,w) = -f(w,v) for all (v,w) in E (flow antisymmetry constraint)
3) excess(v) = sum on u f(u,v) >= 0 is the excess at node v, the algebraic sum of all the incoming preflows at this node.
Each node has an associated "height", in addition to its excess. The height of the source is defined to be equal to n, and cannot change. The height of the target is defined to be zero, and cannot change either. The height of all the other nodes is initialized at zero and is updated during the algorithm (see below). For those who want to know the details, the height of a node, corresponds to a reduced cost, and this enables one to prove that the algorithm actually computes the max flow. Note that the height of a node can be initialized to the distance to the target node in terms of number of nodes. This has not been tried in this implementation.
A node v is said to be *active* if excess(v) > 0.
In this case the following operations can be applied to it:
- if there are *admissible* incident arcs, i.e. arcs which are not saturated,
and whose head's height is lower than the height of the active node
considered, a PushFlow operation can be applied. It consists in sending as
much flow as both the excess at the node and the capacity of the arc
permit.
- if there are no admissible arcs, the active node considered is relabeled,
i.e. its height is increased to 1 + the minimum height of its neighboring
nodes on admissible arcs. This is implemented in Discharge, which itself calls PushFlow and Relabel.
Before running Discharge, it is necessary to initialize the algorithm with a preflow. This is done in InitializePreflow, which saturates all the arcs leaving the source node, and sets the excess at the heads of those arcs accordingly.
The algorithm terminates when there are no remaining active nodes, i.e. all the excesses at all nodes are equal to zero. In this case, a maximum flow is obtained.
The complexity of this algorithm depends amongst other things on the choice of the next active node. It has been shown, for example in: L. Tuncel, "On the Complexity of Preflow-Push Algorithms for Maximum-Flow Problems", Algorithmica 11(4): 353-359 (1994). and J. Cheriyan and K. Mehlhorn, "An analysis of the highest-level selection rule in the preflow-push max-flow algorithm", Information processing letters, 69(5):239-242 (1999). http://www.math.uwaterloo.ca/~jcheriya/PS_files/me3.0.ps
...that choosing the active node with the highest level yields a complexity of O(n^2 * sqrt(m)).
TODO(user): implement the above active node choice rule.
This has been validated experimentally in: R.K. Ahuja, M. Kodialam, A.K. Mishra, and J.B. Orlin, "Computational Investigations of Maximum Flow Algorithms", EJOR 97:509-542(1997). http://jorlin.scripts.mit.edu/docs/publications/58-comput%20investigations%20of.pdf.
TODO(user): an alternative would be to evaluate: A.V. Goldberg, "The Partial Augment-Relabel Algorithm for the Maximum Flow Problem.” In Proceedings of Algorithms ESA, LNCS 5193:466-477, Springer 2008. http://www.springerlink.com/index/5535k2j1mt646338.pdf
An interesting general reference on network flows is: R. K. Ahuja, T. L. Magnanti, J. B. Orlin, "Network Flows: Theory, Algorithms, and Applications," Prentice Hall, 1993, ISBN: 978-0136175490, http://www.amazon.com/dp/013617549X
Keywords: Push-relabel, max-flow, network, graph, Goldberg, Tarjan, Dinic, Dinitz.
Classes |
|
|---|---|
| GenericMaxFlow | |
| MaxFlow | |
MaxFlowStatusClass | |
| PriorityQueueWithRestrictedPush | |
| SimpleMaxFlow | |