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

Line | Hits | Source
--- | --- | ---
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{`
49 | 2 | `private static String RESIDUAL_CAPACITY_KEY = "jung.algorithms.flows.ResidualCapacity";`
50 | 2 | `private static String PARENT_KEY = "jung.algorithms.flows.Parent";`
51 |  | `//represents the best capacity a node has seen so far`
52 | 2 | `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)`
75 | 10 | `{`
76 | 10 | `if (source.getGraph() != directedGraph || sink.getGraph() != directedGraph)`
77 | 2 | `throw new IllegalArgumentException("source and sink vertices must be elements of the specified graph");`
78 |  | ``
79 | 8 | `if (source.equals(sink))`
80 | 1 | `throw new IllegalArgumentException("source and sink vertices must be distinct");`
81 |  | ``
82 | 7 | `mOriginalGraph = directedGraph;`
83 | 7 | `mFlowGraph = (DirectedGraph) directedGraph.copy();`
84 | 7 | `mSource = (Vertex) source.getEqualVertex(mFlowGraph);`
85 | 7 | `mTarget = (Vertex) sink.getEqualVertex(mFlowGraph);`
86 | 7 | `mEdgeFlowKey = edgeFlowKey;`
87 | 7 | `mEdgeCapacityKey = edgeCapacityKey;`
88 | 7 | `mMaxFlow = 0;`
89 | 7 | `mSinkPartitionNodes = new HashSet();`
90 | 7 | `mSourcePartitionNodes = new HashSet();`
91 | 7 | `mMinCutEdges = new HashSet();`
92 | 7 | `}`
93 |  | ``
94 |  | `private void clearParentValues() {`
95 | 35 | `for (Iterator vIt=mFlowGraph.getVertices().iterator();vIt.hasNext();) {`
96 | 366 | `Vertex currentVertex = (Vertex) vIt.next();`
97 | 366 | `currentVertex.removeUserDatum(PARENT_CAPACITY_KEY);`
98 | 366 | `currentVertex.removeUserDatum(PARENT_KEY);`
99 |  | `}`
100 | 35 | `mSource.setUserDatum(PARENT_CAPACITY_KEY,new MutableInteger(Integer.MAX_VALUE),UserData.SHARED);`
101 | 35 | `mSource.setUserDatum(PARENT_KEY,mSource,UserData.SHARED);`
102 |  | ``
103 | 35 | `}`
104 |  | ``
105 |  | `protected boolean hasAugmentingPath() {`
106 |  | ``
107 | 35 | `mSinkPartitionNodes.clear();`
108 | 35 | `mSourcePartitionNodes.clear();`
109 | 35 | `for (Iterator vIt=mFlowGraph.getVertices().iterator();vIt.hasNext();) {`
110 | 366 | `Vertex v = (Vertex) vIt.next();`
111 | 366 | `mSinkPartitionNodes.add(v);`
112 |  | `}`
113 | 35 | `Set visitedEdgesMap = new HashSet();`
114 | 35 | `Buffer queue = new UnboundedFifoBuffer();`
115 | 35 | `queue.add(mSource);`
116 |  | ``
117 | 360 | `while (!queue.isEmpty()) {`
118 | 325 | `Vertex currentVertex = (Vertex) queue.remove();`
119 | 325 | `mSinkPartitionNodes.remove(currentVertex);`
120 | 325 | `mSourcePartitionNodes.add(currentVertex);`
121 | 325 | `MutableInteger currentCapacity = (MutableInteger) currentVertex.getUserDatum(PARENT_CAPACITY_KEY);`
122 |  | ``
123 | 325 | `Set neighboringEdges = currentVertex.getOutEdges();`
124 |  | ``
125 | 325 | `for (Iterator neIt = neighboringEdges.iterator(); neIt.hasNext();) {`
126 | 1148 | `DirectedEdge neighboringEdge = (DirectedEdge) neIt.next();`
127 | 1148 | `Vertex neighboringVertex = neighboringEdge.getDest();`
128 |  | ``
129 | 1148 | `MutableInteger residualCapacity = (MutableInteger) neighboringEdge.getUserDatum(RESIDUAL_CAPACITY_KEY);`
130 | 1148 | `if (residualCapacity.intValue() <= 0 || visitedEdgesMap.contains(neighboringEdge))`
131 | 25 | `continue;`
132 |  | ``
133 | 936 | `Vertex neighborsParent = (Vertex) neighboringVertex.getUserDatum(PARENT_KEY);`
134 | 936 | `MutableInteger neighborCapacity = (MutableInteger) neighboringVertex.getUserDatum(PARENT_CAPACITY_KEY);`
135 | 936 | `int newCapacity = Math.min(residualCapacity.intValue(),currentCapacity.intValue());`
136 |  | ``
137 | 936 | `if ((neighborsParent == null) || newCapacity > neighborCapacity.intValue()) {`
138 | 322 | `neighboringVertex.setUserDatum(PARENT_KEY,currentVertex,UserData.SHARED);`
139 | 322 | `neighboringVertex.setUserDatum(PARENT_CAPACITY_KEY,new MutableInteger(newCapacity),UserData.SHARED);`
140 | 322 | `visitedEdgesMap.add(neighboringEdge);`
141 | 322 | `if (neighboringVertex != mTarget) {`
142 | 290 | `queue.add(neighboringVertex);`
143 |  | `}`
144 |  | `}`
145 |  | `}`
146 |  | `}`
147 |  | ``
148 | 35 | `boolean hasAugmentingPath = false;`
149 | 35 | `MutableInteger targetsParentCapacity = (MutableInteger) mTarget.getUserDatum(PARENT_CAPACITY_KEY);`
150 | 35 | `if (targetsParentCapacity != null && targetsParentCapacity.intValue() > 0) {`
151 | 29 | `updateResidualCapacities();`
152 | 29 | `hasAugmentingPath = true;`
153 |  | `}`
154 | 35 | `clearParentValues();`
155 | 35 | `return hasAugmentingPath;`
156 |  | ``
157 |  | ``
158 |  | `}`
159 |  | ``
160 |  | `protected double evaluateIteration() {`
161 | 35 | `while (hasAugmentingPath()) {`
162 |  | `}`
163 |  | ``
164 | 6 | `computeMinCut();`
165 | 6 | `return 0;`
166 |  | `}`
167 |  | ``
168 |  | `private void computeMinCut() {`
169 |  | ``
170 | 6 | `for (Iterator eIt=mOriginalGraph.getEdges().iterator();eIt.hasNext();) {`
171 | 158 | `DirectedEdge e = (DirectedEdge) eIt.next();`
172 | 158 | `if (mSinkPartitionNodes.contains(e.getSource()) && mSinkPartitionNodes.contains(e.getDest())) {`
173 | 68 | `continue;`
174 |  | `}`
175 | 90 | `if (mSourcePartitionNodes.contains(e.getSource()) && mSourcePartitionNodes.contains(e.getDest())) {`
176 | 60 | `continue;`
177 |  | `}`
178 | 30 | `if (mSinkPartitionNodes.contains(e.getSource()) && mSourcePartitionNodes.contains(e.getDest())) {`
179 | 6 | `continue;`
180 |  | `}`
181 | 24 | `mMinCutEdges.add(e);`
182 |  | `}`
183 |  | ``
184 | 6 | `}`
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() {`
191 | 2 | `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() {`
200 | 1 | `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() {`
209 | 5 | `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() {`
217 | 1 | `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() {`
226 | 3 | `return (DirectedGraph) mFlowGraph.copy();`
227 |  | `}`
228 |  | ``
229 |  | `protected void initializeIterations() {`
230 | 6 | `mSource.setUserDatum(PARENT_CAPACITY_KEY,new MutableInteger(Integer.MAX_VALUE),UserData.SHARED);`
231 | 6 | `mSource.setUserDatum(PARENT_KEY,mSource,UserData.SHARED);`
232 |  | ``
233 | 6 | `List edgeList = new ArrayList();`
234 | 6 | `edgeList.addAll(mFlowGraph.getEdges());`
235 |  | ``
236 | 164 | `for (int eIdx=0;eIdx< edgeList.size();eIdx++) {`
237 | 158 | `DirectedEdge edge = (DirectedEdge) edgeList.get(eIdx);`
238 | 158 | `Number capacity = (Number) edge.getUserDatum(mEdgeCapacityKey);`
239 | 158 | `if (capacity == null) {`
240 | 0 | `throw new IllegalArgumentException("Edge capacities must be decorated using key: " + mEdgeCapacityKey);`
241 |  | `}`
242 | 158 | `edge.setUserDatum(RESIDUAL_CAPACITY_KEY,new MutableInteger(capacity.intValue()),UserData.SHARED);`
243 |  | ``
244 | 158 | `if (!edge.getDest().isPredecessorOf(edge.getSource())) {`
245 | 62 | `DirectedEdge backEdge = (DirectedEdge) GraphUtils.addEdge(mFlowGraph, edge.getDest(),edge.getSource());`
246 | 62 | `backEdge.setUserDatum(RESIDUAL_CAPACITY_KEY,new MutableInteger(0),UserData.SHARED);`
247 |  | `}`
248 |  | `}`
249 | 6 | `}`
250 |  | ``
251 |  | `protected void finalizeIterations() {`
252 |  | ``
253 | 6 | `for (Iterator eIt=mFlowGraph.getEdges().iterator();eIt.hasNext();) {`
254 | 220 | `DirectedEdge currentEdge = (DirectedEdge) eIt.next();`
255 |  | ``
256 | 220 | `Number capacity = (Number) currentEdge.getUserDatum(mEdgeCapacityKey);`
257 | 220 | `Number residualCapacity = (Number) currentEdge.getUserDatum(RESIDUAL_CAPACITY_KEY);`
258 | 220 | `if (capacity != null) {`
259 | 158 | `MutableInteger flowValue = new MutableInteger(capacity.intValue()-residualCapacity.intValue());`
260 | 158 | `currentEdge.setUserDatum(mEdgeFlowKey,flowValue,UserData.SHARED);`
261 |  | `}`
262 |  | `}`
263 |  | ``
264 | 6 | `Set backEdges = new HashSet();`
265 | 6 | `for (Iterator eIt=mFlowGraph.getEdges().iterator();eIt.hasNext();) {`
266 | 220 | `DirectedEdge currentEdge = (DirectedEdge) eIt.next();`
267 | 220 | `if (currentEdge.getUserDatum(mEdgeCapacityKey) == null) {`
268 | 62 | `backEdges.add(currentEdge);`
269 |  | `} else`
270 | 158 | `currentEdge.removeUserDatum(RESIDUAL_CAPACITY_KEY);`
271 |  | `}`
272 |  | ``
273 | 6 | `GraphUtils.removeEdges(mFlowGraph, backEdges);`
274 | 6 | `}`
275 |  | ``
276 |  | `private void updateResidualCapacities() {`
277 |  | ``
278 | 29 | `MutableInteger augmentingPathCapacity = (MutableInteger) mTarget.getUserDatum(PARENT_CAPACITY_KEY);`
279 | 29 | `mMaxFlow += augmentingPathCapacity.intValue();`
280 | 29 | `Vertex currentVertex = mTarget;`
281 | 29 | `Vertex parentVertex = null;`
282 | 118 | `while ((parentVertex = (Vertex) currentVertex.getUserDatum(PARENT_KEY)) != currentVertex) {`
283 | 89 | `DirectedEdge currentEdge = (DirectedEdge) parentVertex.findEdge(currentVertex);`
284 | 89 | `MutableInteger residualCapacity = (MutableInteger) currentEdge.getUserDatum(RESIDUAL_CAPACITY_KEY);`
285 | 89 | `residualCapacity.subtract(augmentingPathCapacity.intValue());`
286 |  | ``
287 | 89 | `DirectedEdge backEdge = (DirectedEdge) currentVertex.findEdge(parentVertex);`
288 | 89 | `residualCapacity = (MutableInteger) backEdge.getUserDatum(RESIDUAL_CAPACITY_KEY);`
289 | 89 | `residualCapacity.add(augmentingPathCapacity.intValue());`
290 | 89 | `currentVertex = parentVertex;`
291 |  | `}`
292 | 29 | `}`
293 |  | `}`

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.