Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Ford-Fulkerson Algorithm Computes Max Flow & Minimum Cut
public class FordFulkerson
{
private static final double FLOATING_POINT_EPSILON = 1E-11;
private final int V; // number of vertices
private boolean[] marked; // marked[v] = true iff s->v path in residual graph
private FlowEdge[] edgeTo; // edgeTo[v] = last edge on shortest residual s->v path
private double value; // current value of max flow
public FordFulkerson( FlowNetwork G, int s, int t )
{
V = G.V();
validate( s );
validate( t );
if ( s == t ) throw new IllegalArgumentException( "Source equals sink" );
if ( !isFeasible( G, s, t ) ) throw new IllegalArgumentException( "Initial flow is infeasible" );
value = excess( G, t );
while ( hasAugmentingPath( G, s, t ) )
{
double bottle = Double.POSITIVE_INFINITY;
for ( int v = t; v != s; v = edgeTo[ v ].other( v ) )
{
bottle = Math.min( bottle, edgeTo[ v ].residualCapacityTo( v ) );
}
for ( int v = t; v != s; v = edgeTo[ v ].other( v ) )
{
edgeTo[ v ].addResidualFlowTo( v, bottle );
}
value += bottle;
}
assert check( G, s, t );
}
public double value()
{ return value; }
public boolean inCut( int v )
{
validate( v );
return marked[ v ];
}
private void validate( int v )
{
if ( v < 0 || v >= V )
throw new IllegalArgumentException( "vertex " + v + " is not between 0 and " + ( V - 1 ) );
}
private boolean hasAugmentingPath( FlowNetwork G, int s, int t )
{
edgeTo = new FlowEdge[ G.V() ];
marked = new boolean[ G.V() ];
Queue<Integer> queue = new Queue<Integer>();
queue.enqueue( s );
marked[ s ] = true;
while ( !queue.isEmpty() && !marked[ t ] )
{
int v = queue.dequeue();
for ( FlowEdge e : G.adj( v ) )
{
int w = e.other( v );
if ( e.residualCapacityTo( w ) > 0)
{
if ( !marked[ w ] )
{
edgeTo[ w ] = e;
marked[ w ] = true;
queue.enqueue( w );
}
}
}
}
return marked[ t ];
}
private double excess( FlowNetwork G, int v )
{
double excess = 0.0;
for ( FlowEdge e : G.adj( v ) )
{
if ( v == e.from() ) excess -= e.flow();
else excess += e.flow();
}
return excess;
}
private boolean isFeasible( FlowNetwork G, int s, int t )
{
for ( int v = 0; v < G.V(); v++ )
{
for ( FlowEdge e : G.adj( v ) )
{
if ( e.flow() < -FLOATING_POINT_EPSILON || e.flow() > e.capacity() + FLOATING_POINT_EPSILON )
{
System.err.println( "Edge does not satisfy capacity constraints: " + e );
return false;
}
}
}
if ( Math.abs( value + excess( G, s ) ) > FLOATING_POINT_EPSILON )
{
System.err.println( "Excess at source = " + excess( G, s ) );
System.err.println( "Max flow = " + value );
return false;
}
if ( Math.abs( value - excess( G, t ) ) > FLOATING_POINT_EPSILON )
{
System.err.println( "Excess at sink = " + excess( G, t ) );
System.err.println( "Max flow = " + value );
return false;
}
for ( int v = 0; v < G.V(); v++ )
{
if ( v == s || v == t ) continue;
else if ( Math.abs( excess( G, v ) ) > FLOATING_POINT_EPSILON )
{
System.err.println( "Net flow out of " + v + " doesn't equal zero" );
return false;
}
}
return true;
}
private boolean check( FlowNetwork G, int s, int t )
{
if ( !isFeasible( G, s, t ) )
{
System.err.println( "Flow is infeasible" );
return false;
}
if ( !inCut( s ) )
{
System.err.println( "source " + s + " is not on source side of min cut" );
return false;
}
if ( inCut( t ) )
{
System.err.println( "sink " + t + " is on source side of min cut" );
return false;
}
double mincutValue = 0.0;
for ( int v = 0; v < G.V(); v++ )
{
for ( FlowEdge e : G.adj( v ) )
{
if ( ( v == e.from() ) && inCut( e.from() ) && !inCut( e.to() ) )
mincutValue += e.capacity();
}
}
if ( Math.abs( mincutValue - value ) > FLOATING_POINT_EPSILON )
{
System.err.println( "Max flow value = " + value + ", min cut value = " + mincutValue );
return false;
}
return true;
}
public static void main( String[] args )
{
int V = Integer.parseInt( args[ 0 ] );
int E = Integer.parseInt( args[ 1 ] );
int s = 0, t = V-1;
FlowNetwork G = new FlowNetwork( V, E );
StdOut.println( G );
FordFulkerson maxflow = new FordFulkerson( G, s, t );
StdOut.println( "Max flow from " + s + " to " + t );
for ( int v = 0; v < G.V(); v++ )
{
for ( FlowEdge e : G.adj( v ) )
{
if ( ( v == e.from() ) && e.flow() > 0 )
StdOut.println( " " + e );
}
}
StdOut.print( "Min cut: " );
for ( int v = 0; v < G.V(); v++ )
{
if ( maxflow.inCut( v ) ) StdOut.print( v + " " );
}
StdOut.println();
StdOut.println( "Max flow value = " + maxflow.value() );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment