Package com.jgalgo

Interface MaximumFlow

public interface MaximumFlow

Calculate the maximum flow in a flow network.

A maximum flow is firstly a valid flow, namely for each vertex except the source and sink the sum of flow units going along Graph.inEdges(int) must be equal to the sum of flow units going along Graph.outEdges(int). In addition, a maximum flow maximize the number of flow units originated at the source and reaching the sink, which is equivalent to the sum of flows going out(in) of the source(sink) subtracted by the sum of flows going in(out) to the source(sink).

 
 Graph g = ...;
 FlowNetwork net = FlowNetwork.createAsEdgeWeight(g);
 for (int e : g.edges())
  f.setCapacity(e, 1);

 int sourceVertex = ...;
 int targetVertex = ...;
 MaxFlow maxFlowAlg = MaximumFlow.newBuilder().build();

 double totalFlow = maxFlowAlg.computeMaximumFlow(g, net, sourceVertex, targetVertex);
 System.out.println("The maximum flow that can be pushed in the network is " + totalFlow);
 for (int e : g.edges()) {
 	double capacity = net.getCapacity(e);
 	double flow = net.getFlow(e);
 	System.out.println("flow on edge " + e + ": " + flow + "/" + capacity);
 }
 

Author:

Barak Ugav

See Also:

FlowNetwork

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	MaximumFlow.Builder	A builder for MaximumFlow objects.

Method Summary

Modifier and Type	Method	Description
double	computeMaximumFlow(Graph g, FlowNetwork net, int source, int sink)	Calculate the maximum flow in a flow network.
static MaximumFlow.Builder	newBuilder()	Create a new maximum flow algorithm builder.

Method Detail

computeMaximumFlow

double computeMaximumFlow(Graph g,
                          FlowNetwork net,
                          int source,
                          int sink)

Calculate the maximum flow in a flow network.

The function will set the edges flow by FlowNetwork.setFlow(int, double).

Parameters:

g - a graph

net - network flow

source - a source vertex

sink - a sink vertex

Returns:

the maximum flow in the network from the source to the sink

Throws:

IllegalArgumentException - if the source and the sink are the same vertex

newBuilder

static MaximumFlow.Builder newBuilder()

Create a new maximum flow algorithm builder.

This is the recommended way to instantiate a new MaximumFlow object.

Returns:

a new builder that can build MaximumFlow objects