![]() |
OR-Tools
8.2
|
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 |
enum | Status { NOT_SOLVED , OPTIMAL , INT_OVERFLOW , BAD_INPUT , BAD_RESULT } |
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 |
|
inherited |
Definition at line 318 of file max_flow.h.
|
inherited |
Definition at line 323 of file max_flow.h.
|
inherited |
Definition at line 322 of file max_flow.h.
|
inherited |
Definition at line 327 of file max_flow.h.
|
inherited |
Definition at line 328 of file max_flow.h.
|
inherited |
Definition at line 317 of file max_flow.h.
|
inherited |
Definition at line 319 of file max_flow.h.
|
inherited |
Definition at line 321 of file max_flow.h.
|
inherited |
Enumerator | |
---|---|
NOT_SOLVED | |
OPTIMAL | |
INT_OVERFLOW | |
BAD_INPUT | |
BAD_RESULT |
Definition at line 302 of file max_flow.h.
Definition at line 654 of file max_flow.h.
|
inherited |
Definition at line 410 of file max_flow.cc.
|
inlineinherited |
Definition at line 375 of file max_flow.h.
|
inherited |
Definition at line 399 of file max_flow.cc.
|
protectedinherited |
Definition at line 450 of file max_flow.cc.
|
inherited |
Definition at line 404 of file max_flow.cc.
|
protectedinherited |
Definition at line 541 of file max_flow.cc.
|
inherited |
Definition at line 426 of file max_flow.cc.
|
protectedinherited |
Definition at line 454 of file max_flow.cc.
|
protectedinherited |
Definition at line 491 of file max_flow.cc.
|
inlineinherited |
Definition at line 365 of file max_flow.h.
|
inlineprotectedinherited |
Definition at line 460 of file max_flow.h.
|
inlineinherited |
Definition at line 361 of file max_flow.h.
|
inlineinherited |
Definition at line 349 of file max_flow.h.
|
inherited |
Definition at line 395 of file max_flow.cc.
|
inlineinherited |
Definition at line 346 of file max_flow.h.
|
inherited |
Definition at line 386 of file max_flow.cc.
|
protectedinherited |
Definition at line 511 of file max_flow.cc.
|
inlineinherited |
Definition at line 338 of file max_flow.h.
Definition at line 532 of file max_flow.h.
|
protectedinherited |
Definition at line 457 of file max_flow.cc.
|
protectedinherited |
Definition at line 494 of file max_flow.cc.
|
inlineprotectedinherited |
Definition at line 437 of file max_flow.h.
|
inlineprotectedinherited |
Definition at line 430 of file max_flow.h.
|
protectedinherited |
Definition at line 535 of file max_flow.cc.
|
protectedinherited |
Definition at line 536 of file max_flow.cc.
|
inlineprotectedinherited |
Definition at line 477 of file max_flow.h.
|
protectedinherited |
Definition at line 534 of file max_flow.cc.
|
inlineinherited |
Definition at line 421 of file max_flow.h.
|
inlineprotectedinherited |
Definition at line 468 of file max_flow.h.
|
protectedinherited |
Definition at line 522 of file max_flow.cc.
|
protectedinherited |
Definition at line 502 of file max_flow.cc.
|
protectedinherited |
Definition at line 486 of file max_flow.cc.
|
protectedinherited |
Definition at line 487 of file max_flow.cc.
|
protectedinherited |
Definition at line 529 of file max_flow.cc.
|
protectedinherited |
Definition at line 517 of file max_flow.cc.
|
inherited |
Definition at line 352 of file max_flow.cc.
|
inherited |
Definition at line 355 of file max_flow.cc.
|
inlineprotectedinherited |
Definition at line 442 of file max_flow.h.
|
inlineinherited |
Definition at line 419 of file max_flow.h.
|
inlineinherited |
Definition at line 420 of file max_flow.h.
|
inlineinherited |
Definition at line 414 of file max_flow.h.
|
inlineinherited |
Definition at line 418 of file max_flow.h.
|
inherited |
Definition at line 358 of file max_flow.cc.
|
inlineinherited |
Definition at line 343 of file max_flow.h.
Definition at line 533 of file max_flow.h.
|
protectedinherited |
Definition at line 597 of file max_flow.h.
|
protectedinherited |
Definition at line 590 of file max_flow.h.
|
protectedinherited |
Definition at line 611 of file max_flow.h.
|
protectedinherited |
Definition at line 634 of file max_flow.h.
|
protectedinherited |
Definition at line 638 of file max_flow.h.
|
protectedinherited |
Definition at line 584 of file max_flow.h.
|
protectedinherited |
Definition at line 547 of file max_flow.h.
|
staticprotectedinherited |
Definition at line 544 of file max_flow.h.
|
protectedinherited |
Definition at line 550 of file max_flow.h.
|
protectedinherited |
Definition at line 610 of file max_flow.h.
|
protectedinherited |
Definition at line 563 of file max_flow.h.
|
protectedinherited |
Definition at line 629 of file max_flow.h.
|
protectedinherited |
Definition at line 581 of file max_flow.h.
|
protectedinherited |
Definition at line 603 of file max_flow.h.
|
protectedinherited |
Definition at line 600 of file max_flow.h.
|
mutableprotectedinherited |
Definition at line 641 of file max_flow.h.
|
protectedinherited |
Definition at line 606 of file max_flow.h.
|
protectedinherited |
Definition at line 614 of file max_flow.h.
|
protectedinherited |
Definition at line 621 of file max_flow.h.