GenericMaxFlow< Graph >

Detailed Description

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

Definition at line 144 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
	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.

Constructor & Destructor Documentation

GenericMaxFlow()

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

~GenericMaxFlow()

virtual ~GenericMaxFlow ( )

inlinevirtual

Definition at line 335 of file max_flow.h.

Member Function Documentation

AugmentingPathExists()

bool AugmentingPathExists

(

)

const

Capacity()

FlowQuantity Capacity ( ArcIndex  arc ) const

inline

Definition at line 375 of file max_flow.h.

CheckInputConsistency()

bool CheckInputConsistency

(

)

const

CheckRelabelPrecondition()

bool CheckRelabelPrecondition ( NodeIndex  node ) const

protected

CheckResult()

bool CheckResult

(

)

const

ComputeReachableNodes()

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

protected

CreateFlowModel()

FlowModel CreateFlowModel

(

)

DebugString()

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

protected

Discharge()

void Discharge ( NodeIndex  node )

protected

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

)

GetSourceNodeIndex()

NodeIndex GetSourceNodeIndex ( ) const

inline

Definition at line 346 of file max_flow.h.

GetSourceSideMinCut()

void GetSourceSideMinCut

(

std::vector< NodeIndex > *

result

)

GlobalUpdate()

void GlobalUpdate ( )

protected

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

InitializePreflow()

void InitializePreflow ( )

protected

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

IsArcValid()

bool IsArcValid ( ArcIndex  arc ) const

protected

IsEmptyActiveNodeContainer()

bool IsEmptyActiveNodeContainer ( )

inlineprotected

Definition at line 477 of file max_flow.h.

Opposite()

ArcIndex Opposite ( ArcIndex  arc ) const

protected

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

PushFlowExcessBackToSource()

void PushFlowExcessBackToSource ( )

protected

Refine()

void Refine ( )

protected

RefineWithGlobalUpdate()

void RefineWithGlobalUpdate ( )

protected

Relabel()

void Relabel ( NodeIndex  node )

protected

SaturateOutgoingArcsFromSource()

bool SaturateOutgoingArcsFromSource ( )

protected

SetArcCapacity()

void SetArcCapacity	(	ArcIndex	arc,
		FlowQuantity	new_capacity
	)

SetArcFlow()

void SetArcFlow	(	ArcIndex	arc,
		FlowQuantity	new_flow
	)

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

(

)

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

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

• max_flow.h