C++ Reference: class GenericMinCostFlow

This documentation is automatically generated.

Method
Capacity

Return type: FlowQuantity

Arguments: ArcIndex arc

Returns the capacity of the given arc.

CheckFeasibility

Return type: bool

Arguments: std::vector<NodeIndex>* const infeasible_supply_node, std::vector<NodeIndex>* const 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 that CheckFeasibility is called by Solve() when the flag min_cost_flow_check_feasibility is set to true (which is the default.)

FeasibleSupply

Return type: FlowQuantity

Arguments: NodeIndex node

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.

Flow

Return type: FlowQuantity

Arguments: ArcIndex arc

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

GenericMinCostFlow

Return type: explicit

Arguments: const Graph* graph

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.

GetOptimalCost

Return type: CostValue

Returns the cost of the minimum-cost flow found by the algorithm.

graph

Return type: const Graph*

Returns the graph associated to the current object.

InitialSupply

Return type: FlowQuantity

Arguments: NodeIndex node

Returns the initial supply at a given node.

MakeFeasible

Return type: bool

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.

SetArcCapacity

Return type: void

Arguments: ArcIndex arc, ArcFlowType new_capacity

Sets the capacity for the given arc.

SetArcFlow

Return type: void

Arguments: 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.

SetArcUnitCost

Return type: void

Arguments: ArcIndex arc, ArcScaledCostType unit_cost

Sets the unit cost for the given arc.

SetCheckFeasibility

Return type: void

Arguments: bool value

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.

SetNodeSupply

Return type: void

Arguments: NodeIndex node, FlowQuantity supply

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

SetUseUpdatePrices

Return type: void

Arguments: bool value

Whether to use the UpdatePrices() heuristic.

Solve

Return type: bool

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

status

Return type: Status

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.

Supply

Return type: FlowQuantity

Arguments: NodeIndex node

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

UnitCost

Return type: CostValue

Arguments: ArcIndex arc

Returns the unscaled cost for the given arc.