edu.princeton.cs.algorithms

Class FordFulkerson

java.lang.Object

edu.princeton.cs.algorithms.FordFulkerson

public class FordFulkerson
extends 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 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, 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

Methods

Modifier and Type	Method and Description
boolean	inCut(int v) Is vertex v on the s side of the minimum st-cut?
static void	main(String[] args) Unit tests the FordFulkerson data type.
double	value() Returns the value of the maximum flow.

Methods inherited from class java.lang.Object

clone, equals, finalize, 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:

IndexOutOfBoundsException - unless 0 <= s < V

IndexOutOfBoundsException - unless 0 <= t < V

IllegalArgumentException - if s = t

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)

Is vertex v on the s side of the minimum st-cut?

Returns:

true if vertex v is on the s side of the micut, and false if vertex v is on the t side.

Throws:

IndexOutOfBoundsException - unless 0 <= v < V

main

public static void main(String[] args)

Unit tests the FordFulkerson data type.