Package com.jgalgo.alg.flow

Interface MaximumFlow

All Known Implementing Classes:
MaximumFlowAbstract, MaximumFlowAbstractWithoutResidualNet, MaximumFlowAbstractWithResidualNet, MaximumFlowDinic, MaximumFlowDinicDynamicTrees, MaximumFlowEdmondsKarp, MaximumFlowPushRelabel, MaximumFlowPushRelabelDynamicTrees
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. 

 
 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:

  • Method Details

    • 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.

      Returns:
      a default implementation of MaximumFlow