OR-Tools  8.2
Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | Static Protected Attributes | List of all members
GenericMaxFlow< Graph >

Detailed Description

template<typename Graph>
class operations_research::GenericMaxFlow< Graph >

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 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
 
template<bool reverse>
void ComputeReachableNodes (NodeIndex start, std::vector< NodeIndex > *result)
 

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
 

Member Typedef Documentation

◆ ArcIndex

typedef Graph::ArcIndex ArcIndex

Definition at line 318 of file max_flow.h.

◆ ArcIndexArray

typedef ZVector<ArcIndex> ArcIndexArray

Definition at line 323 of file max_flow.h.

◆ IncomingArcIterator

typedef Graph::IncomingArcIterator IncomingArcIterator

Definition at line 322 of file max_flow.h.

◆ NodeHeight

typedef NodeIndex NodeHeight

Definition at line 327 of file max_flow.h.

◆ NodeHeightArray

typedef ZVector<NodeHeight> NodeHeightArray

Definition at line 328 of file max_flow.h.

◆ NodeIndex

typedef Graph::NodeIndex NodeIndex

Definition at line 317 of file max_flow.h.

◆ OutgoingArcIterator

typedef Graph::OutgoingArcIterator OutgoingArcIterator

Definition at line 319 of file max_flow.h.

◆ OutgoingOrOppositeIncomingArcIterator

typedef Graph::OutgoingOrOppositeIncomingArcIterator OutgoingOrOppositeIncomingArcIterator

Definition at line 321 of file max_flow.h.

Member Enumeration Documentation

◆ Status

enum Status
inherited
Enumerator
NOT_SOLVED 
OPTIMAL 
INT_OVERFLOW 
BAD_INPUT 
BAD_RESULT 

Definition at line 302 of file max_flow.h.

Constructor & Destructor Documentation

◆ GenericMaxFlow()

GenericMaxFlow ( const Graph *  graph,
NodeIndex  source,
NodeIndex  sink 
)

Definition at line 125 of file max_flow.cc.

◆ ~GenericMaxFlow()

virtual ~GenericMaxFlow ( )
inlinevirtual

Definition at line 335 of file max_flow.h.

Member Function Documentation

◆ AugmentingPathExists()

bool AugmentingPathExists

Definition at line 278 of file max_flow.cc.

◆ Capacity()

FlowQuantity Capacity ( ArcIndex  arc) const
inline

Definition at line 375 of file max_flow.h.

◆ CheckInputConsistency()

bool CheckInputConsistency

Definition at line 163 of file max_flow.cc.

◆ CheckRelabelPrecondition()

bool CheckRelabelPrecondition ( NodeIndex  node) const
protected

Definition at line 307 of file max_flow.cc.

◆ CheckResult()

bool CheckResult

Definition at line 236 of file max_flow.cc.

◆ ComputeReachableNodes()

void ComputeReachableNodes ( NodeIndex  start,
std::vector< NodeIndex > *  result 
)
protected

Definition at line 932 of file max_flow.cc.

◆ CreateFlowModel()

FlowModel CreateFlowModel

Definition at line 966 of file max_flow.cc.

◆ DebugString()

std::string DebugString ( const std::string &  context,
ArcIndex  arc 
) const
protected

Definition at line 318 of file max_flow.cc.

◆ Discharge()

void Discharge ( NodeIndex  node)
protected

Definition at line 847 of file max_flow.cc.

◆ Flow()

FlowQuantity Flow ( ArcIndex  arc) const
inline

Definition at line 365 of file max_flow.h.

◆ GetAndRemoveFirstActiveNode()

NodeIndex GetAndRemoveFirstActiveNode ( )
inlineprotected

Definition at line 460 of file max_flow.h.

◆ GetOptimalFlow()

FlowQuantity GetOptimalFlow ( ) const
inline

Definition at line 361 of file max_flow.h.

◆ GetSinkNodeIndex()

NodeIndex GetSinkNodeIndex ( ) const
inline

Definition at line 349 of file max_flow.h.

◆ GetSinkSideMinCut()

void GetSinkSideMinCut ( std::vector< NodeIndex > *  result)

Definition at line 231 of file max_flow.cc.

◆ GetSourceNodeIndex()

NodeIndex GetSourceNodeIndex ( ) const
inline

Definition at line 346 of file max_flow.h.

◆ GetSourceSideMinCut()

void GetSourceSideMinCut ( std::vector< NodeIndex > *  result)

Definition at line 225 of file max_flow.cc.

◆ GlobalUpdate()

void GlobalUpdate
protected

Definition at line 565 of file max_flow.cc.

◆ graph()

const Graph * graph ( ) const
inline

Definition at line 338 of file max_flow.h.

◆ Head()

NodeIndex Head ( ArcIndex  arc) const
inlineprotected

Definition at line 532 of file max_flow.h.

◆ InitializeActiveNodeContainer()

void InitializeActiveNodeContainer
protected

Definition at line 740 of file max_flow.cc.

◆ InitializePreflow()

void InitializePreflow
protected

Definition at line 379 of file max_flow.cc.

◆ IsActive()

bool IsActive ( NodeIndex  node) const
inlineprotected

Definition at line 437 of file max_flow.h.

◆ IsAdmissible()

bool IsAdmissible ( ArcIndex  arc) const
inlineprotected

Definition at line 430 of file max_flow.h.

◆ IsArcDirect()

bool IsArcDirect ( ArcIndex  arc) const
protected

