2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
10 package edu.uci.ics.jung.algorithms.flows;
12 import java.util.ArrayList;
13 import java.util.Collection;
14 import java.util.HashMap;
15 import java.util.HashSet;
16 import java.util.List;
20 import org.apache.commons.collections15.Buffer;
21 import org.apache.commons.collections15.Factory;
22 import org.apache.commons.collections15.Transformer;
23 import org.apache.commons.collections15.buffer.UnboundedFifoBuffer;
25 import edu.uci.ics.jung.algorithms.util.IterativeProcess;
26 import edu.uci.ics.jung.graph.DirectedGraph;
27 import edu.uci.ics.jung.graph.util.EdgeType;
31 * Implements the Edmonds-Karp maximum flow algorithm for solving the maximum flow problem.
32 * After the algorithm is executed,
33 * the input {@code Map} is populated with a {@code Number} for each edge that indicates
34 * the flow along that edge.
36 * An example of using this algorithm is as follows:
38 * EdmondsKarpMaxFlow ek = new EdmondsKarpMaxFlow(graph, source, sink, edge_capacities, edge_flows,
40 * ek.evaluate(); // This instructs the class to compute the max flow
43 * @see "Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein."
44 * @see "Network Flows by Ahuja, Magnanti, and Orlin."
45 * @see "Theoretical improvements in algorithmic efficiency for network flow problems by Edmonds and Karp, 1972."
46 * @author Scott White, adapted to jung2 by Tom Nelson
48 public class EdmondsKarpMaxFlow<V,E> extends IterativeProcess {
50 private DirectedGraph<V,E> mFlowGraph;
51 private DirectedGraph<V,E> mOriginalGraph;
55 private Set<V> mSourcePartitionNodes;
56 private Set<V> mSinkPartitionNodes;
57 private Set<E> mMinCutEdges;
59 private Map<E,Number> residualCapacityMap = new HashMap<E,Number>();
60 private Map<V,V> parentMap = new HashMap<V,V>();
61 private Map<V,Number> parentCapacityMap = new HashMap<V,Number>();
62 private Transformer<E,Number> edgeCapacityTransformer;
63 private Map<E,Number> edgeFlowMap;
64 private Factory<E> edgeFactory;
67 * Constructs a new instance of the algorithm solver for a given graph, source, and sink.
68 * Source and sink vertices must be elements of the specified graph, and must be
70 * @param directedGraph the flow graph
71 * @param source the source vertex
72 * @param sink the sink vertex
73 * @param edgeCapacityTransformer the transformer that gets the capacity for each edge.
74 * @param edgeFlowMap the map where the solver will place the value of the flow for each edge
75 * @param edgeFactory used to create new edge instances for backEdges
77 @SuppressWarnings("unchecked")
78 public EdmondsKarpMaxFlow(DirectedGraph<V,E> directedGraph, V source, V sink,
79 Transformer<E,Number> edgeCapacityTransformer, Map<E,Number> edgeFlowMap,
80 Factory<E> edgeFactory) {
82 if(directedGraph.getVertices().contains(source) == false ||
83 directedGraph.getVertices().contains(sink) == false) {
84 throw new IllegalArgumentException("source and sink vertices must be elements of the specified graph");
86 if (source.equals(sink)) {
87 throw new IllegalArgumentException("source and sink vertices must be distinct");
89 mOriginalGraph = directedGraph;
93 this.edgeFlowMap = edgeFlowMap;
94 this.edgeCapacityTransformer = edgeCapacityTransformer;
95 this.edgeFactory = edgeFactory;
97 mFlowGraph = directedGraph.getClass().newInstance();
98 for(E e : mOriginalGraph.getEdges()) {
99 mFlowGraph.addEdge(e, mOriginalGraph.getSource(e),
100 mOriginalGraph.getDest(e), EdgeType.DIRECTED);
102 for(V v : mOriginalGraph.getVertices()) {
103 mFlowGraph.addVertex(v);
106 } catch (InstantiationException e) {
108 } catch (IllegalAccessException e) {
112 mSinkPartitionNodes = new HashSet<V>();
113 mSourcePartitionNodes = new HashSet<V>();
114 mMinCutEdges = new HashSet<E>();
117 private void clearParentValues() {
119 parentCapacityMap.clear();
120 parentCapacityMap.put(source, Integer.MAX_VALUE);
121 parentMap.put(source, source);
124 protected boolean hasAugmentingPath() {
126 mSinkPartitionNodes.clear();
127 mSourcePartitionNodes.clear();
128 mSinkPartitionNodes.addAll(mFlowGraph.getVertices());
130 Set<E> visitedEdgesMap = new HashSet<E>();
131 Buffer<V> queue = new UnboundedFifoBuffer<V>();
134 while (!queue.isEmpty()) {
135 V currentVertex = queue.remove();
136 mSinkPartitionNodes.remove(currentVertex);
137 mSourcePartitionNodes.add(currentVertex);
138 Number currentCapacity = parentCapacityMap.get(currentVertex);
140 Collection<E> neighboringEdges = mFlowGraph.getOutEdges(currentVertex);
142 for (E neighboringEdge : neighboringEdges) {
144 V neighboringVertex = mFlowGraph.getDest(neighboringEdge);
146 Number residualCapacity = residualCapacityMap.get(neighboringEdge);
147 if (residualCapacity.intValue() <= 0 || visitedEdgesMap.contains(neighboringEdge))
150 V neighborsParent = parentMap.get(neighboringVertex);
151 Number neighborCapacity = parentCapacityMap.get(neighboringVertex);
152 int newCapacity = Math.min(residualCapacity.intValue(),currentCapacity.intValue());
154 if ((neighborsParent == null) || newCapacity > neighborCapacity.intValue()) {
155 parentMap.put(neighboringVertex, currentVertex);
156 parentCapacityMap.put(neighboringVertex, new Integer(newCapacity));
157 visitedEdgesMap.add(neighboringEdge);
158 if (neighboringVertex != target) {
159 queue.add(neighboringVertex);
165 boolean hasAugmentingPath = false;
166 Number targetsParentCapacity = parentCapacityMap.get(target);
167 if (targetsParentCapacity != null && targetsParentCapacity.intValue() > 0) {
168 updateResidualCapacities();
169 hasAugmentingPath = true;
172 return hasAugmentingPath;
177 while (hasAugmentingPath()) {
183 private void computeMinCut() {
185 for (E e : mOriginalGraph.getEdges()) {
187 V source = mOriginalGraph.getSource(e);
188 V destination = mOriginalGraph.getDest(e);
189 if (mSinkPartitionNodes.contains(source) && mSinkPartitionNodes.contains(destination)) {
192 if (mSourcePartitionNodes.contains(source) && mSourcePartitionNodes.contains(destination)) {
195 if (mSinkPartitionNodes.contains(source) && mSourcePartitionNodes.contains(destination)) {
203 * Returns the value of the maximum flow from the source to the sink.
205 public int getMaxFlow() {
210 * Returns the nodes which share the same partition (as defined by the min-cut edges)
213 public Set<V> getNodesInSinkPartition() {
214 return mSinkPartitionNodes;
218 * Returns the nodes which share the same partition (as defined by the min-cut edges)
219 * as the source node.
221 public Set<V> getNodesInSourcePartition() {
222 return mSourcePartitionNodes;
226 * Returns the edges in the minimum cut.
228 public Set<E> getMinCutEdges() {
233 * Returns the graph for which the maximum flow is calculated.
235 public DirectedGraph<V,E> getFlowGraph() {
240 protected void initializeIterations() {
241 parentCapacityMap.put(source, Integer.MAX_VALUE);
242 parentMap.put(source, source);
244 List<E> edgeList = new ArrayList<E>(mFlowGraph.getEdges());
246 for (int eIdx=0;eIdx< edgeList.size();eIdx++) {
247 E edge = edgeList.get(eIdx);
248 Number capacity = edgeCapacityTransformer.transform(edge);
250 if (capacity == null) {
251 throw new IllegalArgumentException("Edge capacities must be provided in Transformer passed to constructor");
253 residualCapacityMap.put(edge, capacity);
255 V source = mFlowGraph.getSource(edge);
256 V destination = mFlowGraph.getDest(edge);
258 if(mFlowGraph.isPredecessor(source, destination) == false) {
259 E backEdge = edgeFactory.create();
260 mFlowGraph.addEdge(backEdge, destination, source, EdgeType.DIRECTED);
261 residualCapacityMap.put(backEdge, 0);
267 protected void finalizeIterations() {
269 for (E currentEdge : mFlowGraph.getEdges()) {
270 Number capacity = edgeCapacityTransformer.transform(currentEdge);
272 Number residualCapacity = residualCapacityMap.get(currentEdge);
273 if (capacity != null) {
274 Integer flowValue = new Integer(capacity.intValue()-residualCapacity.intValue());
275 this.edgeFlowMap.put(currentEdge, flowValue);
279 Set<E> backEdges = new HashSet<E>();
280 for (E currentEdge: mFlowGraph.getEdges()) {
282 if (edgeCapacityTransformer.transform(currentEdge) == null) {
283 backEdges.add(currentEdge);
285 residualCapacityMap.remove(currentEdge);
288 for(E e : backEdges) {
289 mFlowGraph.removeEdge(e);
293 private void updateResidualCapacities() {
295 Number augmentingPathCapacity = parentCapacityMap.get(target);
296 mMaxFlow += augmentingPathCapacity.intValue();
297 V currentVertex = target;
298 V parentVertex = null;
299 while ((parentVertex = parentMap.get(currentVertex)) != currentVertex) {
300 E currentEdge = mFlowGraph.findEdge(parentVertex, currentVertex);
302 Number residualCapacity = residualCapacityMap.get(currentEdge);
304 residualCapacity = residualCapacity.intValue() - augmentingPathCapacity.intValue();
305 residualCapacityMap.put(currentEdge, residualCapacity);
307 E backEdge = mFlowGraph.findEdge(currentVertex, parentVertex);
308 residualCapacity = residualCapacityMap.get(backEdge);
309 residualCapacity = residualCapacity.intValue() + augmentingPathCapacity.intValue();
310 residualCapacityMap.put(backEdge, residualCapacity);
311 currentVertex = parentVertex;