Package com.jgalgo.alg.flow

Interface MinimumCostFlow

All Known Implementing Classes:
MinimumCostFlowAbstract, MinimumCostFlowAbstractBasedSourceSink, MinimumCostFlowAbstractBasedSupply, MinimumCostFlowCostScaling, MinimumCostFlowCycleCanceling
public interface MinimumCostFlow
Compute the minimum-cost (max) flow in a flow network.

There are a few variations of the minimum-cost flow problem: (1) given source(s) and sink(s) terminal vertices, and the objecting is to find the flow with the lowest cost out of all maximum flows. (2) given per-vertex finite supply, and the objective is to find a minimum-cost flow satisfying the supply, namely that for each vertex the sum of flow units going out of the vertex minus the sum of flow units going into it is equal to its supply.

In addition to these variants, a lower bound for each edge flow can be specified, similar to the capacities which can be viewed as upper bounds.

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

Author:
Barak Ugav
See Also:

  • Method Details

    • computeMinCostMaxFlow

      <V, E> Flow<V,E> computeMinCostMaxFlow(Graph<V,E> g, WeightFunction<E> capacity, WeightFunction<E> cost, V source, V sink)
      Compute the min-cost max-flow in a network between a source and a sink.

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

      If g is an IntGraph, its better to pass a IWeightFunction as capacity and cost 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 - the graph
      capacity - a capacity edge weight function
      cost - an edge weight function representing the cost of each unit of flow along the edge
      source - a source vertex
      sink - a sink vertex
      Returns:
      the flows computed for each edge

    • computeMinCostMaxFlow

      <V, E> Flow<V,E> computeMinCostMaxFlow(Graph<V,E> g, WeightFunction<E> capacity, WeightFunction<E> cost, WeightFunction<E> lowerBound, V source, V sink)
      Compute the min-cost max-flow in a network between a source and a sink given a lower bound for the edges flows.

      If g is an IntGraph, its better to pass a IWeightFunction as capacity, cost and lowerBound 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 - the graph
      capacity - a capacity edge weight function
      cost - an edge weight function representing the cost of each unit of flow along the edge
      lowerBound - an edge weight function representing a lower bound for the flow along each edge
      source - a source vertex
      sink - a sink vertex
      Returns:
      the flows computed for each edge

    • computeMinCostMaxFlow

      <V, E> Flow<V,E> computeMinCostMaxFlow(Graph<V,E> g, WeightFunction<E> capacity, WeightFunction<E> cost, Collection<V> sources, Collection<V> sinks)
      Compute the min-cost max-flow in a network between a set of sources and a set of sinks.

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

      If g is an IntGraph, its better to pass a IWeightFunction as capacity and cost, and IntCollection as sources and sinks 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 - the graph
      capacity - a capacity edge weight function
      cost - an edge weight function representing the cost of each unit of flow along the edge
      sources - a set of source vertices
      sinks - a set of sinks vertices
      Returns:
      the flows computed for each edge

    • computeMinCostMaxFlow

      <V, E> Flow<V,E> computeMinCostMaxFlow(Graph<V,E> g, WeightFunction<E> capacity, WeightFunction<E> cost, WeightFunction<E> lowerBound, Collection<V> sources, Collection<V> sinks)
      Compute the min-cost max-flow in a network between a set of sources and a set of sinks given a lower bound for the edges flows.

      Some algorithm might run faster for integer networks, and WeightFunctionInt can be passed as argument as capacity, cost and lowerBound.

      If g is an IntGraph, its better to pass a IWeightFunction as capacity, cost and lowerBound, and IntCollection as sources and sinks 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 - the graph
      capacity - a capacity edge weight function
      cost - an edge weight function representing the cost of each unit of flow along the edge
      lowerBound - an edge weight function representing a lower bound for the flow along each edge
      sources - a set of source vertices
      sinks - a set of sinks vertices
      Returns:
      the flows computed for each edge

    • computeMinCostFlow

      <V, E> Flow<V,E> computeMinCostFlow(Graph<V,E> g, WeightFunction<E> capacity, WeightFunction<E> cost, WeightFunction<V> supply)
      Compute the min-cost (not maximum!) flow in a network given a supply for each vertex.

      The supply is a scalar for each vertex, and the objective is to find a minimum-cost flow satisfying the supply, namely that for each vertex the sum of flow units going out of the vertex minus the sum of flow units going into it is equal to its supply.

      Some algorithm might run faster for integer networks, and WeightFunctionInt can be passed as argument as capacity, cost and supply.

      If g is an IntGraph, its better to pass a IWeightFunction as capacity, cost and supply 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 - the graph
      capacity - a capacity edge weight function
      cost - an edge weight function representing the cost of each unit of flow along the edge
      supply - a vertex weight function representing the supply for each vertex
      Returns:
      the flows computed for each edge

    • computeMinCostFlow

      <V, E> Flow<V,E> computeMinCostFlow(Graph<V,E> g, WeightFunction<E> capacity, WeightFunction<E> cost, WeightFunction<E> lowerBound, WeightFunction<V> supply)
      Compute the min-cost (not maximum!) flow in a network given a supply for each vertex and a lower bound for the edges flows.

      The supply is a scalar for each vertex, and the objective is to find a minimum-cost flow satisfying the supply, namely that for each vertex the sum of flow units going out of the vertex minus the sum of flow units going into it is equal to its supply.

      Some algorithm might run faster for integer networks, and WeightFunctionInt can be passed as argument as capacity, cost, lowerBound and supply.

      If g is an IntGraph, its better to pass a IWeightFunction as capacity, cost, lowerBound and supply 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 - the graph
      capacity - a capacity edge weight function
      cost - an edge weight function representing the cost of each unit of flow along the edge
      lowerBound - an edge weight function representing a lower bound for the flow along each edge
      supply - a vertex weight function representing the supply for each vertex
      Returns:
      the flows computed for each edge

    • newInstance

      static MinimumCostFlow newInstance()
      Create a new min-cost-flow algorithm object.

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

      Returns:
      a default implementation of MinimumCostFlow

    • builder

      static MinimumCostFlow.Builder builder()
      Create a new minimum cost flow algorithm builder.

      Use newInstance() for a default implementation.

      Returns:
      a new builder that can build MinimumCostFlow objects