C++ Reference

C++ Reference: Graph

Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | Static Protected Attributes | List of all members
MaxFlow

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

typedef Graph::ArcIndex ArcIndex
inherited

Definition at line 318 of file max_flow.h.

◆ ArcIndexArray

typedef ZVector<ArcIndex> ArcIndexArray
inherited

Definition at line 323 of file max_flow.h.

◆ IncomingArcIterator

typedef Graph::IncomingArcIterator IncomingArcIterator
inherited

Definition at line 322 of file max_flow.h.

◆ NodeHeight

typedef NodeIndex NodeHeight
inherited

Definition at line 327 of file max_flow.h.

◆ NodeHeightArray

typedef ZVector<NodeHeight> NodeHeightArray
inherited

Definition at line 328 of file max_flow.h.

◆ NodeIndex

typedef Graph::NodeIndex NodeIndex
inherited

Definition at line 317 of file max_flow.h.

◆ OutgoingArcIterator

typedef Graph::OutgoingArcIterator OutgoingArcIterator
inherited

Definition at line 319 of file max_flow.h.

◆ OutgoingOrOppositeIncomingArcIterator

typedef Graph::OutgoingOrOppositeIncomingArcIterator OutgoingOrOppositeIncomingArcIterator
inherited

Definition at line 321 of file max_flow.h.

Constructor & Destructor Documentation

◆ MaxFlow()

MaxFlow ( const StarGraph *  graph,
NodeIndex  source,
NodeIndex  target 
)
inline

Definition at line 654 of file max_flow.h.

Member Function Documentation

◆ AugmentingPathExists()

bool AugmentingPathExists
inherited

◆ Capacity()

FlowQuantity Capacity ( ArcIndex  arc) const
inlineinherited

Definition at line 375 of file max_flow.h.

◆ CheckInputConsistency()

bool CheckInputConsistency
inherited

◆ CheckRelabelPrecondition()

bool CheckRelabelPrecondition ( NodeIndex  node) const
protectedinherited

◆ CheckResult()

bool CheckResult
inherited

◆ ComputeReachableNodes()

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

◆ CreateFlowModel()

FlowModel CreateFlowModel
inherited

◆ DebugString()

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

◆ Discharge()

void Discharge ( NodeIndex  node)
protectedinherited

◆ Flow()

FlowQuantity Flow ( ArcIndex  arc) const
inlineinherited

Definition at line 365 of file max_flow.h.

◆ GetAndRemoveFirstActiveNode()

NodeIndex GetAndRemoveFirstActiveNode
inlineprotectedinherited

Definition at line 460 of file max_flow.h.

◆ GetOptimalFlow()

FlowQuantity GetOptimalFlow
inlineinherited

Definition at line 361 of file max_flow.h.

◆ GetSinkNodeIndex()

NodeIndex GetSinkNodeIndex
inlineinherited

Definition at line 349 of file max_flow.h.

◆ GetSinkSideMinCut()

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

◆ GetSourceNodeIndex()

NodeIndex GetSourceNodeIndex
inlineinherited

Definition at line 346 of file max_flow.h.

◆ GetSourceSideMinCut()

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

◆ GlobalUpdate()

void GlobalUpdate
protectedinherited

◆ graph()

const StarGraph * graph
inlineinherited

Definition at line 338 of file max_flow.h.

◆ Head()

NodeIndex Head ( ArcIndex  arc) const
inlineprotectedinherited

Definition at line 532 of file max_flow.h.

◆ InitializeActiveNodeContainer()

void InitializeActiveNodeContainer
protectedinherited

◆ InitializePreflow()

void InitializePreflow
protectedinherited

◆ IsActive()

bool IsActive ( NodeIndex  node) const
inlineprotectedinherited

Definition at line 437 of file max_flow.h.

◆ IsAdmissible()

bool IsAdmissible ( ArcIndex  arc) const
inlineprotectedinherited

Definition at line 430 of file max_flow.h.

◆ IsArcDirect()

bool IsArcDirect ( ArcIndex  arc) const
protectedinherited

◆ IsArcValid()

bool IsArcValid ( ArcIndex  arc) const
protectedinherited

◆ IsEmptyActiveNodeContainer()

bool IsEmptyActiveNodeContainer
inlineprotectedinherited

Definition at line 477 of file max_flow.h.

◆ Opposite()

ArcIndex Opposite ( ArcIndex  arc) const
protectedinherited

◆ ProcessNodeByHeight()

void ProcessNodeByHeight ( bool  value)
inlineinherited

