Package com.jgalgo

Interface MinimumCostFlow

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 nodes, 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.

Author:

Barak Ugav

See Also:

MaximumFlow, FlowNetwork, 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
void	computeMinCostFlow(Graph g, FlowNetwork net, WeightFunction cost, WeightFunction supply)	Compute the min-cost (not maximum!) flow in a network given a supply for each vertex.
void	computeMinCostFlow(Graph g, FlowNetwork net, WeightFunction cost, WeightFunction lowerBound, WeightFunction 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.
void	computeMinCostMaxFlow(Graph g, FlowNetwork net, WeightFunction cost, int source, int sink)	Compute the min-cost max-flow in a network between a source and a sink.
void	computeMinCostMaxFlow(Graph g, FlowNetwork net, WeightFunction cost, WeightFunction lowerBound, int source, int sink)	Compute the min-cost max-flow in a network between a source and a sink given a lower bound for the edges flows.
void	computeMinCostMaxFlow(Graph g, FlowNetwork net, WeightFunction cost, WeightFunction lowerBound, IntCollection sources, IntCollection 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.
void	computeMinCostMaxFlow(Graph g, FlowNetwork net, WeightFunction cost, IntCollection sources, IntCollection sinks)	Compute the min-cost max-flow in a network between a set of sources and a set of sinks.
static MinimumCostFlow.Builder	newBuilder()	Create a new minimum cost flow algorithm builder.

Method Detail

computeMinCostMaxFlow

void computeMinCostMaxFlow(Graph g,
                           FlowNetwork net,
                           WeightFunction cost,
                           int source,
                           int sink)

Compute the min-cost max-flow in a network between a source and a sink.

Parameters:

g - the graph

net - the flow network. The result flow values will be set using this network

cost - an edge weight function representing the cost of each unit of flow along the edge

source - a source vertex

sink - a sink vertex

computeMinCostMaxFlow

void computeMinCostMaxFlow(Graph g,
                           FlowNetwork net,
                           WeightFunction cost,
                           WeightFunction lowerBound,
                           int source,
                           int sink)

Compute the min-cost max-flow in a network between a source and a sink given a lower bound for the edges flows.

Parameters:

g - the graph

net - the flow network. The result flow values will be set using this network

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

computeMinCostMaxFlow

void computeMinCostMaxFlow(Graph g,
                           FlowNetwork net,
                           WeightFunction cost,
                           IntCollection sources,
                           IntCollection sinks)

Compute the min-cost max-flow in a network between a set of sources and a set of sinks.

Parameters:

g - the graph

net - the flow network. The result flow values will be set using this network

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

computeMinCostMaxFlow

void computeMinCostMaxFlow(Graph g,
                           FlowNetwork net,
                           WeightFunction cost,
                           WeightFunction lowerBound,
                           IntCollection sources,
                           IntCollection 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.

Parameters:

g - the graph

net - the flow network. The result flow values will be set using this network

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

computeMinCostFlow

void computeMinCostFlow(Graph g,
                        FlowNetwork net,
                        WeightFunction cost,
                        WeightFunction 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.

Parameters:

g - the graph

net - the flow network. The result flow values will be set using this network

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

computeMinCostFlow

void computeMinCostFlow(Graph g,
                        FlowNetwork net,
                        WeightFunction cost,
                        WeightFunction lowerBound,
                        WeightFunction 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.

Parameters:

g - the graph

net - the flow network. The result flow values will be set using this network

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

newBuilder

static MinimumCostFlow.Builder newBuilder()

Create a new minimum cost flow algorithm builder.

This is the recommended way to instantiate a new MinimumCostFlow object.

Returns:

a new builder that can build MinimumCostFlow objects