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. |
copyright © 2003, jcoverage ltd. all rights reserved. |