Forward declaration. More...

#include <min_cost_flow.h>

Inheritance diagram for operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >:

Public Types
typedef Graph::NodeIndex	NodeIndex

typedef Graph::ArcIndex	ArcIndex

typedef Graph::OutgoingArcIterator	OutgoingArcIterator

typedef Graph::OutgoingOrOppositeIncomingArcIterator	OutgoingOrOppositeIncomingArcIterator

typedef ZVector< ArcIndex >	ArcIndexArray

Public Types inherited from operations_research::MinCostFlowBase
enum	Status { NOT_SOLVED , OPTIMAL , FEASIBLE , INFEASIBLE , UNBALANCED , BAD_RESULT , BAD_COST_RANGE }

Public Member Functions
	GenericMinCostFlow (const Graph *graph)

	GenericMinCostFlow (const GenericMinCostFlow &)=delete
	This type is neither copyable nor movable.

GenericMinCostFlow &	operator= (const GenericMinCostFlow &)=delete

const Graph *	graph () const
	Returns the graph associated to the current object.

Status	status () const

void	SetNodeSupply (NodeIndex node, FlowQuantity supply)

void	SetArcUnitCost (ArcIndex arc, ArcScaledCostType unit_cost)
	Sets the unit cost for the given arc.

void	SetArcCapacity (ArcIndex arc, ArcFlowType new_capacity)
	Sets the capacity for the given arc.

void	SetArcFlow (ArcIndex arc, ArcFlowType new_flow)

bool	Solve ()
	Solves the problem, returning true if a min-cost flow could be found.

bool	CheckFeasibility (std::vector< NodeIndex > infeasible_supply_node, std::vector< NodeIndex > infeasible_demand_node)

bool	MakeFeasible ()

CostValue	GetOptimalCost ()

FlowQuantity	Flow (ArcIndex arc) const

FlowQuantity	Capacity (ArcIndex arc) const
	Returns the capacity of the given arc.

CostValue	UnitCost (ArcIndex arc) const
	Returns the unscaled cost for the given arc.

FlowQuantity	Supply (NodeIndex node) const

FlowQuantity	InitialSupply (NodeIndex node) const
	Returns the initial supply at a given node.

FlowQuantity	FeasibleSupply (NodeIndex node) const

void	SetCheckFeasibility (bool value)

void	SetUseUpdatePrices (bool value)
	Algorithm options.

void	SetPriceScaling (bool value)

Detailed Description

template<typename Graph, typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>
class operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >

Forward declaration.

Generic MinCostFlow that works with StarGraph and all the graphs handling reverse arcs from graph.h, see the end of min_cost_flow.cc for the exact types this class is compiled for.

One can greatly decrease memory usage by using appropriately small integer types:

For the Graph<> types, i.e. NodeIndexType and ArcIndexType, see graph.h.
ArcFlowType is used for the per-arc flow quantity. It must be signed, and large enough to hold the maximum arc capacity and its negation.
ArcScaledCostType is used for a per-arc scaled cost. It must be signed and large enough to hold the maximum unit cost of an arc times (num_nodes + 1).

Note: the latter two are different than FlowQuantity and CostValue, which are used for global, aggregated values and may need to be larger.

Todo: (user): Avoid using the globally defined type CostValue and FlowQuantity. Also uses the Arc*Type where there is no risk of overflow in more places.

Definition at line 378 of file min_cost_flow.h.

Member Typedef Documentation

◆ ArcIndex

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

Graph::ArcIndex operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::ArcIndex

Definition at line 381 of file min_cost_flow.h.

◆ ArcIndexArray

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

ZVector<ArcIndex> operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::ArcIndexArray

Definition at line 385 of file min_cost_flow.h.

◆ NodeIndex

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

Graph::NodeIndex operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::NodeIndex

Definition at line 380 of file min_cost_flow.h.

◆ OutgoingArcIterator

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

Graph::OutgoingArcIterator operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::OutgoingArcIterator

Definition at line 382 of file min_cost_flow.h.

◆ OutgoingOrOppositeIncomingArcIterator

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

Graph::OutgoingOrOppositeIncomingArcIterator operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::OutgoingOrOppositeIncomingArcIterator

