jcoverage | summary | package | file

Coverage details for edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow

LineHitsSource
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.HashSet;
14 import java.util.Iterator;
15 import java.util.List;
16 import java.util.Set;
17  
18 import org.apache.commons.collections.Buffer;
19 import org.apache.commons.collections.buffer.UnboundedFifoBuffer;
20  
21 import edu.uci.ics.jung.algorithms.IterativeProcess;
22 import edu.uci.ics.jung.graph.DirectedEdge;
23 import edu.uci.ics.jung.graph.DirectedGraph;
24 import edu.uci.ics.jung.graph.Vertex;
25 import edu.uci.ics.jung.utils.GraphUtils;
26 import edu.uci.ics.jung.utils.MutableInteger;
27 import edu.uci.ics.jung.utils.UserData;
28  
29 /**
30  * Implements the EdmondsKarpMaxFlow algorithm for solving the maximum flow problem. After the algorithm is executed,
31  * each edge is labeled with a MutableDouble value that indicates the flow along that edge.
32  * <p>
33  * The algorithm operates on the assumption that the user has provided a UserDatum value (with copy action either
34  * SHARED or CLONE, but not REMOVE) of type Number along
35  * each edge indicating the capacity available.
36  * <p>
37  * An example of using this algorithm is as follows:
38  * <pre>
39  * EdmondsKarpMaxFlow ek = new EdmondsKarpMaxFlow(graph,sourceVertex,"CAPACITY","FLOW");
40  * ek.evaluate(); // This actually instructs the solver 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
47  */
48 public class EdmondsKarpMaxFlow extends IterativeProcess{
492    private static String RESIDUAL_CAPACITY_KEY = "jung.algorithms.flows.ResidualCapacity";
502    private static String PARENT_KEY = "jung.algorithms.flows.Parent";
51     //represents the best capacity a node has seen so far
522    private static String PARENT_CAPACITY_KEY = "jung.algorithms.flows.ParentCapacity";
53     private DirectedGraph mFlowGraph;
54     private DirectedGraph mOriginalGraph;
55     private Vertex mSource;
56     private Vertex mTarget;
57     private String mEdgeFlowKey;
58     private String mEdgeCapacityKey;
59     private int mMaxFlow;
60     private Set mSourcePartitionNodes;
61     private Set mSinkPartitionNodes;
62     private Set mMinCutEdges;
63  
64     /**
65      * Constructs a new instance of the algorithm solver for a given graph, source, and sink.
66      * Source and sink vertices must be elements of the specified graph, and must be
67      * distinct.
68      * @param directedGraph the flow graph
69      * @param source the source vertex
70      * @param sink the sink vertex
71      * @param edgeCapacityKey the UserDatum key that stores the capacity for each edge.
72      * @param edgeFlowKey the UserDatum key where the solver will place the value of the flow for each edge
73      */
74     public EdmondsKarpMaxFlow(DirectedGraph directedGraph, Vertex source, Vertex sink, String edgeCapacityKey, String edgeFlowKey)
7510    {
7610        if (source.getGraph() != directedGraph || sink.getGraph() != directedGraph)
772            throw new IllegalArgumentException("source and sink vertices must be elements of the specified graph");
78         
798        if (source.equals(sink))
801            throw new IllegalArgumentException("source and sink vertices must be distinct");
81         
827        mOriginalGraph = directedGraph;
837        mFlowGraph = (DirectedGraph) directedGraph.copy();
847        mSource = (Vertex) source.getEqualVertex(mFlowGraph);
857        mTarget = (Vertex) sink.getEqualVertex(mFlowGraph);
867        mEdgeFlowKey = edgeFlowKey;
877        mEdgeCapacityKey = edgeCapacityKey;
887        mMaxFlow = 0;
897        mSinkPartitionNodes = new HashSet();
907        mSourcePartitionNodes = new HashSet();
917        mMinCutEdges = new HashSet();
927    }
93  
94     private void clearParentValues() {
9535        for (Iterator vIt=mFlowGraph.getVertices().iterator();vIt.hasNext();) {
96366            Vertex currentVertex = (Vertex) vIt.next();
97366            currentVertex.removeUserDatum(PARENT_CAPACITY_KEY);
98366            currentVertex.removeUserDatum(PARENT_KEY);
99         }
10035        mSource.setUserDatum(PARENT_CAPACITY_KEY,new MutableInteger(Integer.MAX_VALUE),UserData.SHARED);
10135        mSource.setUserDatum(PARENT_KEY,mSource,UserData.SHARED);
102  
10335    }
104  
105     protected boolean hasAugmentingPath() {
106  
10735        mSinkPartitionNodes.clear();
10835        mSourcePartitionNodes.clear();
10935        for (Iterator vIt=mFlowGraph.getVertices().iterator();vIt.hasNext();) {
110366            Vertex v = (Vertex) vIt.next();
111366            mSinkPartitionNodes.add(v);
112         }
11335        Set visitedEdgesMap = new HashSet();
11435        Buffer queue = new UnboundedFifoBuffer();
11535        queue.add(mSource);
116  
117360        while (!queue.isEmpty()) {
118325            Vertex currentVertex = (Vertex) queue.remove();
119325            mSinkPartitionNodes.remove(currentVertex);
120325            mSourcePartitionNodes.add(currentVertex);
121325            MutableInteger currentCapacity = (MutableInteger) currentVertex.getUserDatum(PARENT_CAPACITY_KEY);
122  
123325            Set neighboringEdges = currentVertex.getOutEdges();
124  
125325            for (Iterator neIt = neighboringEdges.iterator(); neIt.hasNext();) {
1261148                DirectedEdge neighboringEdge = (DirectedEdge) neIt.next();
1271148                Vertex neighboringVertex = neighboringEdge.getDest();
128  
1291148                MutableInteger residualCapacity = (MutableInteger) neighboringEdge.getUserDatum(RESIDUAL_CAPACITY_KEY);
1301148                if (residualCapacity.intValue() <= 0 || visitedEdgesMap.contains(neighboringEdge))
13125                    continue;
132  
133936                Vertex neighborsParent = (Vertex) neighboringVertex.getUserDatum(PARENT_KEY);
134936                MutableInteger neighborCapacity = (MutableInteger) neighboringVertex.getUserDatum(PARENT_CAPACITY_KEY);
135936                int newCapacity = Math.min(residualCapacity.intValue(),currentCapacity.intValue());
136  
137936                if ((neighborsParent == null) || newCapacity > neighborCapacity.intValue()) {
138322                    neighboringVertex.setUserDatum(PARENT_KEY,currentVertex,UserData.SHARED);
139322                    neighboringVertex.setUserDatum(PARENT_CAPACITY_KEY,new MutableInteger(newCapacity),UserData.SHARED);
140322                    visitedEdgesMap.add(neighboringEdge);
141322                    if (neighboringVertex != mTarget) {
142290                       queue.add(neighboringVertex);
143                     }
144                 }
145             }
146         }
147  
14835        boolean hasAugmentingPath = false;
14935        MutableInteger targetsParentCapacity = (MutableInteger) mTarget.getUserDatum(PARENT_CAPACITY_KEY);
15035        if (targetsParentCapacity != null && targetsParentCapacity.intValue() > 0) {
15129            updateResidualCapacities();
15229            hasAugmentingPath = true;
153         }
15435        clearParentValues();
15535        return hasAugmentingPath;
156  
157  
158     }
159  
160      protected double evaluateIteration() {
16135        while (hasAugmentingPath()) {
162         }
163  
1646        computeMinCut();
1656        return 0;
166     }
167  
168     private void computeMinCut() {
169  
1706        for (Iterator eIt=mOriginalGraph.getEdges().iterator();eIt.hasNext();) {
171158            DirectedEdge e = (DirectedEdge) eIt.next();
172158            if (mSinkPartitionNodes.contains(e.getSource()) && mSinkPartitionNodes.contains(e.getDest())) {
17368                continue;
174             }
17590            if (mSourcePartitionNodes.contains(e.getSource()) && mSourcePartitionNodes.contains(e.getDest())) {
17660                continue;
177             }
17830            if (mSinkPartitionNodes.contains(e.getSource()) && mSourcePartitionNodes.contains(e.getDest())) {
1796                continue;
180             }
18124            mMinCutEdges.add(e);
182         }
183  
1846    }
185  
186     /**
187      * Returns the max flow value
188      * @return int the value of the maximum flow from the source to the sink
189      */
190     public int getMaxFlow() {
1912        return mMaxFlow;
192     }
193  
194     /**
195      * Retrieves the nodes lying on the side of the partition (partitioned using the
196      * min-cut) of the sink node
197      * @return the set of nodes in the sink partition class
198      */
199     public Set getNodesInSinkPartition() {
2001        return mSinkPartitionNodes;
201     }
202  
203     /**
204      * Retrieves the nodes lying on the side of the partition (partitioned using the
205      * min-cut) of the source node
206      * @return the set of nodes in the source partition class
207      */
208     public Set getNodesInSourcePartition() {
2095        return mSourcePartitionNodes;
210     }
211  
212     /**
213      * Retrieve the min-cut edge set
214      * @return set of edges in the min cut set
215      */
216     public Set getMinCutEdges() {
2171        return mMinCutEdges;
218  
219     }
220  
221     /**
222      * Retrieves the flow graph used to compute the max flow
223      * @return a copy of the flow graph
224      */
225     public DirectedGraph getFlowGraph() {
2263        return (DirectedGraph) mFlowGraph.copy();
227     }
228  
229     protected void initializeIterations() {
2306        mSource.setUserDatum(PARENT_CAPACITY_KEY,new MutableInteger(Integer.MAX_VALUE),UserData.SHARED);
2316        mSource.setUserDatum(PARENT_KEY,mSource,UserData.SHARED);
232  
2336        List edgeList = new ArrayList();
2346        edgeList.addAll(mFlowGraph.getEdges());
235  
236164        for (int eIdx=0;eIdx< edgeList.size();eIdx++) {
237158            DirectedEdge edge = (DirectedEdge) edgeList.get(eIdx);
238158            Number capacity = (Number) edge.getUserDatum(mEdgeCapacityKey);
239158            if (capacity == null) {
2400                throw new IllegalArgumentException("Edge capacities must be decorated using key: " + mEdgeCapacityKey);
241             }
242158            edge.setUserDatum(RESIDUAL_CAPACITY_KEY,new MutableInteger(capacity.intValue()),UserData.SHARED);
243  
244158            if (!edge.getDest().isPredecessorOf(edge.getSource())) {
24562                DirectedEdge backEdge = (DirectedEdge) GraphUtils.addEdge(mFlowGraph, edge.getDest(),edge.getSource());
24662                backEdge.setUserDatum(RESIDUAL_CAPACITY_KEY,new MutableInteger(0),UserData.SHARED);
247             }
248         }
2496    }
250  
251     protected void finalizeIterations() {
252  
2536        for (Iterator eIt=mFlowGraph.getEdges().iterator();eIt.hasNext();) {
254220            DirectedEdge currentEdge = (DirectedEdge) eIt.next();
255  
256220            Number capacity = (Number) currentEdge.getUserDatum(mEdgeCapacityKey);
257220            Number residualCapacity = (Number) currentEdge.getUserDatum(RESIDUAL_CAPACITY_KEY);
258220            if (capacity != null) {
259158                MutableInteger flowValue = new MutableInteger(capacity.intValue()-residualCapacity.intValue());
260158                currentEdge.setUserDatum(mEdgeFlowKey,flowValue,UserData.SHARED);
261             }
262         }
263  
2646        Set backEdges = new HashSet();
2656        for (Iterator eIt=mFlowGraph.getEdges().iterator();eIt.hasNext();) {
266220            DirectedEdge currentEdge = (DirectedEdge) eIt.next();
267220            if (currentEdge.getUserDatum(mEdgeCapacityKey) == null) {
26862                backEdges.add(currentEdge);
269             } else
270158                currentEdge.removeUserDatum(RESIDUAL_CAPACITY_KEY);
271         }
272  
2736        GraphUtils.removeEdges(mFlowGraph, backEdges);
2746    }
275  
276     private void updateResidualCapacities() {
277  
27829        MutableInteger augmentingPathCapacity = (MutableInteger) mTarget.getUserDatum(PARENT_CAPACITY_KEY);
27929        mMaxFlow += augmentingPathCapacity.intValue();
28029        Vertex currentVertex = mTarget;
28129        Vertex parentVertex = null;
282118        while ((parentVertex = (Vertex) currentVertex.getUserDatum(PARENT_KEY)) != currentVertex) {
28389            DirectedEdge currentEdge = (DirectedEdge) parentVertex.findEdge(currentVertex);
28489            MutableInteger residualCapacity = (MutableInteger) currentEdge.getUserDatum(RESIDUAL_CAPACITY_KEY);
28589            residualCapacity.subtract(augmentingPathCapacity.intValue());
286  
28789            DirectedEdge backEdge = (DirectedEdge) currentVertex.findEdge(parentVertex);
28889            residualCapacity = (MutableInteger) backEdge.getUserDatum(RESIDUAL_CAPACITY_KEY);
28989            residualCapacity.add(augmentingPathCapacity.intValue());
29089            currentVertex = parentVertex;
291         }
29229    }
293 }

jcoverage | summary | package | file

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.