Definition at line 917 of file max_flow.cc.

◆ IsArcValid()

bool IsArcValid ( ArcIndex  arc) const
protected

Definition at line 922 of file max_flow.cc.

◆ IsEmptyActiveNodeContainer()

bool IsEmptyActiveNodeContainer ( )
inlineprotected

Definition at line 477 of file max_flow.h.

◆ Opposite()

Graph::ArcIndex Opposite ( ArcIndex  arc) const
protected

Definition at line 912 of file max_flow.cc.

◆ ProcessNodeByHeight()

void ProcessNodeByHeight ( bool  value)
inline

Definition at line 421 of file max_flow.h.

◆ PushActiveNode()

void PushActiveNode ( const NodeIndex &  node)
inlineprotected

Definition at line 468 of file max_flow.h.

◆ PushFlow()

void PushFlow ( FlowQuantity  flow,
ArcIndex  arc 
)
protected

Definition at line 718 of file max_flow.cc.

◆ PushFlowExcessBackToSource()

void PushFlowExcessBackToSource
protected

Definition at line 410 of file max_flow.cc.

◆ Refine()

void Refine
protected

Definition at line 755 of file max_flow.cc.

◆ RefineWithGlobalUpdate()

void RefineWithGlobalUpdate
protected

Definition at line 794 of file max_flow.cc.

◆ Relabel()

void Relabel ( NodeIndex  node)
protected

Definition at line 879 of file max_flow.cc.

◆ SaturateOutgoingArcsFromSource()

bool SaturateOutgoingArcsFromSource
protected

Definition at line 675 of file max_flow.cc.

◆ SetArcCapacity()

void SetArcCapacity ( ArcIndex  arc,
FlowQuantity  new_capacity 
)

Definition at line 175 of file max_flow.cc.

◆ SetArcFlow()

void SetArcFlow ( ArcIndex  arc,
FlowQuantity  new_flow 
)

Definition at line 209 of file max_flow.cc.

◆ SetCapacityAndClearFlow()

void SetCapacityAndClearFlow ( ArcIndex  arc,
FlowQuantity  capacity 
)
inlineprotected

Definition at line 442 of file max_flow.h.

◆ SetCheckInput()

void SetCheckInput ( bool  value)
inline

Definition at line 419 of file max_flow.h.

◆ SetCheckResult()

void SetCheckResult ( bool  value)
inline

Definition at line 420 of file max_flow.h.

◆ SetUseGlobalUpdate()

void SetUseGlobalUpdate ( bool  value)
inline

Definition at line 414 of file max_flow.h.

◆ SetUseTwoPhaseAlgorithm()

void SetUseTwoPhaseAlgorithm ( bool  value)
inline

Definition at line 418 of file max_flow.h.

◆ Solve()

bool Solve

Definition at line 334 of file max_flow.cc.

◆ status()

Status status ( ) const
inline

Definition at line 343 of file max_flow.h.

◆ Tail()

NodeIndex Tail ( ArcIndex  arc) const
inlineprotected

Definition at line 533 of file max_flow.h.

Member Data Documentation

◆ active_node_by_height_

PriorityQueueWithRestrictedPush<NodeIndex, NodeHeight> active_node_by_height_
protected

Definition at line 597 of file max_flow.h.

◆ active_nodes_

std::vector<NodeIndex> active_nodes_
protected

Definition at line 590 of file max_flow.h.

◆ bfs_queue_

std::vector<NodeIndex> bfs_queue_
protected

Definition at line 611 of file max_flow.h.

◆ check_input_

bool check_input_
protected

Definition at line 634 of file max_flow.h.

◆ check_result_

bool check_result_
protected

Definition at line 638 of file max_flow.h.

◆ first_admissible_arc_

ArcIndexArray first_admissible_arc_
protected

Definition at line 584 of file max_flow.h.

◆ graph_

const Graph* graph_
protected

Definition at line 547 of file max_flow.h.

◆ kMaxFlowQuantity

const FlowQuantity kMaxFlowQuantity
staticprotected
Initial value:
=
std::numeric_limits<FlowQuantity>::max()
max
int64 max
Definition: alldiff_cst.cc:139

Definition at line 544 of file max_flow.h.

◆ node_excess_

QuantityArray node_excess_
protected

Definition at line 550 of file max_flow.h.

◆ node_in_bfs_queue_

std::vector<bool> node_in_bfs_queue_
protected

Definition at line 610 of file max_flow.h.

◆ node_potential_

NodeHeightArray node_potential_
protected

Definition at line 563 of file max_flow.h.

◆ process_node_by_height_

bool process_node_by_height_
protected

Definition at line 629 of file max_flow.h.

◆ residual_arc_capacity_

QuantityArray residual_arc_capacity_
protected

Definition at line 581 of file max_flow.h.

◆ sink_

NodeIndex sink_
protected

Definition at line 603 of file max_flow.h.

◆ source_

NodeIndex source_
protected

Definition at line 600 of file max_flow.h.

◆ stats_

StatsGroup stats_
mutableprotected

Definition at line 641 of file max_flow.h.

◆ status_

Status status_
protected

Definition at line 606 of file max_flow.h.

◆ use_global_update_

bool use_global_update_
protected

Definition at line 614 of file max_flow.h.

◆ use_two_phase_algorithm_

bool use_two_phase_algorithm_
protected

Definition at line 621 of file max_flow.h.

The documentation for this class was generated from the following files: