Algorithms in a Nutshell

(^232) | Chapter 8: Network Flow Algorithms
Any search method that extends the abstractSearchclass in Figure 8-5 can be
used to locate an augmenting path. The original description of FORD-FULKERSON
uses DEPTH-FIRSTSEARCHwhile EDMONDS-KARPuses BREADTH-FIRSTSEARCH
(see Chapter 6).
// Compute maximal flow for the flow network. Results of the
// computation are stored within the flow network object.
public boolean compute ( ) {
boolean augmented = false;
while (searchMethod.findAugmentingPath(network.vertices)) {
processPath(network.vertices);
augmented = true;
}
return augmented;
}
// Find edge in augmenting path with lowest potential to be increased
// and augment flows within path from source to sink by that amount
protected void processPath(VertexInfo []vertices) {
int v = network.sinkIndex;
int delta = Integer.MAX_VALUE; // goal is to find smallest
while (v != network.sourceIndex) {
int u = vertices[v].previous;
int flow;
if (vertices[v].forward) {
// Forward edges can be adjusted by remaining capacity on edge
flow = network.edge(u, v).capacity - network.edge(u, v).flow;
} else {
// Backward edges can only be reduced by their existing flow
flow = network.edge(v, u).flow;
}
if (flow < delta) { delta = flow; } // smaller candidate flow
v = u; // follow reverse path to source
}
// Adjust path (forward is added, backward is reduced) with delta.
v = network.sinkIndex;
while (v != network.sourceIndex) {
int u = vertices[v].previous;
if (vertices[v].forward) {
network.edge(u, v).flow += delta;
} else {
network.edge(v, u).flow -= delta;
}
v = u; // follow reverse path to source
}
Arrays.fill(network.vertices, null); // reset for next iteration
}
}
Example 8-1. Sample Java Ford-Fulkerson implementation (continued)
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use