third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.java

   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 }