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, Wikipedia

    • Method Detail

      • computeMaximumFlow

        double computeMaximumFlow​(Graph g,
                          FlowNetwork net,
                          int source,
                          int sink)
        Calculate the maximum flow in a network between a source and a sink.

        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

      • computeMaximumFlow

        double computeMaximumFlow​(Graph g,
                          FlowNetwork net,
                          IntCollection sources,
                          IntCollection sinks)
        Calculate the maximum flow in a network between a set of sources and a set of sinks.

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

        Parameters:
        g - a graph
        net - network flow
        sources - a set of source vertices
        sinks - a set of sink vertices
        Returns:
        the maximum flow in the network from the sources to the sinks
        Throws:
        IllegalArgumentException - if a vertex is both a source and a sink, or if a vertex appear twice in the source or sinks sets

      • 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