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