edu.princeton.cs.algs4

Class FordFulkerson

java.lang.Object

edu.princeton.cs.algs4.FordFulkerson

public class FordFulkerson
extends java.lang.Object

The FordFulkerson class represents a data type for computing a maximum st-flow and minimum st-cut in a flow network.

This implementation uses the Ford-Fulkerson algorithm with the shortest augmenting path heuristic. The constructor takes time proportional to E V (E + V) in the worst case and extra space (not including the network) proportional to V, where V is the number of vertices and E is the number of edges. In practice, the algorithm will run much faster. Afterwards, the inCut() and value() methods take constant time.

If the capacities and initial flow values are all integers, then this implementation guarantees to compute an integer-valued maximum flow. If the capacities and floating-point numbers, then floating-point roundoff error can accumulate.

For additional documentation, see Section 6.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
FordFulkerson(FlowNetwork G, int s, int t) Compute a maximum flow and minimum cut in the network G from vertex s to vertex t.

Method Summary

Modifier and Type	Method and Description
boolean	inCut(int v) Returns true if the specified vertex is on the s side of the mincut.
static void	main(java.lang.String[] args) Unit tests the FordFulkerson data type.
double	value() Returns the value of the maximum flow.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FordFulkerson

public FordFulkerson(FlowNetwork G,
                     int s,
                     int t)

Compute a maximum flow and minimum cut in the network G from vertex s to vertex t.

Parameters:

G - the flow network

s - the source vertex

t - the sink vertex

Throws:

java.lang.IllegalArgumentException - unless 0 <= s < V

java.lang.IllegalArgumentException - unless 0 <= t < V

java.lang.IllegalArgumentException - if s == t

java.lang.IllegalArgumentException - if initial flow is infeasible

Method Detail

value

public double value()

Returns the value of the maximum flow.

Returns:

the value of the maximum flow

inCut

public boolean inCut(int v)

Returns true if the specified vertex is on the s side of the mincut.

Parameters:

v - vertex

Returns:

true if vertex v is on the s side of the micut; false otherwise

Throws:

java.lang.IllegalArgumentException - unless 0 <= v < V

main

public static void main(java.lang.String[] args)

Unit tests the FordFulkerson data type.

Parameters:

args - the command-line arguments