FordFulkerson (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.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 O(E V (E + V)) time, where V is the number of vertices and E is the number of edges. In practice, the algorithm will run much faster. The inCut() and value() methods take Θ(1) time. It uses Θ(V) extra space (not including the network).
This correctly computes the maxflow and mincut if all arithmetic performed is without floating-point rounding error or arithmetic overflow. This is guaranteed to be the case if all edge capacities and initial flow values are integers and the value of the maxflow does not exceed 2⁵².
For additional documentation, see Section 6.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors
Constructor	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

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`boolean`	`inCut(int v)`	Returns true if the specified vertex is on the `s` side of the mincut.
`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, 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:
    
    IllegalArgumentException - unless 0 <= s < V
    
    IllegalArgumentException - 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)
```
    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 mincut; false otherwise
    
    Throws:
    
    IllegalArgumentException - unless 0 <= v < V
  - main
```
public static void main(String[] args)
```
    Unit tests the FordFulkerson data type.
    
    Parameters:
    
    args - the command-line arguments