![]() |
OR-Tools
8.2
|
Definition at line 315 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 | |
GenericMaxFlow (const Graph *graph, NodeIndex source, NodeIndex sink) | |
virtual | ~GenericMaxFlow () |
const Graph * | 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 Attributes | |
const Graph * | 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 |
typedef Graph::ArcIndex ArcIndex |
Definition at line 318 of file max_flow.h.
typedef ZVector<ArcIndex> ArcIndexArray |
Definition at line 323 of file max_flow.h.
typedef Graph::IncomingArcIterator IncomingArcIterator |
Definition at line 322 of file max_flow.h.
typedef NodeIndex NodeHeight |
Definition at line 327 of file max_flow.h.
typedef ZVector<NodeHeight> NodeHeightArray |
Definition at line 328 of file max_flow.h.
typedef Graph::NodeIndex NodeIndex |
Definition at line 317 of file max_flow.h.
typedef Graph::OutgoingArcIterator OutgoingArcIterator |
Definition at line 319 of file max_flow.h.
typedef Graph::OutgoingOrOppositeIncomingArcIterator OutgoingOrOppositeIncomingArcIterator |
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.
GenericMaxFlow | ( | const Graph * | graph, |
NodeIndex | source, | ||
NodeIndex | sink | ||
) |
Definition at line 125 of file max_flow.cc.
|
inlinevirtual |
Definition at line 335 of file max_flow.h.
bool AugmentingPathExists |
Definition at line 278 of file max_flow.cc.
|
inline |
Definition at line 375 of file max_flow.h.
bool CheckInputConsistency |
Definition at line 163 of file max_flow.cc.
|
protected |
Definition at line 307 of file max_flow.cc.
bool CheckResult |
Definition at line 236 of file max_flow.cc.
Definition at line 932 of file max_flow.cc.
FlowModel CreateFlowModel |
Definition at line 966 of file max_flow.cc.
|
protected |
Definition at line 318 of file max_flow.cc.
|
protected |
Definition at line 847 of file max_flow.cc.
|
inline |
Definition at line 365 of file max_flow.h.
|
inlineprotected |
Definition at line 460 of file max_flow.h.
|
inline |
Definition at line 361 of file max_flow.h.
|
inline |
Definition at line 349 of file max_flow.h.
void GetSinkSideMinCut | ( | std::vector< NodeIndex > * | result | ) |
Definition at line 231 of file max_flow.cc.
|
inline |
Definition at line 346 of file max_flow.h.
void GetSourceSideMinCut | ( | std::vector< NodeIndex > * | result | ) |
Definition at line 225 of file max_flow.cc.
|
protected |
Definition at line 565 of file max_flow.cc.
|
inline |
Definition at line 338 of file max_flow.h.
Definition at line 532 of file max_flow.h.
|
protected |
Definition at line 740 of file max_flow.cc.
|
protected |
Definition at line 379 of file max_flow.cc.
|
inlineprotected |
Definition at line 437 of file max_flow.h.
|
inlineprotected |
Definition at line 430 of file max_flow.h.
|
protected |
Definition at line 917 of file max_flow.cc.
|
protected |
Definition at line 922 of file max_flow.cc.
|
inlineprotected |
Definition at line 477 of file max_flow.h.
|
protected |
Definition at line 912 of file max_flow.cc.
|
inline |
Definition at line 421 of file max_flow.h.
|
inlineprotected |
Definition at line 468 of file max_flow.h.
|
protected |
Definition at line 718 of file max_flow.cc.
|
protected |
Definition at line 410 of file max_flow.cc.
|
protected |
Definition at line 755 of file max_flow.cc.
|
protected |
Definition at line 794 of file max_flow.cc.
|
protected |
Definition at line 879 of file max_flow.cc.
|
protected |
Definition at line 675 of file max_flow.cc.
void SetArcCapacity | ( | ArcIndex | arc, |
FlowQuantity | new_capacity | ||
) |
Definition at line 175 of file max_flow.cc.
void SetArcFlow | ( | ArcIndex | arc, |
FlowQuantity | new_flow | ||
) |
Definition at line 209 of file max_flow.cc.
|
inlineprotected |
Definition at line 442 of file max_flow.h.
|
inline |
Definition at line 419 of file max_flow.h.
|
inline |
Definition at line 420 of file max_flow.h.
|
inline |
Definition at line 414 of file max_flow.h.
|
inline |
Definition at line 418 of file max_flow.h.
bool Solve |
Definition at line 334 of file max_flow.cc.
|
inline |
Definition at line 343 of file max_flow.h.
Definition at line 533 of file max_flow.h.
|
protected |
Definition at line 597 of file max_flow.h.
|
protected |
Definition at line 590 of file max_flow.h.
|
protected |
Definition at line 611 of file max_flow.h.
|
protected |
Definition at line 634 of file max_flow.h.
|
protected |
Definition at line 638 of file max_flow.h.
|
protected |
Definition at line 584 of file max_flow.h.
|
protected |
Definition at line 547 of file max_flow.h.
|
staticprotected |
Definition at line 544 of file max_flow.h.
|
protected |
Definition at line 550 of file max_flow.h.
|
protected |
Definition at line 610 of file max_flow.h.
|
protected |
Definition at line 563 of file max_flow.h.
|
protected |
Definition at line 629 of file max_flow.h.
|
protected |
Definition at line 581 of file max_flow.h.
|
protected |
Definition at line 603 of file max_flow.h.
|
protected |
Definition at line 600 of file max_flow.h.
|
mutableprotected |
Definition at line 641 of file max_flow.h.
|
protected |
Definition at line 606 of file max_flow.h.
|
protected |
Definition at line 614 of file max_flow.h.
|
protected |
Definition at line 621 of file max_flow.h.