Package com.jgalgo.alg

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(Object) must be equal to the sum of flow units going along Graph.outEdges(Object). 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).

    Use newInstance() to get a default implementation of this interface. A builder obtained via builder() may support different options to obtain different implementations. 

     
 Graph<String, Integer> g = ...;
 WeightsDouble<Integer> capacities = g.addEdgesWeights("capacity", double.class);
 for (Integer e : g.edges())
  capacities.set(e, 1);

 String sourceVertex = ...;
 String targetVertex = ...;
 MaximumFlow maxFlowAlg = MaximumFlow.newInstance();
 Flow<String, Integer> flow = maxFlowAlg.computeMaximumFlow(g, capacities, sourceVertex, targetVertex);

 System.out.println("The maximum flow that can be pushed in the network is " + flow.getSupply(sourceVertex));
 for (Integer e : g.edges()) {
 	double capacity = capacities.get(e);
 	double f = flow.getFlow(e);
 	System.out.println("flow on edge " + e + ": " + f + "/" + capacity);
 }
    Author:
    Barak Ugav
    See Also:
    Flow, Wikipedia

    • Method Detail

      • computeMaximumFlow

        <V,​E> Flow<V,​E> computeMaximumFlow​(Graph<V,​E> g,
                                               WeightFunction<E> capacity,
                                               V source,
                                               V sink)
        Calculate the maximum flow in a network between a source and a sink.

        Some algorithm might run faster for integer capacities, and WeightFunctionInt can be passed as capacity.

        If g is an IntGraph, its better to pass a IWeightFunction as capacity to avoid boxing/unboxing. If g is an IntGraph, the returned object is IFlow.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        capacity - a capacity edge weight function
        source - a source vertex
        sink - a sink vertex
        Returns:
        the flows computed for each edge
        Throws:
        IllegalArgumentException - if the source and the sink are the same vertex

      • computeMaximumFlow

        <V,​E> Flow<V,​E> computeMaximumFlow​(Graph<V,​E> g,
                                               WeightFunction<E> capacity,
                                               Collection<V> sources,
                                               Collection<V> sinks)
        Calculate the maximum flow in a network between a set of sources and a set of sinks.

        Some algorithm might run faster for integer capacities, and WeightFunctionInt can be passed as capacity.

        If g is an IntGraph, its better to pass a IWeightFunction as capacity to avoid boxing/unboxing. If g is an IntGraph, the returned object is IFlow.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        capacity - a capacity edge weight function
        sources - a set of source vertices
        sinks - a set of sink vertices
        Returns:
        the flows computed for each edge
        Throws:
        IllegalArgumentException - if a vertex is both a source and a sink, or if a vertex appear twice in the source or sinks sets

      • newInstance

        static MaximumFlow newInstance()
        Create a new maximum flow algorithm object.

        This is the recommended way to instantiate a new MaximumFlow object. The MaximumFlow.Builder might support different options to obtain different implementations.

        Returns:
        a default implementation of MaximumFlow