View Javadoc

1   /*
2   * Copyright (c) 2003, the JUNG Project and the Regents of the University 
3   * of California
4   * All rights reserved.
5   *
6   * This software is open-source under the BSD license; see either
7   * "license.txt" or
8   * http://jung.sourceforge.net/license.txt for a description.
9   */
10  package edu.uci.ics.jung.algorithms.flows;
11  
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;
17  import java.util.Map;
18  import java.util.Set;
19  
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;
24  
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;
28  
29  
30  /**
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.
35   * <p>
36   * An example of using this algorithm is as follows:
37   * <pre>
38   * EdmondsKarpMaxFlow ek = new EdmondsKarpMaxFlow(graph, source, sink, edge_capacities, edge_flows, 
39   * edge_factory);
40   * ek.evaluate(); // This instructs the class to compute the max flow
41   * </pre>
42   *
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
47   */
48  public class EdmondsKarpMaxFlow<V,E> extends IterativeProcess {
49  
50      private DirectedGraph<V,E> mFlowGraph;
51      private DirectedGraph<V,E> mOriginalGraph;
52      private V source;
53      private V target;
54      private int mMaxFlow;
55      private Set<V> mSourcePartitionNodes;
56      private Set<V> mSinkPartitionNodes;
57      private Set<E> mMinCutEdges;
58      
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;
65  
66      /**
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 
69       * distinct.
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
76       */
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) {
81      	
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");
85      	}
86          if (source.equals(sink)) {
87              throw new IllegalArgumentException("source and sink vertices must be distinct");
88          }
89          mOriginalGraph = directedGraph;
90  
91          this.source = source;
92          this.target = sink;
93          this.edgeFlowMap = edgeFlowMap;
94          this.edgeCapacityTransformer = edgeCapacityTransformer;
95          this.edgeFactory = edgeFactory;
96          try {
97  			mFlowGraph = directedGraph.getClass().newInstance();
98  			for(E e : mOriginalGraph.getEdges()) {
99  				mFlowGraph.addEdge(e, mOriginalGraph.getSource(e), 
100 						mOriginalGraph.getDest(e), EdgeType.DIRECTED);
101 			}
102 			for(V v : mOriginalGraph.getVertices()) {
103 				mFlowGraph.addVertex(v);
104 			}
105 
106 		} catch (InstantiationException e) {
107 			e.printStackTrace();
108 		} catch (IllegalAccessException e) {
109 			e.printStackTrace();
110 		}
111         mMaxFlow = 0;
112         mSinkPartitionNodes = new HashSet<V>();
113         mSourcePartitionNodes = new HashSet<V>();
114         mMinCutEdges = new HashSet<E>();
115     }
116 
117     private void clearParentValues() {
118     	parentMap.clear();
119     	parentCapacityMap.clear();
120         parentCapacityMap.put(source, Integer.MAX_VALUE);
121         parentMap.put(source, source);
122     }
123 
124     protected boolean hasAugmentingPath() {
125 
126         mSinkPartitionNodes.clear();
127         mSourcePartitionNodes.clear();
128         mSinkPartitionNodes.addAll(mFlowGraph.getVertices());
129 
130         Set<E> visitedEdgesMap = new HashSet<E>();
131         Buffer<V> queue = new UnboundedFifoBuffer<V>();
132         queue.add(source);
133 
134         while (!queue.isEmpty()) {
135             V currentVertex = queue.remove();
136             mSinkPartitionNodes.remove(currentVertex);
137             mSourcePartitionNodes.add(currentVertex);
138             Number currentCapacity = parentCapacityMap.get(currentVertex);
139 
140             Collection<E> neighboringEdges = mFlowGraph.getOutEdges(currentVertex);
141             
142             for (E neighboringEdge : neighboringEdges) {
143 
144                 V neighboringVertex = mFlowGraph.getDest(neighboringEdge);
145 
146                 Number residualCapacity = residualCapacityMap.get(neighboringEdge);
147                 if (residualCapacity.intValue() <= 0 || visitedEdgesMap.contains(neighboringEdge))
148                     continue;
149 
150                 V neighborsParent = parentMap.get(neighboringVertex);
151                 Number neighborCapacity = parentCapacityMap.get(neighboringVertex);
152                 int newCapacity = Math.min(residualCapacity.intValue(),currentCapacity.intValue());
153 
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);
160                     }
161                 }
162             }
163         }
164 
165         boolean hasAugmentingPath = false;
166         Number targetsParentCapacity = parentCapacityMap.get(target);
167         if (targetsParentCapacity != null && targetsParentCapacity.intValue() > 0) {
168             updateResidualCapacities();
169             hasAugmentingPath = true;
170         }
171         clearParentValues();
172         return hasAugmentingPath;
173     }
174 
175      @Override
176     public void step() {
177         while (hasAugmentingPath()) {
178         }
179         computeMinCut();
180 //        return 0;
181     }
182 
183     private void computeMinCut() {
184 
185         for (E e : mOriginalGraph.getEdges()) {
186 
187         	V source = mOriginalGraph.getSource(e);
188         	V destination = mOriginalGraph.getDest(e);
189             if (mSinkPartitionNodes.contains(source) && mSinkPartitionNodes.contains(destination)) {
190                 continue;
191             }
192             if (mSourcePartitionNodes.contains(source) && mSourcePartitionNodes.contains(destination)) {
193                 continue;
194             }
195             if (mSinkPartitionNodes.contains(source) && mSourcePartitionNodes.contains(destination)) {
196                 continue;
197             }
198             mMinCutEdges.add(e);
199         }
200     }
201 
202     /**
203      * Returns the value of the maximum flow from the source to the sink.
204      */
205     public int getMaxFlow() {
206         return mMaxFlow;
207     }
208 
209     /**
210      * Returns the nodes which share the same partition (as defined by the min-cut edges)
211      * as the sink node.
212      */
213     public Set<V> getNodesInSinkPartition() {
214         return mSinkPartitionNodes;
215     }
216 
217     /**
218      * Returns the nodes which share the same partition (as defined by the min-cut edges)
219      * as the source node.
220      */
221     public Set<V> getNodesInSourcePartition() {
222         return mSourcePartitionNodes;
223     }
224 
225     /**
226      * Returns the edges in the minimum cut.
227      */
228     public Set<E> getMinCutEdges() {
229         return mMinCutEdges;
230     }
231 
232     /**
233      * Returns the graph for which the maximum flow is calculated.
234      */
235     public DirectedGraph<V,E> getFlowGraph() {
236         return mFlowGraph;
237     }
238 
239     @Override
240     protected void initializeIterations() {
241         parentCapacityMap.put(source, Integer.MAX_VALUE);
242         parentMap.put(source, source);
243 
244         List<E> edgeList = new ArrayList<E>(mFlowGraph.getEdges());
245 
246         for (int eIdx=0;eIdx< edgeList.size();eIdx++) {
247             E edge = edgeList.get(eIdx);
248             Number capacity = edgeCapacityTransformer.transform(edge);
249 
250             if (capacity == null) {
251                 throw new IllegalArgumentException("Edge capacities must be provided in Transformer passed to constructor");
252             }
253             residualCapacityMap.put(edge, capacity);
254 
255             V source = mFlowGraph.getSource(edge);
256             V destination = mFlowGraph.getDest(edge);
257 
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);
262             }
263         }
264     }
265     
266     @Override
267     protected void finalizeIterations() {
268 
269         for (E currentEdge : mFlowGraph.getEdges()) {
270             Number capacity = edgeCapacityTransformer.transform(currentEdge);
271             
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);
276             }
277         }
278 
279         Set<E> backEdges = new HashSet<E>();
280         for (E currentEdge: mFlowGraph.getEdges()) {
281         	
282             if (edgeCapacityTransformer.transform(currentEdge) == null) {
283                 backEdges.add(currentEdge);
284             } else {
285                 residualCapacityMap.remove(currentEdge);
286             }
287         }
288         for(E e : backEdges) {
289         	mFlowGraph.removeEdge(e);
290         }
291     }
292 
293     private void updateResidualCapacities() {
294 
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);
301 
302             Number residualCapacity = residualCapacityMap.get(currentEdge);
303 
304             residualCapacity = residualCapacity.intValue() - augmentingPathCapacity.intValue();
305             residualCapacityMap.put(currentEdge, residualCapacity);
306 
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;
312         }
313     }
314 }