C++ Reference
C++ Reference: Graph
max_flow.h
std::vector< NodeIndex > bfs_queue_
Definition: max_flow.h:611
void SetUseGlobalUpdate(bool value)
Definition: max_flow.h:414
FlowQuantity Flow(ArcIndex arc) const
Definition: max_flow.h:365
MaxFlow(const StarGraph *graph, NodeIndex source, NodeIndex target)
Definition: max_flow.h:654
void Push(Element element, IntegerPriority priority)
Definition: max_flow.h:673
FlowModel CreateFlowModelOfLastSolve()
void ProcessNodeByHeight(bool value)
Definition: max_flow.h:421
bool IsAdmissible(ArcIndex arc) const
Definition: max_flow.h:430
ArcIndex AddArcWithCapacity(NodeIndex tail, NodeIndex head, FlowQuantity capacity)
Status Solve(NodeIndex source, NodeIndex sink)
void ComputeReachableNodes(NodeIndex start, std::vector< NodeIndex > *result)
std::vector< bool > node_in_bfs_queue_
Definition: max_flow.h:610
bool SaturateOutgoingArcsFromSource()
void GlobalUpdate()
bool use_global_update_
Definition: max_flow.h:614
bool IsArcValid(ArcIndex arc) const
PriorityQueueWithRestrictedPush()
Definition: max_flow.h:266
void SetArcFlow(ArcIndex arc, FlowQuantity new_flow)
NodeIndex GetSinkNodeIndex() const
Definition: max_flow.h:349
Definition: christofides.h:33
PriorityQueueWithRestrictedPush< NodeIndex, NodeHeight > active_node_by_height_
Definition: max_flow.h:597
bool Solve()
ZVector< FlowQuantity > QuantityArray
Definition: ebert_graph.h:209
bool CheckResult() const
void RefineWithGlobalUpdate()
bool IsEmpty() const
Definition: max_flow.h:661
NodeIndex Head(ArcIndex arc) const
Graph::OutgoingArcIterator OutgoingArcIterator
Definition: max_flow.h:319
ArcIndex NumArcs() const
FlowQuantity Flow(ArcIndex arc) const
ZVector< ArcIndex > ArcIndexArray
Definition: max_flow.h:323
void SetCapacityAndClearFlow(ArcIndex arc, FlowQuantity capacity)
Definition: max_flow.h:442
bool IsArcDirect(ArcIndex arc) const
QuantityArray residual_arc_capacity_
Definition: max_flow.h:581
void SetCheckResult(bool value)
Definition: max_flow.h:420
void GetSourceSideMinCut(std::vector< NodeIndex > *result)
Definition: max_flow.h:152
void SetArcCapacity(ArcIndex arc, FlowQuantity capacity)
void Discharge(NodeIndex node)
std::string DebugString(const std::string &context, ArcIndex arc) const
NodeIndex Tail(ArcIndex arc) const
Definition: max_flow.h:533
Definition: ebert_graph.h:188
void GetSourceSideMinCut(std::vector< NodeIndex > *result)
void InitializeActiveNodeContainer()
static const FlowQuantity kMaxFlowQuantity
Definition: max_flow.h:544
GenericMaxFlow(const Graph *graph, NodeIndex source, NodeIndex sink)
NodeIndex GetAndRemoveFirstActiveNode()
Definition: max_flow.h:460
NodeIndex Tail(ArcIndex arc) const
Definition: max_flow.h:652
virtual ~GenericMaxFlow()
Definition: max_flow.h:335
FlowQuantity OptimalFlow() const
bool IsActive(NodeIndex node) const
Definition: max_flow.h:437
NodeIndex NumNodes() const
void Refine()
void PushFlowExcessBackToSource()
void Relabel(NodeIndex node)
bool CheckRelabelPrecondition(NodeIndex node) const
ZVector< NodeHeight > NodeHeightArray
Definition: max_flow.h:328
NodeHeightArray node_potential_
Definition: max_flow.h:563
Graph::IncomingArcIterator IncomingArcIterator
Definition: max_flow.h:322
Graph::OutgoingOrOppositeIncomingArcIterator OutgoingOrOppositeIncomingArcIterator
Definition: max_flow.h:321
void PushFlow(FlowQuantity flow, ArcIndex arc)
Definition: graph.h:548
void InitializePreflow()
bool AugmentingPathExists() const
SimpleMaxFlow()
void PushActiveNode(const NodeIndex &node)
Definition: max_flow.h:468
void GetSinkSideMinCut(std::vector< NodeIndex > *result)
void SetUseTwoPhaseAlgorithm(bool value)
Definition: max_flow.h:418
bool process_node_by_height_
Definition: max_flow.h:629
bool use_two_phase_algorithm_
Definition: max_flow.h:621
bool CheckInputConsistency() const
FlowQuantity Capacity(ArcIndex arc) const
FlowQuantity GetOptimalFlow() const
Definition: max_flow.h:361
QuantityArray node_excess_
Definition: max_flow.h:550
FlowModel CreateFlowModel()
std::vector< NodeIndex > active_nodes_
Definition: max_flow.h:590
NodeIndex Head(ArcIndex arc) const
Definition: max_flow.h:532
ArcIndexArray first_admissible_arc_
Definition: max_flow.h:584
FlowQuantity Capacity(ArcIndex arc) const
Definition: max_flow.h:375
void SetArcCapacity(ArcIndex arc, FlowQuantity new_capacity)
NodeIndex GetSourceNodeIndex() const
Definition: max_flow.h:346
void GetSinkSideMinCut(std::vector< NodeIndex > *result)
ArcIndex Opposite(ArcIndex arc) const
void SetCheckInput(bool value)
Definition: max_flow.h:419
bool IsEmptyActiveNodeContainer()
Definition: max_flow.h:477