C++ Reference
C++ Reference: Graph
Detailed Description
Definition at line 652 of file max_flow.h.
Public Types | |
| typedef Graph::NodeIndex | NodeIndex |
| typedef Graph::ArcIndex | ArcIndex |
| typedef Graph::OutgoingArcIterator | OutgoingArcIterator |
| typedef Graph::OutgoingOrOppositeIncomingArcIterator | OutgoingOrOppositeIncomingArcIterator |
| typedef Graph::IncomingArcIterator | IncomingArcIterator |
| typedef ZVector< ArcIndex > | ArcIndexArray |
| typedef NodeIndex | NodeHeight |
| typedef ZVector< NodeHeight > | NodeHeightArray |
Public Member Functions | |
| MaxFlow (const StarGraph *graph, NodeIndex source, NodeIndex target) | |
| const StarGraph * | graph () const |
| Status | status () const |
| NodeIndex | GetSourceNodeIndex () const |
| NodeIndex | GetSinkNodeIndex () const |
| void | SetArcCapacity (ArcIndex arc, FlowQuantity new_capacity) |
| void | SetArcFlow (ArcIndex arc, FlowQuantity new_flow) |
| bool | Solve () |
| FlowQuantity | GetOptimalFlow () const |
| FlowQuantity | Flow (ArcIndex arc) const |
| FlowQuantity | Capacity (ArcIndex arc) const |
| void | GetSourceSideMinCut (std::vector< NodeIndex > *result) |
| void | GetSinkSideMinCut (std::vector< NodeIndex > *result) |
| bool | CheckInputConsistency () const |
| bool | CheckResult () const |
| bool | AugmentingPathExists () const |
| void | SetUseGlobalUpdate (bool value) |
| void | SetUseTwoPhaseAlgorithm (bool value) |
| void | SetCheckInput (bool value) |
| void | SetCheckResult (bool value) |
| void | ProcessNodeByHeight (bool value) |
| FlowModel | CreateFlowModel () |
Protected Member Functions | |
| bool | IsAdmissible (ArcIndex arc) const |
| bool | IsActive (NodeIndex node) const |
| void | SetCapacityAndClearFlow (ArcIndex arc, FlowQuantity capacity) |
| bool | CheckRelabelPrecondition (NodeIndex node) const |
| std::string | DebugString (const std::string &context, ArcIndex arc) const |
| void | InitializeActiveNodeContainer () |
| NodeIndex | GetAndRemoveFirstActiveNode () |
| void | PushActiveNode (const NodeIndex &node) |
| bool | IsEmptyActiveNodeContainer () |
| void | Refine () |
| void | RefineWithGlobalUpdate () |
| void | Discharge (NodeIndex node) |
| void | InitializePreflow () |
| void | PushFlowExcessBackToSource () |
| void | GlobalUpdate () |
| bool | SaturateOutgoingArcsFromSource () |
| void | PushFlow (FlowQuantity flow, ArcIndex arc) |
| void | Relabel (NodeIndex node) |
| NodeIndex | Head (ArcIndex arc) const |
| NodeIndex | Tail (ArcIndex arc) const |
| ArcIndex | Opposite (ArcIndex arc) const |
| bool | IsArcDirect (ArcIndex arc) const |
| bool | IsArcValid (ArcIndex arc) const |
| void | ComputeReachableNodes (NodeIndex start, std::vector< NodeIndex > *result) |
Protected Attributes | |
| const StarGraph * | graph_ |
| QuantityArray | node_excess_ |
| NodeHeightArray | node_potential_ |
| QuantityArray | residual_arc_capacity_ |
| ArcIndexArray | first_admissible_arc_ |
| std::vector< NodeIndex > | active_nodes_ |
| PriorityQueueWithRestrictedPush< NodeIndex, NodeHeight > | active_node_by_height_ |
| NodeIndex | source_ |
| NodeIndex | sink_ |
| Status | status_ |
| std::vector< bool > | node_in_bfs_queue_ |
| std::vector< NodeIndex > | bfs_queue_ |
| bool | use_global_update_ |
| bool | use_two_phase_algorithm_ |
| bool | process_node_by_height_ |
| bool | check_input_ |
| bool | check_result_ |
| StatsGroup | stats_ |
Static Protected Attributes | |
| static const FlowQuantity | kMaxFlowQuantity |
Member Typedef Documentation
◆ ArcIndex
|
inherited |
Definition at line 318 of file max_flow.h.
◆ ArcIndexArray
|
inherited |
Definition at line 323 of file max_flow.h.
◆ IncomingArcIterator
|
inherited |
Definition at line 322 of file max_flow.h.
◆ NodeHeight
|
inherited |
Definition at line 327 of file max_flow.h.
◆ NodeHeightArray
|
inherited |
Definition at line 328 of file max_flow.h.
◆ NodeIndex
|
inherited |
Definition at line 317 of file max_flow.h.
◆ OutgoingArcIterator
|
inherited |
Definition at line 319 of file max_flow.h.
◆ OutgoingOrOppositeIncomingArcIterator
|
inherited |
Definition at line 321 of file max_flow.h.
Constructor & Destructor Documentation
◆ MaxFlow()
Definition at line 654 of file max_flow.h.
Member Function Documentation
◆ AugmentingPathExists()
|
inherited |
◆ Capacity()
|
inlineinherited |
Definition at line 375 of file max_flow.h.
◆ CheckInputConsistency()
|
inherited |
◆ CheckRelabelPrecondition()
|
protectedinherited |
◆ CheckResult()
|
inherited |
◆ ComputeReachableNodes()
|
protectedinherited |
◆ CreateFlowModel()
|
inherited |
◆ DebugString()
|
protectedinherited |
◆ Discharge()
|
protectedinherited |
◆ Flow()
|
inlineinherited |
Definition at line 365 of file max_flow.h.
◆ GetAndRemoveFirstActiveNode()
|
inlineprotectedinherited |
Definition at line 460 of file max_flow.h.
◆ GetOptimalFlow()
|
inlineinherited |
Definition at line 361 of file max_flow.h.
◆ GetSinkNodeIndex()
|
inlineinherited |
Definition at line 349 of file max_flow.h.
◆ GetSinkSideMinCut()
|
inherited |
◆ GetSourceNodeIndex()
|
inlineinherited |
Definition at line 346 of file max_flow.h.
◆ GetSourceSideMinCut()
|
inherited |
◆ GlobalUpdate()
|
protectedinherited |
◆ graph()
|
inlineinherited |
Definition at line 338 of file max_flow.h.
◆ Head()
Definition at line 532 of file max_flow.h.
◆ InitializeActiveNodeContainer()
|
protectedinherited |
◆ InitializePreflow()
|
protectedinherited |
◆ IsActive()
|
inlineprotectedinherited |
Definition at line 437 of file max_flow.h.
◆ IsAdmissible()
|
inlineprotectedinherited |
Definition at line 430 of file max_flow.h.
◆ IsArcDirect()
|
protectedinherited |
◆ IsArcValid()
|
protectedinherited |
◆ IsEmptyActiveNodeContainer()
|
inlineprotectedinherited |
Definition at line 477 of file max_flow.h.
◆ Opposite()
◆ ProcessNodeByHeight()
|
inlineinherited |
Definition at line 421 of file max_flow.h.
◆ PushActiveNode()
|
inlineprotectedinherited |
Definition at line 468 of file max_flow.h.
◆ PushFlow()
|
protectedinherited |
◆ PushFlowExcessBackToSource()
|
protectedinherited |
◆ Refine()
|
protectedinherited |
◆ RefineWithGlobalUpdate()
|
protectedinherited |
◆ Relabel()
|
protectedinherited |
◆ SaturateOutgoingArcsFromSource()
|
protectedinherited |
◆ SetArcCapacity()
|
inherited |
◆ SetArcFlow()
|
inherited |
◆ SetCapacityAndClearFlow()
|
inlineprotectedinherited |
Definition at line 442 of file max_flow.h.
◆ SetCheckInput()
|
inlineinherited |
Definition at line 419 of file max_flow.h.
◆ SetCheckResult()
|
inlineinherited |
Definition at line 420 of file max_flow.h.
◆ SetUseGlobalUpdate()
|
inlineinherited |
Definition at line 414 of file max_flow.h.
◆ SetUseTwoPhaseAlgorithm()
|
inlineinherited |
Definition at line 418 of file max_flow.h.
◆ Solve()
|
inherited |
◆ status()
|
inlineinherited |
Definition at line 343 of file max_flow.h.
◆ Tail()
Definition at line 533 of file max_flow.h.
Member Data Documentation
◆ active_node_by_height_
|
protectedinherited |
Definition at line 597 of file max_flow.h.
◆ active_nodes_
|
protectedinherited |
Definition at line 590 of file max_flow.h.
◆ bfs_queue_
|
protectedinherited |
Definition at line 611 of file max_flow.h.
◆ check_input_
|
protectedinherited |
Definition at line 634 of file max_flow.h.
◆ check_result_
|
protectedinherited |
Definition at line 638 of file max_flow.h.
◆ first_admissible_arc_
|
protectedinherited |
Definition at line 584 of file max_flow.h.
◆ graph_
|
protectedinherited |
Definition at line 547 of file max_flow.h.
◆ kMaxFlowQuantity
|
staticprotectedinherited |
Definition at line 544 of file max_flow.h.
◆ node_excess_
|
protectedinherited |
Definition at line 550 of file max_flow.h.
◆ node_in_bfs_queue_
|
protectedinherited |
Definition at line 610 of file max_flow.h.
◆ node_potential_
|
protectedinherited |
Definition at line 563 of file max_flow.h.
◆ process_node_by_height_
|
protectedinherited |
Definition at line 629 of file max_flow.h.
◆ residual_arc_capacity_
|
protectedinherited |
Definition at line 581 of file max_flow.h.
◆ sink_
|
protectedinherited |
Definition at line 603 of file max_flow.h.
◆ source_
|
protectedinherited |
Definition at line 600 of file max_flow.h.
◆ stats_
|
mutableprotectedinherited |
Definition at line 641 of file max_flow.h.
◆ status_
|
protectedinherited |
Definition at line 606 of file max_flow.h.
◆ use_global_update_
|
protectedinherited |
Definition at line 614 of file max_flow.h.
◆ use_two_phase_algorithm_
|
protectedinherited |
Definition at line 621 of file max_flow.h.
The documentation for this class was generated from the following file: