Forward declaration. More...

#include <max_flow.h>

Inheritance diagram for operations_research::GenericMaxFlow< Graph >:

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 Types inherited from operations_research::MaxFlowStatusClass
enum	Status { NOT_SOLVED , OPTIMAL , INT_OVERFLOW , BAD_INPUT , BAD_RESULT }

Public Member Functions
	GenericMaxFlow (const Graph *graph, NodeIndex source, NodeIndex sink)

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

GenericMaxFlow &	operator= (const GenericMaxFlow &)=delete

virtual	~GenericMaxFlow ()

const Graph *	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.

Protected Member Functions
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

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

const FlowQuantity	kMaxFlowQuantity

const FlowQuantity	kMaxFlowQuantity

Protected Attributes
const Graph *	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
static const FlowQuantity	kMaxFlowQuantity
	Maximum manageable flow.

Detailed Description

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

Forward declaration.

Generic MaxFlow (there is a default MaxFlow specialization defined below) that works with StarGraph and all the reverse arc graphs from graph.h, see the end of max_flow.cc for the exact types this class is compiled for.

Definition at line 324 of file max_flow.h.

Member Typedef Documentation

◆ ArcIndex

template<typename Graph >

Graph::ArcIndex operations_research::GenericMaxFlow< Graph >::ArcIndex

Definition at line 327 of file max_flow.h.

◆ ArcIndexArray

template<typename Graph >

ZVector<ArcIndex> operations_research::GenericMaxFlow< Graph >::ArcIndexArray

Definition at line 332 of file max_flow.h.

◆ IncomingArcIterator

template<typename Graph >

Graph::IncomingArcIterator operations_research::GenericMaxFlow< Graph >::IncomingArcIterator

Definition at line 331 of file max_flow.h.

◆ NodeHeight

template<typename Graph >

NodeIndex operations_research::GenericMaxFlow< Graph >::NodeHeight

The height of a node never excess 2 times the number of node, so we use the same type as a Node index.

Definition at line 336 of file max_flow.h.

◆ NodeHeightArray

template<typename Graph >

ZVector<NodeHeight> operations_research::GenericMaxFlow< Graph >::NodeHeightArray

Definition at line 337 of file max_flow.h.

◆ NodeIndex

template<typename Graph >

Graph::NodeIndex operations_research::GenericMaxFlow< Graph >::NodeIndex

Definition at line 326 of file max_flow.h.

◆ OutgoingArcIterator

template<typename Graph >

Graph::OutgoingArcIterator operations_research::GenericMaxFlow< Graph >::OutgoingArcIterator

Definition at line 328 of file max_flow.h.

◆ OutgoingOrOppositeIncomingArcIterator

template<typename Graph >

Graph::OutgoingOrOppositeIncomingArcIterator operations_research::GenericMaxFlow< Graph >::OutgoingOrOppositeIncomingArcIterator

Definition at line 330 of file max_flow.h.

Constructor & Destructor Documentation

◆ GenericMaxFlow() [1/2]

template<typename Graph >

operations_research::GenericMaxFlow< Graph >::GenericMaxFlow	(	const Graph *	graph,
		NodeIndex	source,
		NodeIndex	sink )

Initialize a MaxFlow instance on the given graph. The graph does not need to be fully built yet, but its capacity reservation are used to initialize the memory of this class. source and sink must also be valid node of graph.

Definition at line 144 of file max_flow.cc.

◆ GenericMaxFlow() [2/2]

template<typename Graph >

operations_research::GenericMaxFlow< Graph >::GenericMaxFlow ( const GenericMaxFlow< Graph > & )

delete

This type is neither copyable nor movable.

◆ ~GenericMaxFlow()

template<typename Graph >

virtual operations_research::GenericMaxFlow< Graph >::~GenericMaxFlow ( )

inlinevirtual

Definition at line 351 of file max_flow.h.

Member Function Documentation

◆ AugmentingPathExists()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::AugmentingPathExists ( ) const

Returns true if there exists a path from the source to the sink with remaining capacity. This allows us to easily check at the end that the flow we computed is indeed optimal (provided that all the conditions tested by CheckResult() also hold).

We simply compute the reachability from the source in the residual graph.

Definition at line 297 of file max_flow.cc.

◆ Capacity()

template<typename Graph >

FlowQuantity operations_research::GenericMaxFlow< Graph >::Capacity ( ArcIndex arc ) const

inline

Returns the capacity of arc using the equations given in the comment on residual_arc_capacity_.

Definition at line 391 of file max_flow.h.

◆ CheckInputConsistency()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::CheckInputConsistency ( ) const

Checks the consistency of the input, i.e. that capacities on the arcs are non-negative or null.

Definition at line 182 of file max_flow.cc.

◆ CheckRelabelPrecondition()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::CheckRelabelPrecondition ( NodeIndex node ) const

protected

Returns true if a precondition for Relabel is met, i.e. the outgoing arcs of node are all either saturated or the heights of their heads are greater or equal to the height of node.

Definition at line 326 of file max_flow.cc.

◆ CheckResult()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::CheckResult ( ) const

Checks whether the result is valid, i.e. that node excesses are all equal to zero (we have a flow) and that residual capacities are all non-negative or zero.

The initial capacity of the direct arcs is non-negative.

Definition at line 255 of file max_flow.cc.

◆ ComputeReachableNodes()

template<typename Graph >

template<bool reverse>

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

protected

Returns the set of nodes reachable from start in the residual graph or in the reverse residual graph (if reverse is true).

If start is not a valid node index, it can reach only itself. Note(user): This is needed because source and sink are given independently of the graph and sometimes before it is even constructed.

Definition at line 951 of file max_flow.cc.

◆ CreateFlowModel()

template<typename Graph >

FlowModelProto operations_research::GenericMaxFlow< Graph >::CreateFlowModel ( )

Returns the protocol buffer representation of the current problem.

Definition at line 985 of file max_flow.cc.

◆ DebugString()

template<typename Graph >

std::string operations_research::GenericMaxFlow< Graph >::DebugString	(	absl::string_view	context,
		ArcIndex	arc ) const

protected

Returns context concatenated with information about arc in a human-friendly way.

Definition at line 337 of file max_flow.cc.

◆ Discharge()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::Discharge ( NodeIndex node )

protected

Discharges an active node node by saturating its admissible adjacent arcs, if any, and by relabelling it when it becomes inactive.

The push below will make the node active for sure. Note that we may push the sink_, but that is handled properly in Refine().

Definition at line 866 of file max_flow.cc.

◆ Flow()

template<typename Graph >

FlowQuantity operations_research::GenericMaxFlow< Graph >::Flow ( ArcIndex arc ) const

inline

Returns the flow on arc using the equations given in the comment on residual_arc_capacity_.

Definition at line 381 of file max_flow.h.

◆ GetAndRemoveFirstActiveNode()

template<typename Graph >

NodeIndex operations_research::GenericMaxFlow< Graph >::GetAndRemoveFirstActiveNode ( )

inlineprotected

Get the first element from the active node container.

Definition at line 476 of file max_flow.h.

◆ GetOptimalFlow()

template<typename Graph >

FlowQuantity operations_research::GenericMaxFlow< Graph >::GetOptimalFlow ( ) const

inline

Returns the total flow found by the algorithm.

Definition at line 377 of file max_flow.h.

◆ GetSinkNodeIndex()

template<typename Graph >

NodeIndex operations_research::GenericMaxFlow< Graph >::GetSinkNodeIndex ( ) const

inline

Returns the index of the node corresponding to the sink of the network.

Definition at line 365 of file max_flow.h.

◆ GetSinkSideMinCut()

template<typename Graph >

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

Returns the nodes that can reach the sink in the residual graph, the outgoing arcs of this set form a minimum cut. Note that if this is the complement of GetNodeReachableFromSource(), then the min-cut is unique.

Todo: (user): In the two-phases algorithm, we can get this minimum cut without doing the second phase. Add an option for this if there is a need to, note that the second phase is pretty fast so the gain will be small.

Definition at line 250 of file max_flow.cc.

◆ GetSourceNodeIndex()

template<typename Graph >

NodeIndex operations_research::GenericMaxFlow< Graph >::GetSourceNodeIndex ( ) const

inline

Returns the index of the node corresponding to the source of the network.

Definition at line 362 of file max_flow.h.

◆ GetSourceSideMinCut()

template<typename Graph >

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

Returns the nodes reachable from the source in the residual graph, the outgoing arcs of this set form a minimum cut.

Definition at line 244 of file max_flow.cc.

◆ GlobalUpdate()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::GlobalUpdate ( )

protected

Computes the best possible node potential given the current flow using a reverse breadth-first search from the sink in the reverse residual graph. This is an implementation of the global update heuristic mentioned in many max-flow papers. See for instance: B.V. Cherkassky, A.V. Goldberg, "On implementing push-relabel methods for the maximum flow problem", Algorithmica, 19:390-410, 1997. ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/94/1523/CS-TR-94-1523.pdf

We do two BFS in the reverse residual graph, one from the sink and one from the source. Because all the arcs from the source are saturated (except in presence of integer overflow), the source cannot reach the sink in the residual graph. However, we still want to relabel all the nodes that cannot reach the sink but can reach the source (because if they have excess, we need to push it back to the source).

Note: the second pass is not needed here if we use a two-pass algorithm to return the flow to the source after we found the min cut.

Skip the arc if the height of head was already set to the correct value (Remember we are doing reverse BFS).

Todo

(user): By using more memory we can speed this up quite a bit by avoiding to take the opposite arc here, too options:

if (residual_arc_capacity_[arc] != arc_capacity_[arc])
if (opposite_arc_is_admissible_[arc]) ///< need updates. Experiment with the first option shows more than 10% gain on this function running time, which is the bottleneck on many instances.

Note(user): We used to have a DCHECK_GE(candidate_distance, node_potential_[head]); which is always true except in the case where we can push more than kMaxFlowQuantity out of the source. The problem comes from the fact that in this case, we call PushFlowExcessBackToSource() in the middle of the algorithm. The later call will break the properties of the node potential. Note however, that this function will recompute a good node potential for all the nodes and thus fix the issue.

If head is active, we can steal some or all of its excess. This brings a huge gain on some problems. Note(user): I haven't seen this anywhere in the literature.

Todo: (user): Investigate more and maybe write a publication :)

If the arc became saturated, it is no longer in the residual graph, so we do not need to consider head at this time.

Note: there is no need to touch first_admissible_arc_[node] because of the relaxed Relabel() we use.

At the end of the search, some nodes may not be in the bfs_queue_. Such nodes cannot reach the sink_ or source_ in the residual graph, so there is no point trying to push flow toward them. We obtain this effect by setting their height to something unreachable.

Note: this also prevents cycling due to our anti-overflow procedure. For instance, suppose there is an edge s -> n outgoing from the source. If node n has no other connection and some excess, we will push the flow back to the source, but if we don't update the height of n SaturateOutgoingArcsFromSource() will push the flow to n again.

Todo: (user): This is another argument for another anti-overflow algorithm.

Reset the active nodes. Doing it like this pushes the nodes in increasing order of height. Note that bfs_queue_[0] is the sink_ so we skip it.

Definition at line 584 of file max_flow.cc.

◆ graph()

template<typename Graph >

const Graph * operations_research::GenericMaxFlow< Graph >::graph ( ) const

inline

Returns the graph associated to the current object.

Definition at line 354 of file max_flow.h.

◆ Head()

template<typename Graph >

NodeIndex operations_research::GenericMaxFlow< Graph >::Head ( ArcIndex arc ) const

inlineprotected

Handy member functions to make the code more compact.

Definition at line 548 of file max_flow.h.

◆ InitializeActiveNodeContainer()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::InitializeActiveNodeContainer ( )

protected

Initializes the container active_nodes_.

Definition at line 759 of file max_flow.cc.

◆ InitializePreflow()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::InitializePreflow ( )

protected

Initializes the preflow to a state that enables to run Refine.

InitializePreflow() clears the whole flow that could have been computed by a previous Solve(). This is not optimal in terms of complexity.

Todo: (user): find a way to make the re-solving incremental (not an obvious task, and there has not been a lot of literature on the subject.)

All the initial heights are zero except for the source whose height is equal to the number of nodes and will never change during the algorithm.

Initially no arcs are admissible except maybe the one leaving the source, but we treat the source in a special way, see SaturateOutgoingArcsFromSource().

Definition at line 398 of file max_flow.cc.

◆ IsActive()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::IsActive ( NodeIndex node ) const

inlineprotected

Returns true if node is active, i.e. if its excess is positive and it is neither the source or the sink of the graph.

Definition at line 453 of file max_flow.h.

◆ IsAdmissible()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::IsAdmissible ( ArcIndex arc ) const

inlineprotected

Returns true if arc is admissible.

Definition at line 446 of file max_flow.h.

◆ IsArcDirect()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::IsArcDirect ( ArcIndex arc ) const

protected

Definition at line 936 of file max_flow.cc.

◆ IsArcValid()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::IsArcValid ( ArcIndex arc ) const

protected

Definition at line 941 of file max_flow.cc.

◆ IsEmptyActiveNodeContainer()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::IsEmptyActiveNodeContainer ( )

inlineprotected

Check the emptiness of the container.

Definition at line 493 of file max_flow.h.

◆ kMaxFlowQuantity() [1/2]

const FlowQuantity operations_research::GenericMaxFlow< StarGraph >::kMaxFlowQuantity

protected

Explicit instantiations that can be used by a client.

Todo: (user): moves this code out of a .cc file and include it at the end of the header so it can work with any graph implementation ?

Definition at line 1008 of file max_flow.cc.

◆ kMaxFlowQuantity() [2/2]

const FlowQuantity operations_research::GenericMaxFlow< StarGraph >::kMaxFlowQuantity

protected

Note: SWIG does not seem to understand explicit template specialization and instantiation declarations.

Definition at line 666 of file max_flow.h.

◆ operator=()

template<typename Graph >

GenericMaxFlow & operations_research::GenericMaxFlow< Graph >::operator= ( const GenericMaxFlow< Graph > & )

delete

◆ Opposite()

template<typename Graph >

Graph::ArcIndex operations_research::GenericMaxFlow< Graph >::Opposite ( ArcIndex arc ) const

protected

Definition at line 931 of file max_flow.cc.

◆ ProcessNodeByHeight()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::ProcessNodeByHeight ( bool value )

inline

Definition at line 437 of file max_flow.h.

◆ PushActiveNode()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::PushActiveNode ( const NodeIndex & node )

inlineprotected

Push element to the active node container.

Definition at line 484 of file max_flow.h.

◆ PushFlow()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::PushFlow	(	FlowQuantity	flow,
		ArcIndex	arc )

protected

Pushes flow on arc, i.e. consumes flow on residual_arc_capacity_[arc], and consumes -flow on residual_arc_capacity_[Opposite(arc)]. Updates node_excess_ at the tail and head of arc accordingly.

Todo: (user): Do not allow a zero flow after fixing the UniformMaxFlow code.

node_excess_ should be always greater than or equal to 0 except for the source where it should always be smaller than or equal to 0. Note however that we cannot check this because when we cancel the flow on a cycle in PushFlowExcessBackToSource(), we may break this invariant during the operation even if it is still valid at the end.

Update the residual capacity of the arc and its opposite arc.

Update the excesses at the tail and head of the arc.

Definition at line 737 of file max_flow.cc.

◆ PushFlowExcessBackToSource()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::PushFlowExcessBackToSource ( )

protected

Clears the flow excess at each node by pushing the flow back to the source:

Do a depth-first search from the source in the direct graph to cancel flow cycles.
Then, return flow excess along the depth-first search tree (by pushing the flow in the reverse dfs topological order). The theoretical complexity is O(mn), but it is a lot faster in practice.

Note(user): Calling this function will break the property on the node potentials because of the way we cancel flow on cycle. However, we only call that at the end of the algorithm, or just before a GlobalUpdate() that will restore the precondition on the node potentials.

We implement a variation of Tarjan's strongly connected component algorithm to detect cycles published in: Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing. A description can also be found in wikipedia.

Stored nodes are settled nodes already stored in the reverse_topological_order (except the sink_ that we do not actually store).

The visited nodes that are not yet stored are all the nodes from the source_ to the current node in the current dfs branch.

Stack of arcs to explore in the dfs search. The current node is Head(arc_stack.back()).

Increasing list of indices into the arc_stack that correspond to the list of arcs in the current dfs branch from the source_ to the current node.

Node in reverse_topological_order in the final dfs tree.

We start by pushing all the outgoing arcs from the source on the stack to avoid special conditions in the code. As a result, source_ will not be stored in reverse_topological_order, and this is what we want.

Start the dfs on the subgraph formed by the direct arcs with positive flow.

If the node is visited, it means we have explored all its arcs and we have just backtracked in the dfs. Store it if it is not already stored and process the next arc on the stack.

The node is a new unexplored node, add all its outgoing arcs with positive flow to the stack and go deeper in the dfs.

There is a cycle. Find the first index to consider, arc_stack[index_branch[cycle_begin]] will be the first arc on the cycle.

Compute the maximum flow that can be canceled on the cycle and the min index such that arc_stack[index_branch[i]] will be saturated.

This is just here for a DCHECK() below.

Cancel the flow on the cycle, and set visited[node] = false for the node that will be backtracked over.

This is a simple check that the flow was pushed properly.

Backtrack the dfs just before index_branch[first_saturated_index]. If the current node is still active, there is nothing to do.

We backtracked over the current node, so there is no need to continue looping over its arcs.

Return the flow to the sink. Note that the sink_ and the source_ are not stored in reverse_topological_order.

Definition at line 429 of file max_flow.cc.

◆ Refine()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::Refine ( )

protected

Performs optimization step.

Usually SaturateOutgoingArcsFromSource() will saturate all the arcs from the source in one go, and we will loop just once. But in case we can push more than kMaxFlowQuantity out of the source the loop is as follow:

Push up to kMaxFlowQuantity out of the source on the admissible outgoing arcs. Stop if no flow was pushed.
Compute the current max-flow. This will push some flow back to the source and render more outgoing arcs from the source not admissible.

Todo
(user): This may not be the most efficient algorithm if we need to loop many times. An alternative may be to handle the source like the other nodes in the algorithm, initially putting an excess of kMaxFlowQuantity on it, and making the source active like any other node with positive excess. To investigate.

Todo
(user): The code below is buggy when more than kMaxFlowQuantity can be pushed out of the source (i.e. when we loop more than once in the while()). This is not critical, since this code is not used in the default algorithm computation. The issue is twofold:

Definition at line 774 of file max_flow.cc.

◆ RefineWithGlobalUpdate()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::RefineWithGlobalUpdate ( )

protected

Todo: (user): This should be graph_->num_nodes(), but ebert graph does not have a correct size if the highest index nodes have no arcs.

The idea behind this is that if a node height augments by more than one, then it is likely to push flow back the way it came. This can lead to very costly loops. A bad case is: source -> n1 -> n2 and n2 just recently isolated from the sink. Then n2 will push flow back to n1, and n1 to n2 and so on. The height of each node will increase by steps of two until the height of the source is reached, which can take a long time. If the chain is longer, the situation is even worse. The behavior of this heuristic is related to the Gap heuristic.

Note: the global update will fix all such cases efficiently. So the idea is to discharge the active node as much as possible, and then do a global update.

We skip a node when this condition was true 2 times to avoid doing a global update too frequently.

Definition at line 813 of file max_flow.cc.

◆ Relabel()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::Relabel ( NodeIndex node )

protected

Relabels a node, i.e. increases its height by the minimum necessary amount. This version of Relabel is relaxed in a way such that if an admissible arc exists at the current node height, then the node is not relabeled. This enables us to deal with wrong values of first_admissible_arc_[node] when updating it is too costly.

Because we use a relaxed version, this is no longer true if the first_admissible_arc_[node] was not actually the first arc! DCHECK(CheckRelabelPrecondition(node));

Update min_height only for arcs with available capacity.

We found an admissible arc at the current height, just stop there. This is the true first_admissible_arc_[node].

Note: after a Relabel(), the loop will continue in Discharge(), and we are sure that all the arcs before first_admissible_arc are not admissible since their height is > min_height.

Definition at line 898 of file max_flow.cc.

◆ SaturateOutgoingArcsFromSource()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::SaturateOutgoingArcsFromSource ( )

protected

Tries to saturate all the outgoing arcs from the source that can reach the sink. Most of the time, we can do that in one go, except when more flow than kMaxFlowQuantity can be pushed out of the source in which case we have to be careful. Returns true if some flow was pushed.

If sink_ or source_ already have kMaxFlowQuantity, then there is no point pushing more flow since it will cause an integer overflow.

This is a special IsAdmissible() condition for the source.

We are careful in case the sum of the flow out of the source is greater than kMaxFlowQuantity to avoid overflow.

We push as much flow as we can so the current flow on the network will be kMaxFlowQuantity.

Since at the beginning of the function, current_flow_out_of_source was different from kMaxFlowQuantity, we are sure to have pushed some flow before if capped_flow is 0.

Definition at line 694 of file max_flow.cc.

◆ SetArcCapacity()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::SetArcCapacity	(	ArcIndex	arc,
		FlowQuantity	new_capacity )

Sets the capacity for arc to new_capacity.

The above condition is true if one of the two conditions is true: 1/ (capacity_delta > 0), meaning we are increasing the capacity 2/ (capacity_delta < 0 && free_capacity + capacity_delta >= 0) meaning we are reducing the capacity, but that the capacity reduction is not larger than the free capacity.

Note: this breaks the preflow invariants but it is currently not an issue since we restart from scratch on each Solve() and we set the status to NOT_SOLVED.

Todo: (user): The easiest is probably to allow negative node excess in other places than the source, but the current implementation does not deal with this.

Definition at line 194 of file max_flow.cc.

◆ SetArcFlow()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::SetArcFlow	(	ArcIndex	arc,
		FlowQuantity	new_flow )

Sets the flow for arc.

Note: this breaks the preflow invariants but it is currently not an issue since we restart from scratch on each Solve() and we set the status to NOT_SOLVED.

Definition at line 228 of file max_flow.cc.

◆ SetCapacityAndClearFlow()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::SetCapacityAndClearFlow	(	ArcIndex	arc,
		FlowQuantity	capacity )

inlineprotected

Sets the capacity of arc to 'capacity' and clears the flow on arc.

Definition at line 458 of file max_flow.h.

◆ SetCheckInput()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::SetCheckInput ( bool value )

inline

Definition at line 435 of file max_flow.h.

◆ SetCheckResult()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::SetCheckResult ( bool value )

inline

Definition at line 436 of file max_flow.h.

◆ SetUseGlobalUpdate()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::SetUseGlobalUpdate ( bool value )

inline

Sets the different algorithm options. All default to true. See the corresponding variable declaration below for more details.

Definition at line 430 of file max_flow.h.

◆ SetUseTwoPhaseAlgorithm()

template<typename Graph >

void operations_research::GenericMaxFlow< Graph >::SetUseTwoPhaseAlgorithm ( bool value )

inline

Definition at line 434 of file max_flow.h.

◆ Solve()

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::Solve ( )

Returns true if a maximum flow was solved.

Deal with the case when source_ or sink_ is not inside graph_. Since they are both specified independently of the graph, we do need to take care of this corner case.

Behave like a normal graph where source_ and sink_ are disconnected.

Note: the arc flow is set to 0 by InitializePreflow().

In this case, we are sure that the flow is > kMaxFlowQuantity.

Definition at line 353 of file max_flow.cc.

◆ status()

template<typename Graph >

Status operations_research::GenericMaxFlow< Graph >::status ( ) const

inline

Returns the status of last call to Solve(). NOT_SOLVED is returned if Solve() has never been called or if the problem has been modified in such a way that the previous solution becomes invalid.

Definition at line 359 of file max_flow.h.

◆ Tail()

template<typename Graph >

NodeIndex operations_research::GenericMaxFlow< Graph >::Tail ( ArcIndex arc ) const

inlineprotected

Definition at line 549 of file max_flow.h.

Member Data Documentation

◆ active_node_by_height_

template<typename Graph >

PriorityQueueWithRestrictedPush<NodeIndex, NodeHeight> operations_research::GenericMaxFlow< Graph >::active_node_by_height_

protected

A priority queue used for managing active nodes in the algorithm. It allows to select the active node with highest height before each Discharge(). Moreover, since all pushes from this node will be to nodes with height greater or equal to the initial discharged node height minus one, the PriorityQueueWithRestrictedPush is a perfect fit.

Definition at line 613 of file max_flow.h.

◆ active_nodes_

template<typename Graph >

std::vector<NodeIndex> operations_research::GenericMaxFlow< Graph >::active_nodes_

protected

A stack used for managing active nodes in the algorithm.

Note: the papers cited above recommend the use of a queue, but benchmarking so far has not proved it is better. In particular, processing nodes in LIFO order has better cache locality.

Definition at line 606 of file max_flow.h.

◆ bfs_queue_

template<typename Graph >

std::vector<NodeIndex> operations_research::GenericMaxFlow< Graph >::bfs_queue_

protected

Definition at line 627 of file max_flow.h.

◆ check_input_

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::check_input_

protected

Whether or not we check the input, this is a small price to pay for robustness. Disable only if you know the input is valid because an invalid input can cause the algorithm to run into an infinite loop!

Definition at line 650 of file max_flow.h.

◆ check_result_

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::check_result_

protected

Whether or not we check the result.

Todo: (user): Make the check more exhaustive by checking the optimality?

Definition at line 654 of file max_flow.h.

◆ first_admissible_arc_

template<typename Graph >

ArcIndexArray operations_research::GenericMaxFlow< Graph >::first_admissible_arc_

protected

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

Definition at line 600 of file max_flow.h.

◆ graph_

template<typename Graph >

const Graph* operations_research::GenericMaxFlow< Graph >::graph_

protected

A pointer to the graph passed as argument.

Definition at line 563 of file max_flow.h.

◆ kMaxFlowQuantity

template<typename Graph >

const FlowQuantity operations_research::GenericMaxFlow< Graph >::kMaxFlowQuantity

staticprotected

Initial value:

=

std::numeric_limits<FlowQuantity>::max()

Maximum manageable flow.

Definition at line 560 of file max_flow.h.

◆ node_excess_

template<typename Graph >

QuantityArray operations_research::GenericMaxFlow< Graph >::node_excess_

protected

An array representing the excess for each node in graph_.

Definition at line 566 of file max_flow.h.

◆ node_in_bfs_queue_

template<typename Graph >

std::vector<bool> operations_research::GenericMaxFlow< Graph >::node_in_bfs_queue_

protected

BFS queue used by the GlobalUpdate() function. We do not use a C++ queue because we need access to the vector for different optimizations.

Definition at line 626 of file max_flow.h.

◆ node_potential_

template<typename Graph >

NodeHeightArray operations_research::GenericMaxFlow< Graph >::node_potential_

protected

An array representing the height function for each node in graph_. For a given node, this is a lower bound on the shortest path length from this node to the sink in the residual network. The height of a node always goes up during the course of a Solve().

Since initially we saturate all the outgoing arcs of the source, we can never reach the sink from the source in the residual graph. Initially we set the height of the source to n (the number of node of the graph) and it never changes. If a node as an height >= n, then this node can't reach the sink and its height minus n is a lower bound on the shortest path length from this node to the source in the residual graph.

Definition at line 579 of file max_flow.h.

◆ process_node_by_height_

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::process_node_by_height_

protected

Whether or not we use the PriorityQueueWithRestrictedPush to process the active nodes rather than a simple queue. This can only be true if use_global_update_ is true.

Note(user): using a template will be slightly faster, but since we test this in a non-critical path, this only has a minor impact.

Definition at line 645 of file max_flow.h.

◆ residual_arc_capacity_

template<typename Graph >

QuantityArray operations_research::GenericMaxFlow< Graph >::residual_arc_capacity_

protected

An array representing the residual_capacity for each arc in graph_. Residual capacities enable one to represent the capacity and flow for all arcs in the graph in the following manner. For all arc, residual_arc_capacity_[arc] = capacity[arc] - flow[arc] Moreover, for reverse arcs, capacity[arc] = 0 by definition, Also flow[Opposite(arc)] = -flow[arc] by definition. Therefore:

for a direct arc: flow[arc] = 0 - flow[Opposite(arc)] = capacity[Opposite(arc)] - flow[Opposite(arc)] = residual_arc_capacity_[Opposite(arc)]
for a reverse arc: flow[arc] = -residual_arc_capacity_[arc] Using these facts enables one to only maintain residual_arc_capacity_, instead of both capacity and flow, for each direct and indirect arc. This reduces the amount of memory for this information by a factor 2.

Definition at line 597 of file max_flow.h.

◆ sink_

template<typename Graph >

NodeIndex operations_research::GenericMaxFlow< Graph >::sink_

protected

The index of the sink node in graph_.

Definition at line 619 of file max_flow.h.

◆ source_

template<typename Graph >

NodeIndex operations_research::GenericMaxFlow< Graph >::source_

protected

The index of the source node in graph_.

Definition at line 616 of file max_flow.h.

◆ stats_

template<typename Graph >

StatsGroup operations_research::GenericMaxFlow< Graph >::stats_

mutableprotected

Statistics about this class.

Definition at line 657 of file max_flow.h.

◆ status_

template<typename Graph >

Status operations_research::GenericMaxFlow< Graph >::status_

protected

The status of the problem.

Definition at line 622 of file max_flow.h.

◆ use_global_update_

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::use_global_update_

protected

Whether or not to use GlobalUpdate().

Definition at line 630 of file max_flow.h.

◆ use_two_phase_algorithm_

template<typename Graph >

bool operations_research::GenericMaxFlow< Graph >::use_two_phase_algorithm_

protected

Whether or not we use a two-phase algorithm: 1/ Only deal with nodes that can reach the sink. At the end we know the value of the maximum flow and we have a min-cut. 2/ Call PushFlowExcessBackToSource() to obtain a max-flow. This is usually a lot faster than the first phase.

Definition at line 637 of file max_flow.h.

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

ortools/graph/max_flow.h
ortools/graph/max_flow.cc

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Typedef Documentation

◆ ArcIndex

◆ ArcIndexArray

◆ IncomingArcIterator

◆ NodeHeight

◆ NodeHeightArray

◆ NodeIndex

◆ OutgoingArcIterator

◆ OutgoingOrOppositeIncomingArcIterator

Constructor & Destructor Documentation

◆ GenericMaxFlow() [1/2]

◆ GenericMaxFlow() [2/2]

◆ ~GenericMaxFlow()

Member Function Documentation

◆ AugmentingPathExists()

◆ Capacity()

◆ CheckInputConsistency()

◆ CheckRelabelPrecondition()

◆ CheckResult()

◆ ComputeReachableNodes()

◆ CreateFlowModel()

◆ DebugString()

◆ Discharge()

◆ Flow()

◆ GetAndRemoveFirstActiveNode()

◆ GetOptimalFlow()

◆ GetSinkNodeIndex()

◆ GetSinkSideMinCut()

◆ GetSourceNodeIndex()

◆ GetSourceSideMinCut()

◆ GlobalUpdate()

◆ graph()

◆ Head()

◆ InitializeActiveNodeContainer()

◆ InitializePreflow()

◆ IsActive()

◆ IsAdmissible()

◆ IsArcDirect()

◆ IsArcValid()

◆ IsEmptyActiveNodeContainer()

◆ kMaxFlowQuantity() [1/2]

◆ kMaxFlowQuantity() [2/2]

◆ operator=()

◆ Opposite()

◆ ProcessNodeByHeight()

◆ PushActiveNode()

◆ PushFlow()

◆ PushFlowExcessBackToSource()

◆ Refine()

◆ RefineWithGlobalUpdate()

◆ Relabel()

◆ SaturateOutgoingArcsFromSource()

◆ SetArcCapacity()

◆ SetArcFlow()

◆ SetCapacityAndClearFlow()

◆ SetCheckInput()

◆ SetCheckResult()

◆ SetUseGlobalUpdate()

◆ SetUseTwoPhaseAlgorithm()

◆ Solve()

◆ status()

◆ Tail()

Member Data Documentation

◆ active_node_by_height_

◆ active_nodes_

◆ bfs_queue_

◆ check_input_

◆ check_result_

◆ first_admissible_arc_

◆ graph_

◆ kMaxFlowQuantity

◆ node_excess_

◆ node_in_bfs_queue_

◆ node_potential_