168#ifndef OR_TOOLS_GRAPH_MIN_COST_FLOW_H_
169#define OR_TOOLS_GRAPH_MIN_COST_FLOW_H_
187template <
typename Graph,
typename ArcFlowType,
typename ArcScaledCostType>
188class GenericMinCostFlow;
244 return SolveWithPossibleAdjustment(SupplyAdjustment::DONT_ADJUST);
253 return SolveWithPossibleAdjustment(SupplyAdjustment::ADJUST);
283 typedef ::util::ReverseArcStaticGraph<NodeIndex, ArcIndex> Graph;
284 enum SupplyAdjustment { ADJUST, DONT_ADJUST };
290 Status SolveWithPossibleAdjustment(SupplyAdjustment adjustment);
293 std::vector<NodeIndex> arc_tail_;
294 std::vector<NodeIndex> arc_head_;
295 std::vector<FlowQuantity> arc_capacity_;
296 std::vector<FlowQuantity> node_supply_;
297 std::vector<CostValue> arc_cost_;
298 std::vector<ArcIndex> arc_permutation_;
299 std::vector<FlowQuantity> arc_flow_;
331 typedef typename Graph::OutgoingOrOppositeIncomingArcIterator
374 std::vector<NodeIndex>*
const infeasible_demand_node);
424 bool IsAdmissible(
ArcIndex arc)
const;
439 bool CheckInputConsistency()
const;
445 bool CheckResult()
const;
449 bool CheckCostRange()
const;
455 bool CheckRelabelPrecondition(
NodeIndex node)
const;
459 std::string DebugString(
const std::string&
context,
ArcIndex arc)
const;
463 void ResetFirstAdmissibleArcs();
475 void SaturateAdmissibleArcs();
485 void InitializeActiveNodeStack();
519 bool IsArcDirect(
ArcIndex arc)
const;
520 bool IsArcValid(
ArcIndex arc)
const;
552 ZVector<ArcFlowType> residual_arc_capacity_;
560 std::stack<NodeIndex> active_nodes_;
573 ZVector<ArcScaledCostType> scaled_arc_unit_cost_;
595 int num_relabels_since_last_price_update_;
598 bool feasibility_checked_;
601 bool use_price_update_;
604 bool check_feasibility_;
Graph::OutgoingArcIterator OutgoingArcIterator
CostValue UnitCost(ArcIndex arc) const
Graph::OutgoingOrOppositeIncomingArcIterator OutgoingOrOppositeIncomingArcIterator
FlowQuantity FeasibleSupply(NodeIndex node) const
FlowQuantity Flow(ArcIndex arc) const
GenericMinCostFlow(const Graph *graph)
Graph::NodeIndex NodeIndex
void SetCheckFeasibility(bool value)
void SetNodeSupply(NodeIndex node, FlowQuantity supply)
FlowQuantity InitialSupply(NodeIndex node) const
const Graph * graph() const
void SetArcFlow(ArcIndex arc, ArcFlowType new_flow)
bool CheckFeasibility(std::vector< NodeIndex > *const infeasible_supply_node, std::vector< NodeIndex > *const infeasible_demand_node)
FlowQuantity Capacity(ArcIndex arc) const
CostValue GetOptimalCost() const
FlowQuantity Supply(NodeIndex node) const
void SetArcUnitCost(ArcIndex arc, ArcScaledCostType unit_cost)
ZVector< ArcIndex > ArcIndexArray
void SetUseUpdatePrices(bool value)
void SetArcCapacity(ArcIndex arc, ArcFlowType new_capacity)
MinCostFlow(const StarGraph *graph)
CostValue UnitCost(ArcIndex arc) const
ArcIndex AddArcWithCapacityAndUnitCost(NodeIndex tail, NodeIndex head, FlowQuantity capacity, CostValue unit_cost)
Status SolveMaxFlowWithMinCost()
FlowQuantity Flow(ArcIndex arc) const
FlowQuantity MaximumFlow() const
NodeIndex NumNodes() const
SimpleMinCostFlow(NodeIndex reserve_num_nodes=0, ArcIndex reserve_num_arcs=0)
void SetNodeSupply(NodeIndex node, FlowQuantity supply)
NodeIndex Tail(ArcIndex arc) const
FlowQuantity Capacity(ArcIndex arc) const
FlowQuantity Supply(NodeIndex node) const
NodeIndex Head(ArcIndex arc) const
CostValue OptimalCost() const
GurobiMPCallbackContext * context
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
ZVector< FlowQuantity > QuantityArray
ZVector< CostValue > CostArray