Algorithm
Development Kit 1.0

algs.model.network
Class FordFulkerson

java.lang.Object
  extended by algs.model.network.FordFulkerson

public class FordFulkerson
extends java.lang.Object

Given a flow network (see definition below) with known capacities on each directed edge, compute the maximal flow between the source vertex and the sink vertex.

A Flow Network is a directed graph G=(V,E) with two special vertices, source and sink. Each edge (u, v) has an associated capacity c(u,v) >= 0, and the resulting computation leaves f(u,v) flow values with each edge. Since it is likely that the problem data is stored in a rich set of classes, this algorithm assumes that the multi-dimensional data needed by the algorithm is provided up-front.

The structure of the data is as follows: Each edge (i,j) is represented by an EdgeInfo object containing:

Each vertex is represented by a VertexInfo object containing: Note that available is the running total (regardless of path) as we compute along. While the FlowNetwork and Search classes are parameterized, at this level of detail there is no need to know what its generic parameter is, which is why we suppress warnings about generics.

Author:
George Heineman

Constructor Summary
FordFulkerson(FlowNetwork network, Search method)
          Construct instance to compute maximum flow across the given network, using the given search method to find an augmenting path.
 
Method Summary
 boolean compute()
          Compute the Maximal flow for the given flow network.
protected  void processPath(VertexInfo[] vertices)
          Augments the flows within the network along the path found from source to sink.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

FordFulkerson

public FordFulkerson(FlowNetwork network,
                     Search method)
Construct instance to compute maximum flow across the given network, using the given search method to find an augmenting path.

Parameters:
network - The FlowNetwork
method - The method for locating augmenting paths within the network.
Method Detail

compute

public boolean compute()
Compute the Maximal flow for the given flow network.

The results of the computation are stored within the network object. Specifically, the final labeling of vertices computes the set S of nodes which is disjoint from the unlabeled vertices which form the set T. Together, S and T represent the disjoint split of the graph into two sets whose connecting edges for the min-cut, in other words, the forward edges from S to T all have flow values which equal their capacity. Thus no additional augmentations are possible.

Returns:
true if an augmenting path was found; false otherwise.
Throws:
java.lang.Exception - if the graph structure is not a flow network.

processPath

protected void processPath(VertexInfo[] vertices)
Augments the flows within the network along the path found from source to sink.

Walking backwards from the sink vertex to the source vertex, this updates the flow values for the edges in the augmenting path by finding the most constraining edge in the augmenting path. This minimum amount is the maximum amount that can be augmented over the augmenting path. Special care is required for backward edges which can "give up" only as much flow is going over the forward direction of the edge.

Note that the available units in the sinkIndex are used as the additive value (for forward edges) and the subtractive value (for backward edges).

Parameters:
vertices - Stores information about the computed augmented path

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.