Package com.jgalgo.alg.flow

Class MinimumCostFlowAbstract

java.lang.Object

com.jgalgo.alg.flow.MinimumCostFlowAbstract

All Implemented Interfaces:

MinimumCostFlow

Direct Known Subclasses:

MinimumCostFlowAbstractBasedSourceSink, MinimumCostFlowAbstractBasedSupply

public abstract class MinimumCostFlowAbstract
extends Object
implements MinimumCostFlow

Abstract class for computing minimum cost flow in a graph.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.flow.MinimumCostFlow

MinimumCostFlow.Builder

Constructor Summary

Constructors

Constructor	Description
MinimumCostFlowAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<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.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MinimumCostFlowAbstract

public MinimumCostFlowAbstract()

Default constructor.

Method Detail

computeMinCostMaxFlow

public <V,E> Flow<V,E> computeMinCostMaxFlow(Graph<V,E> g,
                                                         WeightFunction<E> capacity,
                                                         WeightFunction<E> cost,
                                                         V source,
                                                         V sink)

Description copied from interface: MinimumCostFlow

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.

Specified by:

computeMinCostMaxFlow in interface MinimumCostFlow

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

public <V,E> Flow<V,E> computeMinCostMaxFlow(Graph<V,E> g,
                                                         WeightFunction<E> capacity,
                                                         WeightFunction<E> cost,
                                                         WeightFunction<E> lowerBound,
                                                         V source,
                                                         V sink)

Description copied from interface: MinimumCostFlow

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.

Specified by:

computeMinCostMaxFlow in interface MinimumCostFlow

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

public <V,E> Flow<V,E> computeMinCostMaxFlow(Graph<V,E> g,
                                                         WeightFunction<E> capacity,
                                                         WeightFunction<E> cost,
                                                         Collection<V> sources,
                                                         Collection<V> sinks)

Description copied from interface: MinimumCostFlow

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.

Specified by:

computeMinCostMaxFlow in interface MinimumCostFlow

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

public <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)

Description copied from interface: MinimumCostFlow

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.

Specified by:

computeMinCostMaxFlow in interface MinimumCostFlow

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

public <V,E> Flow<V,E> computeMinCostFlow(Graph<V,E> g,
                                                      WeightFunction<E> capacity,
                                                      WeightFunction<E> cost,
                                                      WeightFunction<V> supply)

Description copied from interface: MinimumCostFlow

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.

Specified by:

computeMinCostFlow in interface MinimumCostFlow

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

public <V,E> Flow<V,E> computeMinCostFlow(Graph<V,E> g,
                                                      WeightFunction<E> capacity,
                                                      WeightFunction<E> cost,
                                                      WeightFunction<E> lowerBound,
                                                      WeightFunction<V> supply)

Description copied from interface: MinimumCostFlow

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.

Specified by:

computeMinCostFlow in interface MinimumCostFlow

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