net.sourceforge.combean.graph.alg.flow
Class MulticommodityMinCostFlowByLPAlg

java.lang.Object
  net.sourceforge.combean.graph.alg.AbstractGraphAlg
      net.sourceforge.combean.graph.alg.flow.MulticommodityMinCostFlowByLPAlg

All Implemented Interfaces:

AbstractFlowAlg, FeasibleFlowAlg, MinCostFlowAlg, MulticommodityCapable, MulticommodityMinCostFlowAlg, GraphAlgorithm

public class MulticommodityMinCostFlowByLPAlg
extends AbstractGraphAlg
implements MulticommodityMinCostFlowAlg

An implementation of a multicommodity min-cost flow algorithm using an LP solver.

Constructor Summary

MulticommodityMinCostFlowByLPAlg()
constructor

Method Summary

void	focusOnCommodity(int numCommodity) All subsequent calls for a single commodity (e.g. setting the edge weight, the inflow or the individual capacitiy) refer to the given commodity.
FixedDoubleEdgeMap	getFlowMap() Return the calculated flow.
double	getTotalCost() Calculate the total cost of the flow.
boolean	isFeasible() Check if a feasible flow exists.
void	run() Execute the algorithm.
void	setCommonEdgeCapacityMap(FixedDoubleEdgeMap edgeCapacities) Set the edge capacities for the sum of the flows.
void	setEdgeCapacityMap(FixedDoubleEdgeMap edgeCapacities) Set the edge capacities.
void	setEdgeWeightsMap(FixedDoubleEdgeMap edgeWeights) Set the cost of one unit of flow for each edge.
void	setInflowMap(FixedDoubleNodeMap inflowMap) Set the inflow at each node in the graph.
void	setLpModelLoader(LPModelSolver lpModelSolver)
void	setLpSolver(LPSolver lpSolver)
void	setNumCommodities(int numCommodities) Define the number of commodities.

Methods inherited from class net.sourceforge.combean.graph.alg.AbstractGraphAlg

getGraph, setGraph

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.sourceforge.combean.interfaces.graph.alg.GraphAlgorithm

getGraph, setGraph

Constructor Detail

MulticommodityMinCostFlowByLPAlg

public MulticommodityMinCostFlowByLPAlg()

constructor

Method Detail

setLpModelLoader

public final void setLpModelLoader(LPModelSolver lpModelSolver)

Parameters:

lpModelSolver - The lpModelSolver to set.

setLpSolver

public final void setLpSolver(LPSolver lpSolver)

Parameters:

lpSolver - The lpSolver to set.

setEdgeWeightsMap

public void setEdgeWeightsMap(FixedDoubleEdgeMap edgeWeights)

Description copied from interface: MinCostFlowAlg

Set the cost of one unit of flow for each edge. If this map is not set, the cost is assumed to be zero for each edge.

Specified by:

setEdgeWeightsMap in interface MinCostFlowAlg

Parameters:

edgeWeights - a map containing the cost of each edge in the graph

setInflowMap

public void setInflowMap(FixedDoubleNodeMap inflowMap)

Description copied from interface: FeasibleFlowAlg

Set the inflow at each node in the graph. A positive value means that additional flow is injected at the node, whereas a negative value represents the fact that flow is drained from the network. If this map is not set, the flow balance at each node is assumed to be zero, i.e., inbound equals outbound flow.

Specified by:

setInflowMap in interface FeasibleFlowAlg

Parameters:

inflowMap - the inflow at each node.

setEdgeCapacityMap

public void setEdgeCapacityMap(FixedDoubleEdgeMap edgeCapacities)

Description copied from interface: AbstractFlowAlg

Set the edge capacities.

Specified by:

setEdgeCapacityMap in interface AbstractFlowAlg

Parameters:

edgeCapacities - a map containing the edge capacities.

run

public void run()

Description copied from interface: GraphAlgorithm

Execute the algorithm.

Specified by:

run in interface GraphAlgorithm

isFeasible

public boolean isFeasible()

Description copied from interface: FeasibleFlowAlg

Check if a feasible flow exists. May only be called after the algorithm has been executed.

Specified by:

isFeasible in interface FeasibleFlowAlg

Returns:

true if a feasible flow exists.

getTotalCost

public double getTotalCost()

Description copied from interface: MinCostFlowAlg

Calculate the total cost of the flow. May only be called after the algorithm has been executed.

Specified by:

getTotalCost in interface MinCostFlowAlg

Returns:

the total cost of the flow.

getFlowMap

public FixedDoubleEdgeMap getFlowMap()

Description copied from interface: AbstractFlowAlg

Return the calculated flow. May only be called after the algorithm has been executed.

Specified by:

getFlowMap in interface AbstractFlowAlg

Returns:

the calculated flow.

focusOnCommodity

public void focusOnCommodity(int numCommodity)

Description copied from interface: MulticommodityCapable

All subsequent calls for a single commodity (e.g. setting the edge weight, the inflow or the individual capacitiy) refer to the given commodity.

Specified by:

focusOnCommodity in interface MulticommodityCapable

Parameters:

numCommodity - the commodity to which all subsequent calls shall refer.

setCommonEdgeCapacityMap

public void setCommonEdgeCapacityMap(FixedDoubleEdgeMap edgeCapacities)

Description copied from interface: MulticommodityCapable

Set the edge capacities for the sum of the flows.

Specified by:

setCommonEdgeCapacityMap in interface MulticommodityCapable

Parameters:

edgeCapacities - a map containing the edge capacities.

setNumCommodities

public void setNumCommodities(int numCommodities)

Description copied from interface: MulticommodityCapable

Define the number of commodities. Must be called before any call to focusOnCommodity. Default is one.

Specified by:

setNumCommodities in interface MulticommodityCapable