Definition at line 421 of file max_flow.h.

◆ PushActiveNode()

void PushActiveNode ( const NodeIndex &  node)
inlineprotectedinherited

Definition at line 468 of file max_flow.h.

◆ PushFlow()

void PushFlow ( FlowQuantity  flow,
ArcIndex  arc 
)
protectedinherited

◆ PushFlowExcessBackToSource()

void PushFlowExcessBackToSource
protectedinherited

◆ Refine()

void Refine
protectedinherited

◆ RefineWithGlobalUpdate()

void RefineWithGlobalUpdate
protectedinherited

◆ Relabel()

void Relabel ( NodeIndex  node)
protectedinherited

◆ SaturateOutgoingArcsFromSource()

bool SaturateOutgoingArcsFromSource
protectedinherited

◆ SetArcCapacity()

void SetArcCapacity ( ArcIndex  arc,
FlowQuantity  new_capacity 
)
inherited

◆ SetArcFlow()

void SetArcFlow ( ArcIndex  arc,
FlowQuantity  new_flow 
)
inherited

◆ SetCapacityAndClearFlow()

void SetCapacityAndClearFlow ( ArcIndex  arc,
FlowQuantity  capacity 
)
inlineprotectedinherited

Definition at line 442 of file max_flow.h.

◆ SetCheckInput()

void SetCheckInput ( bool  value)
inlineinherited

Definition at line 419 of file max_flow.h.

◆ SetCheckResult()

void SetCheckResult ( bool  value)
inlineinherited

Definition at line 420 of file max_flow.h.

◆ SetUseGlobalUpdate()

void SetUseGlobalUpdate ( bool  value)
inlineinherited

Definition at line 414 of file max_flow.h.

◆ SetUseTwoPhaseAlgorithm()

void SetUseTwoPhaseAlgorithm ( bool  value)
inlineinherited

Definition at line 418 of file max_flow.h.

◆ Solve()

bool Solve
inherited

◆ status()

Status status
inlineinherited

Definition at line 343 of file max_flow.h.

◆ Tail()

NodeIndex Tail ( ArcIndex  arc) const
inlineprotectedinherited

Definition at line 533 of file max_flow.h.

Member Data Documentation

◆ active_node_by_height_

PriorityQueueWithRestrictedPush<NodeIndex, NodeHeight> active_node_by_height_
protectedinherited

Definition at line 597 of file max_flow.h.

◆ active_nodes_

std::vector<NodeIndex> active_nodes_
protectedinherited

Definition at line 590 of file max_flow.h.

◆ bfs_queue_

std::vector<NodeIndex> bfs_queue_
protectedinherited

Definition at line 611 of file max_flow.h.

◆ check_input_

bool check_input_
protectedinherited

Definition at line 634 of file max_flow.h.

◆ check_result_

bool check_result_
protectedinherited

Definition at line 638 of file max_flow.h.

◆ first_admissible_arc_

ArcIndexArray first_admissible_arc_
protectedinherited

Definition at line 584 of file max_flow.h.

◆ graph_

const StarGraph * graph_
protectedinherited

Definition at line 547 of file max_flow.h.

◆ kMaxFlowQuantity

const FlowQuantity kMaxFlowQuantity
staticprotectedinherited

Definition at line 544 of file max_flow.h.

◆ node_excess_

QuantityArray node_excess_
protectedinherited

Definition at line 550 of file max_flow.h.

◆ node_in_bfs_queue_

std::vector<bool> node_in_bfs_queue_
protectedinherited

Definition at line 610 of file max_flow.h.

◆ node_potential_

NodeHeightArray node_potential_
protectedinherited

Definition at line 563 of file max_flow.h.

◆ process_node_by_height_

bool process_node_by_height_
protectedinherited

Definition at line 629 of file max_flow.h.

◆ residual_arc_capacity_

QuantityArray residual_arc_capacity_
protectedinherited

Definition at line 581 of file max_flow.h.

◆ sink_

NodeIndex sink_
protectedinherited

Definition at line 603 of file max_flow.h.

◆ source_

NodeIndex source_
protectedinherited

Definition at line 600 of file max_flow.h.

◆ stats_

StatsGroup stats_
mutableprotectedinherited

Definition at line 641 of file max_flow.h.

◆ status_

Status status_
protectedinherited

Definition at line 606 of file max_flow.h.

◆ use_global_update_

bool use_global_update_
protectedinherited

Definition at line 614 of file max_flow.h.

◆ use_two_phase_algorithm_

bool 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: