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:

MaximumFlow, Flow, Wikipedia

Nested Class Summary

Nested Classes

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

Method Summary

Modifier and Type	Method	Description
static MinimumCostFlow.Builder	builder()	Create a new minimum cost flow algorithm builder.
<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!)
<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!)
<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.
<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.
<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.
<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.
static MinimumCostFlow	newInstance()	Create a new min-cost-flow algorithm object.

Method Detail

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