#include <max_flow.h>

Inheritance diagram for operations_research::MaxFlow:

Public Member Functions
	MaxFlow (const StarGraph *graph, NodeIndex source, NodeIndex target)

Public Member Functions inherited from operations_research::GenericMaxFlow< StarGraph >
	GenericMaxFlow (const StarGraph *graph, NodeIndex source, NodeIndex sink)

	GenericMaxFlow (const GenericMaxFlow &)=delete
	This type is neither copyable nor movable.

GenericMaxFlow &	operator= (const GenericMaxFlow &)=delete

virtual	~GenericMaxFlow ()

const StarGraph *	graph () const
	Returns the graph associated to the current object.

Status	status () const

NodeIndex	GetSourceNodeIndex () const
	Returns the index of the node corresponding to the source of the network.

NodeIndex	GetSinkNodeIndex () const
	Returns the index of the node corresponding to the sink of the network.

void	SetArcCapacity (ArcIndex arc, FlowQuantity new_capacity)
	Sets the capacity for arc to new_capacity.

void	SetArcFlow (ArcIndex arc, FlowQuantity new_flow)
	Sets the flow for arc.

bool	Solve ()
	Returns true if a maximum flow was solved.

FlowQuantity	GetOptimalFlow () const
	Returns the total flow found by the algorithm.

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)

FlowModelProto	CreateFlowModel ()
	Returns the protocol buffer representation of the current problem.

Additional Inherited Members
Public Types inherited from operations_research::GenericMaxFlow< StarGraph >
typedef StarGraph::NodeIndex	NodeIndex

typedef StarGraph::ArcIndex	ArcIndex

typedef StarGraph::OutgoingArcIterator	OutgoingArcIterator

typedef StarGraph::OutgoingOrOppositeIncomingArcIterator	OutgoingOrOppositeIncomingArcIterator

typedef StarGraph::IncomingArcIterator	IncomingArcIterator

typedef ZVector< ArcIndex >	ArcIndexArray

typedef NodeIndex	NodeHeight

typedef ZVector< NodeHeight >	NodeHeightArray

Public Types inherited from operations_research::MaxFlowStatusClass
enum	Status { NOT_SOLVED , OPTIMAL , INT_OVERFLOW , BAD_INPUT , BAD_RESULT }

Protected Member Functions inherited from operations_research::GenericMaxFlow< StarGraph >
const FlowQuantity	kMaxFlowQuantity

const FlowQuantity	kMaxFlowQuantity

bool	IsAdmissible (ArcIndex arc) const
	Returns true if arc is admissible.

bool	IsActive (NodeIndex node) const

void	SetCapacityAndClearFlow (ArcIndex arc, FlowQuantity capacity)
	Sets the capacity of arc to 'capacity' and clears the flow on arc.

bool	CheckRelabelPrecondition (NodeIndex node) const

std::string	DebugString (absl::string_view context, ArcIndex arc) const

void	InitializeActiveNodeContainer ()
	Initializes the container active_nodes_.

NodeIndex	GetAndRemoveFirstActiveNode ()
	Get the first element from the active node container.

void	PushActiveNode (const NodeIndex &node)
	Push element to the active node container.

bool	IsEmptyActiveNodeContainer ()
	Check the emptiness of the container.

void	Refine ()
	Performs optimization step.

void	RefineWithGlobalUpdate ()

void	Discharge (NodeIndex node)

void	InitializePreflow ()
	Initializes the preflow to a state that enables to run Refine.

void	PushFlowExcessBackToSource ()

void	GlobalUpdate ()

bool	SaturateOutgoingArcsFromSource ()

void	PushFlow (FlowQuantity flow, ArcIndex arc)

void	Relabel (NodeIndex node)

NodeIndex	Head (ArcIndex arc) const
	Handy member functions to make the code more compact.

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 inherited from operations_research::GenericMaxFlow< StarGraph >
const StarGraph *	graph_
	A pointer to the graph passed as argument.

QuantityArray	node_excess_
	An array representing the excess for each node in graph_.

NodeHeightArray	node_potential_

QuantityArray	residual_arc_capacity_

ArcIndexArray	first_admissible_arc_
	An array representing the first admissible arc for each node in graph_.

std::vector< NodeIndex >	active_nodes_

PriorityQueueWithRestrictedPush< NodeIndex, NodeHeight >	active_node_by_height_

NodeIndex	source_
	The index of the source node in graph_.

NodeIndex	sink_
	The index of the sink node in graph_.

Status	status_
	The status of the problem.

std::vector< bool >	node_in_bfs_queue_

std::vector< NodeIndex >	bfs_queue_

bool	use_global_update_
	Whether or not to use GlobalUpdate().

bool	use_two_phase_algorithm_

bool	process_node_by_height_

bool	check_input_

bool	check_result_

StatsGroup	stats_
	Statistics about this class.

Static Protected Attributes inherited from operations_research::GenericMaxFlow< StarGraph >
static const FlowQuantity	kMaxFlowQuantity
	Maximum manageable flow.

Detailed Description

Default instance MaxFlow that uses StarGraph. Note that we cannot just use a typedef because of dependent code expecting MaxFlow to be a real class.

Todo: (user): Modify this code and remove it.

Definition at line 685 of file max_flow.h.

Constructor & Destructor Documentation

◆ MaxFlow()

operations_research::MaxFlow::MaxFlow	(	const StarGraph *	graph,
		NodeIndex	source,
		NodeIndex	target )

inline

Definition at line 687 of file max_flow.h.

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

ortools/graph/max_flow.h

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ MaxFlow()