Definition at line 384 of file min_cost_flow.h.

Constructor & Destructor Documentation

◆ GenericMinCostFlow() [1/2]

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::GenericMinCostFlow ( const Graph * graph )

explicit

Initialize a MinCostFlow instance on the given graph. The graph does not need to be fully built yet, but its capacity reservation is used to initialize the memory of this class.

Definition at line 50 of file min_cost_flow.cc.

◆ GenericMinCostFlow() [2/2]

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::GenericMinCostFlow ( const GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType > & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ Capacity()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

FlowQuantity operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::Capacity ( ArcIndex arc ) const

Returns the capacity of the given arc.

We use the equations given in the comment of residual_arc_capacity_.

Definition at line 364 of file min_cost_flow.cc.

◆ CheckFeasibility()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

bool operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::CheckFeasibility	(	std::vector< NodeIndex > *	infeasible_supply_node,
		std::vector< NodeIndex > *	infeasible_demand_node )

Checks for feasibility, i.e., that all the supplies and demands can be matched without exceeding bottlenecks in the network. If infeasible_supply_node (resp. infeasible_demand_node) are not NULL, they are populated with the indices of the nodes where the initial supplies (resp. demands) are too large. Feasible values for the supplies and demands are accessible through FeasibleSupply.

Note: CheckFeasibility is called by Solve() when the flag min_cost_flow_check_feasibility is set to true (which is the default.)

Create a new graph, which is a copy of graph_, with the following modifications: Two nodes are added: a source and a sink. The source is linked to each supply node (whose supply > 0) by an arc whose capacity is equal to the supply at the supply node. The sink is linked to each demand node (whose supply < 0) by an arc whose capacity is the demand (-supply) at the demand node. There are no supplies or demands or costs in the graph, as we will run max-flow.

Todo: (user): make it possible to share a graph by MaxFlow and MinCostFlow. For this it is necessary to make StarGraph resizable.

Copy graph_ to checker_graph.

Create the source-to-supply node arcs and the demand-node-to-sink arcs.

Definition at line 251 of file min_cost_flow.cc.

◆ FeasibleSupply()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

FlowQuantity operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::FeasibleSupply ( NodeIndex node ) const

Returns the largest supply (if > 0) or largest demand in absolute value (if < 0) admissible at node. If the problem is not feasible, some of these values will be smaller (in absolute value) than the initial supplies and demand given as input.

Definition at line 397 of file min_cost_flow.cc.

◆ Flow()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

FlowQuantity operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::Flow ( ArcIndex arc ) const

Returns the flow on the given arc using the equations given in the comment on residual_arc_capacity_.

Definition at line 352 of file min_cost_flow.cc.

◆ GetOptimalCost()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

CostValue operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::GetOptimalCost ( )

Returns the cost of the minimum-cost flow found by the algorithm. This works in O(num_arcs). This will only work if the last Solve() call was successful and returned true, otherwise it will return 0. Note that the computation might overflow, in which case we will cap the cost at std::numeric_limits<CostValue>::max().

The total cost of the flow. We cap the result if its overflow.

Definition at line 485 of file min_cost_flow.cc.

◆ graph()

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

const Graph * operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::graph ( ) const

inline

Returns the graph associated to the current object.

Definition at line 399 of file min_cost_flow.h.

◆ InitialSupply()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

FlowQuantity operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::InitialSupply ( NodeIndex node ) const

Returns the initial supply at a given node.

Definition at line 390 of file min_cost_flow.cc.

◆ MakeFeasible()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

bool operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::MakeFeasible ( )

Makes the min-cost flow problem solvable by truncating supplies and demands to a level acceptable by the network. There may be several ways to do it. In our case, the levels are computed from the result of the max-flow algorithm run in CheckFeasibility(). MakeFeasible returns false if CheckFeasibility() was not called before.

Definition at line 339 of file min_cost_flow.cc.

◆ operator=()

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

GenericMinCostFlow & operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::operator= ( const GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType > & )

delete

◆ SetArcCapacity()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

void operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::SetArcCapacity	(	ArcIndex	arc,
		ArcFlowType	new_capacity )

Sets the capacity for the given arc.

The above condition is true when one of two following holds: 1/ (capacity_delta > 0), meaning we are increasing the capacity 2/ (capacity_delta < 0 && free_capacity + capacity_delta >= 0) meaning we are reducing the capacity, but that the capacity reduction is not larger than the free capacity.

We have to reduce the flow on the arc, and update the excesses accordingly.

Definition at line 94 of file min_cost_flow.cc.

◆ SetArcFlow()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

void operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::SetArcFlow	(	ArcIndex	arc,
		ArcFlowType	new_flow )

Sets the flow for the given arc. Note that new_flow must be smaller than the capacity of the arc.

Definition at line 131 of file min_cost_flow.cc.

◆ SetArcUnitCost()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

void operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::SetArcUnitCost	(	ArcIndex	arc,
		ArcScaledCostType	unit_cost )

Sets the unit cost for the given arc.

Definition at line 84 of file min_cost_flow.cc.

◆ SetCheckFeasibility()

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

void operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::SetCheckFeasibility ( bool value )

inline

Whether to check the feasibility of the problem with a max-flow, prior to solving it. This uses about twice as much memory, but detects infeasible problems (where the flow can't be satisfied) and makes Solve() return INFEASIBLE. If you disable this check, you will spare memory but you must make sure that your problem is feasible, otherwise the code can loop forever.

Definition at line 477 of file min_cost_flow.h.

◆ SetNodeSupply()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

void operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::SetNodeSupply	(	NodeIndex	node,
		FlowQuantity	supply )

Sets the supply corresponding to node. A demand is modeled as a negative supply.

Definition at line 74 of file min_cost_flow.cc.

◆ SetPriceScaling()

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

void operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::SetPriceScaling ( bool value )

inline

Definition at line 481 of file min_cost_flow.h.

◆ SetUseUpdatePrices()

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

void operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::SetUseUpdatePrices ( bool value )

inline

Algorithm options.

Definition at line 480 of file min_cost_flow.h.

◆ Solve()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

bool operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::Solve ( )

Solves the problem, returning true if a min-cost flow could be found.

Definition at line 454 of file min_cost_flow.cc.

◆ status()

template<typename Graph , typename ArcFlowType = FlowQuantity, typename ArcScaledCostType = CostValue>

Status operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::status ( ) const

inline

Returns the status of last call to Solve(). NOT_SOLVED is returned if Solve() has never been called or if the problem has been modified in such a way that the previous solution becomes invalid.

Definition at line 404 of file min_cost_flow.h.

◆ Supply()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

FlowQuantity operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::Supply ( NodeIndex node ) const

Returns the supply at a given node. Demands are modelled as negative supplies.

Definition at line 382 of file min_cost_flow.cc.

◆ UnitCost()

template<typename Graph , typename ArcFlowType , typename ArcScaledCostType >

CostValue operations_research::GenericMinCostFlow< Graph, ArcFlowType, ArcScaledCostType >::UnitCost ( ArcIndex arc ) const

Returns the unscaled cost for the given arc.

Definition at line 374 of file min_cost_flow.cc.

The documentation for this class was generated from the following files:

ortools/graph/min_cost_flow.h
ortools/graph/min_cost_flow.cc

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ ArcIndex

◆ ArcIndexArray

◆ NodeIndex

◆ OutgoingArcIterator

◆ OutgoingOrOppositeIncomingArcIterator

Constructor & Destructor Documentation

◆ GenericMinCostFlow() [1/2]

◆ GenericMinCostFlow() [2/2]

Member Function Documentation

◆ Capacity()

◆ CheckFeasibility()

◆ FeasibleSupply()

◆ Flow()

◆ GetOptimalCost()

◆ graph()

◆ InitialSupply()

◆ MakeFeasible()

◆ operator=()

◆ SetArcCapacity()

◆ SetArcFlow()

◆ SetArcUnitCost()

◆ SetCheckFeasibility()

◆ SetNodeSupply()

◆ SetPriceScaling()

◆ SetUseUpdatePrices()

◆ Solve()

◆ status()

◆ Supply()

◆ UnitCost()