#include <generic_max_flow.h>

Inheritance diagram for operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >:

Public Types
typedef Graph::NodeIndex	NodeIndex

typedef Graph::ArcIndex	ArcIndex

typedef ArcFlowT	ArcFlowType

typedef FlowSumT	FlowSumType

typedef NodeIndex	NodeHeight

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

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, ArcFlowType new_capacity)

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

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

FlowSumType	Flow (ArcIndex arc) const

ArcFlowType	Capacity (ArcIndex arc) const
	Returns the initial capacity of an arc.

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

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

bool	AugmentingPathExists () const

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

Protected Member Functions
bool	CheckResult () const

bool	IsAdmissible (NodeIndex tail, ArcIndex arc, const NodeHeight *potentials) const
	Returns true if arc is admissible.

bool	IsActive (NodeIndex node) const

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 (ArcFlowType flow, NodeIndex tail, ArcIndex arc)

void	PushAsMuchFlowAsPossible (NodeIndex tail, ArcIndex arc, FlowSumType *node_excess)

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)

Protected Attributes
const Graph *	graph_
	A pointer to the graph passed as argument.

std::unique_ptr< FlowSumType[]>	node_excess_

std::unique_ptr< NodeHeight[]>	node_potential_

ZVector< ArcFlowType >	residual_arc_capacity_

std::unique_ptr< ArcFlowType[]>	initial_capacity_

std::unique_ptr< ArcIndex[]>	first_admissible_arc_
	An array representing the first admissible arc for each node in graph_.

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_

StatsGroup	stats_
	Statistics about this class.

Static Protected Attributes
static constexpr FlowSumType	kMaxFlowSum
	Maximum manageable flow.

Detailed Description

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
class operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >

Generic MaxFlow that works on graphs with the notion of "reverse" arcs. That is, the graph is directed, and each arc 'tail -> head' must be associated to an unique reverse arc going in the opposite direction 'head -> tail'. We must also have reverse[reverse[arc]] = arc.

This works with all the reverse arc graphs from 'util/graph/graph.h' and uses the API defined there.

We actually support two kind of graphs with "reverse" arcs depending on the value of Graph::kHasNegativeReverseArcs:

If it is true, the arcs from the "user graph" are called "direct" arcs and are assumed to be indexed in [0, num_arcs). These are the only ones that can have a positive capacity. All the "reverse/opposite" of these arcs will always have negative indices in [-num_arcs, 0) and a capacity of zero.
If it is false, then we only have "direct" arcs in [0, num_arcs), the reverse of each arc must lives in the same space, and both an arc and its reverse can have a positive initial capacity. This can lead to twice fewer arcs and a faster algo if the "user graph" as a lot of reverse arcs already.

Flow types and overflow: To optimize memory usage and speed we have two integer types representing flow quantities.

ArcFlowType (can be unsigned) is used to represent the flow per arc. The type should be big enough to hold the initial capacity of an arc + its reverse. So if all your initial capacity <= std::numeric_limit<ArcFlowType>::max() / 2, you are safe.
FlowSumType (must be signed) is used to hold the sum of a flow going through a node or through the full network. Ideally, the sum of all the capacity of the arcs leaving the source should fit in a FlowSumType. If this is the case, you will get the better performance, and always an OPTIMAL result. Otherwise, the code might be slower, and you will get OPTIMAL only if the max_flow that can be sent through the network fit a FlowSumType, you will get the INT_OVERFLOW status if more flow than that can be sent.

Definition at line 250 of file generic_max_flow.h.

Member Typedef Documentation

◆ ArcFlowType

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

typedef ArcFlowT operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::ArcFlowType

Definition at line 254 of file generic_max_flow.h.

◆ ArcIndex

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

typedef Graph::ArcIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::ArcIndex

Definition at line 253 of file generic_max_flow.h.

◆ FlowSumType

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

typedef FlowSumT operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::FlowSumType

Definition at line 255 of file generic_max_flow.h.

◆ NodeHeight

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

typedef NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 261 of file generic_max_flow.h.

◆ NodeIndex

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

typedef Graph::NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::NodeIndex

Definition at line 252 of file generic_max_flow.h.

Constructor & Destructor Documentation

◆ GenericMaxFlow() [1/2]

template<typename Graph, typename ArcFlowT, typename FlowSumT>

operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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.

We will initialize them in InitializePreflow(), so no need for memset.

Todo: (user): Unfortunately std/absl::make_unique_for_overwrite is not yet available in open-source.

We will need to store the initial capacity in this case.

Definition at line 593 of file generic_max_flow.h.

◆ GenericMaxFlow() [2/2]

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GenericMaxFlow ( const GenericMaxFlow< Graph, ArcFlowT, FlowSumT > & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AugmentingPathExists()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 713 of file generic_max_flow.h.

◆ Capacity()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

ArcFlowType operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Capacity ( ArcIndex arc ) const

inline

Returns the initial capacity of an arc.

Definition at line 322 of file generic_max_flow.h.

◆ CheckRelabelPrecondition()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 740 of file generic_max_flow.h.

◆ CheckResult()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::CheckResult ( ) const

protected

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 666 of file generic_max_flow.h.

◆ ComputeReachableNodes()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

template<bool reverse>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 1359 of file generic_max_flow.h.

◆ CreateFlowModel()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

FlowModelProto operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::CreateFlowModel ( )

Returns the protocol buffer representation of the current problem.

Definition at line 1391 of file generic_max_flow.h.

◆ DebugString()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

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

protected

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

Definition at line 751 of file generic_max_flow.h.

◆ Discharge()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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.

We cache this as this is a hot-loop and we don't want bound checking.

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

This node can no longer reach the sink, skip until PushFlowExcessBackToSource().

Definition at line 1271 of file generic_max_flow.h.

◆ Flow()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

FlowSumType operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Flow ( ArcIndex arc ) const

inline

Returns the current flow on the given arc.

Note: on a couple (arc, opposite_arc) the flow only goes in one direction (where it is positive) and the other direction will have the negation of that flow.

Tricky: This returns a FlowSumType in order to be able to distinguish negative flow from positive flow when ArcFlowType is unsigned.

Todo: (user): We could change the API to avoid that if needed.

Definition at line 310 of file generic_max_flow.h.

◆ GetAndRemoveFirstActiveNode()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GetAndRemoveFirstActiveNode ( )

inlineprotected

Get the first element from the active node container.

Definition at line 386 of file generic_max_flow.h.

◆ GetOptimalFlow()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

FlowSumType operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GetOptimalFlow ( ) const

inline

Returns the total flow found by the algorithm.

Definition at line 299 of file generic_max_flow.h.

◆ GetSinkNodeIndex()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GetSinkNodeIndex ( ) const

inline

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

Definition at line 287 of file generic_max_flow.h.

◆ GetSinkSideMinCut()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 660 of file generic_max_flow.h.

◆ GetSourceNodeIndex()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GetSourceNodeIndex ( ) const

inline

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

Definition at line 284 of file generic_max_flow.h.

◆ GetSourceSideMinCut()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 654 of file generic_max_flow.h.

◆ GlobalUpdate()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 cache this as this is a hot-loop and we don't want bound checking.

We do a BFS in the reverse residual graph, starting from the sink. 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. If there is possible overflow and the source is reachable, we still do not want to relabel it, so we start with the source marked.

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 kMaxFlowSum 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 1001 of file generic_max_flow.h.

◆ graph()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

const Graph * operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::graph ( ) const

inline

Returns the graph associated to the current object.

Definition at line 276 of file generic_max_flow.h.

◆ Head()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

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

inlineprotected

Handy member functions to make the code more compact.

Definition at line 453 of file generic_max_flow.h.

◆ InitializeActiveNodeContainer()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::InitializeActiveNodeContainer ( )

protected

Initializes the container active_nodes_.

This node cannot reach the sink in the residual graph, we don't need to consider it anymore, and we will just push its potential excess back to the source in PushFlowExcessBackToSource() at the end.

Definition at line 1187 of file generic_max_flow.h.

◆ InitializePreflow()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::InitializePreflow ( )

protected

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

Todo: (user): Ebert graph has an issue with nodes with no arcs, so we use max_num_nodes here to resize vectors.

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.)

Restart from a clear state with no flow, and an initial arc capacity.

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 we set first_admissible_arc_ to the first arc in the iteration.

Definition at line 796 of file generic_max_flow.h.

◆ IsActive()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 369 of file generic_max_flow.h.

◆ IsAdmissible()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::IsAdmissible	(	NodeIndex	tail,
		ArcIndex	arc,
		const NodeHeight *	potentials ) const

inlineprotected

Returns true if arc is admissible.

Definition at line 360 of file generic_max_flow.h.

◆ IsArcDirect()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

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

protected

Definition at line 1347 of file generic_max_flow.h.

◆ IsArcValid()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

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

protected

Definition at line 1353 of file generic_max_flow.h.

◆ IsEmptyActiveNodeContainer()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::IsEmptyActiveNodeContainer ( )

inlineprotected

Check the emptiness of the container.

Definition at line 396 of file generic_max_flow.h.

◆ operator=()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

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

delete

◆ Opposite()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

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

protected

Definition at line 1341 of file generic_max_flow.h.

◆ PushActiveNode()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

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

inlineprotected

Push element to the active node container.

Definition at line 391 of file generic_max_flow.h.

◆ PushAsMuchFlowAsPossible()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::PushAsMuchFlowAsPossible	(	NodeIndex	tail,
		ArcIndex	arc,
		FlowSumType *	node_excess )

protected

Similar to PushFlow(), but this will always push std::min(node_excess_[tail], residual_arc_capacity_[arc]).

We also use a cached node_excess_.data() as this is used in hot loops and allow to remove bound checking and fetching the pointer which is constant.

We either push all node_excess or saturate the arc by consuming all its residual capacity.

Definition at line 1165 of file generic_max_flow.h.

◆ PushFlow()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::PushFlow	(	ArcFlowType	flow,
		NodeIndex	tail,
		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.

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

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

Note(user): 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.

Definition at line 1141 of file generic_max_flow.h.

◆ PushFlowExcessBackToSource()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 source. Note that the sink_ and the source_ are not stored in reverse_topological_order.

Definition at line 845 of file generic_max_flow.h.

◆ Refine()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Refine ( )

protected

Performs optimization step.

◆ RefineWithGlobalUpdate()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::RefineWithGlobalUpdate ( )

protected

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 kMaxFlowSum out of the source the loop is as follow:

Push up to kMaxFlowSum 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 kMaxFlowSum on it, and making the source active like any other node with positive excess. To investigate.

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.

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 1203 of file generic_max_flow.h.

◆ Relabel()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 1310 of file generic_max_flow.h.

◆ SaturateOutgoingArcsFromSource()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 kMaxFlowSum 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 kMaxFlowSum, 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 kMaxFlowSum to avoid overflow.

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

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

Definition at line 1100 of file generic_max_flow.h.

◆ SetArcCapacity()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::SetArcCapacity	(	ArcIndex	arc,
		ArcFlowType	new_capacity )

Sets the capacity for arc to new_capacity.

Note: this will be ignored for self-arc, so do not be surprised if you get zero when reading the capacity of a self-arc back.

This serves no purpose from a max-flow point of view, so it is safer to just leave the capacity of all self-arc at zero.

Since the class might have already be used, we need to make sure we clear any previous state on this arc and its reverse.

Definition at line 629 of file generic_max_flow.h.

◆ Solve()

template<typename Graph, typename ArcFlowT, typename FlowSumT>

bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 > kMaxFlowSum.

Definition at line 767 of file generic_max_flow.h.

◆ status()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

Status operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 281 of file generic_max_flow.h.

◆ Tail()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

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

inlineprotected

Definition at line 454 of file generic_max_flow.h.

Member Data Documentation

◆ active_node_by_height_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

PriorityQueueWithRestrictedPush<NodeIndex, NodeHeight> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 520 of file generic_max_flow.h.

◆ bfs_queue_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

std::vector<NodeIndex> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::bfs_queue_

protected

Definition at line 534 of file generic_max_flow.h.

◆ first_admissible_arc_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

std::unique_ptr<ArcIndex[]> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::first_admissible_arc_

protected

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

Definition at line 513 of file generic_max_flow.h.

◆ graph_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

const Graph* operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::graph_

protected

A pointer to the graph passed as argument.

Definition at line 469 of file generic_max_flow.h.

◆ initial_capacity_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

std::unique_ptr<ArcFlowType[]> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::initial_capacity_

protected

The initial capacity as set by SetArcCapacity(), unused if Graph::kNegativeReverseArcs, as we can always recover the initial capacity from the residual capacities of an arc and its reverse.

Definition at line 510 of file generic_max_flow.h.

◆ kMaxFlowSum

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

FlowSumType operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::kMaxFlowSum

staticconstexprprotected

Initial value:

=

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

Maximum manageable flow.

Definition at line 465 of file generic_max_flow.h.

◆ node_excess_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

std::unique_ptr<FlowSumType[]> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::node_excess_

protected

An array representing the excess for each node in graph_. With the current algorithm this is always positive except at the source.

Todo: (user): If needed we could tweak that to allow unsigned FlowSumType.

Definition at line 474 of file generic_max_flow.h.

◆ node_in_bfs_queue_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

std::vector<bool> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 533 of file generic_max_flow.h.

◆ node_potential_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

std::unique_ptr<NodeHeight[]> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 487 of file generic_max_flow.h.

◆ residual_arc_capacity_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

ZVector<ArcFlowType> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::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 505 of file generic_max_flow.h.

◆ sink_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::sink_

protected

The index of the sink node in graph_.

Definition at line 526 of file generic_max_flow.h.

◆ source_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::source_

protected

The index of the source node in graph_.

Definition at line 523 of file generic_max_flow.h.

◆ stats_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

StatsGroup operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::stats_

mutableprotected

Statistics about this class.

Definition at line 537 of file generic_max_flow.h.

◆ status_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>

Status operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::status_

protected

The status of the problem.

Definition at line 529 of file generic_max_flow.h.

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

ortools/graph/generic_max_flow.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Typedef Documentation

◆ ArcFlowType

◆ ArcIndex

◆ FlowSumType

◆ NodeHeight

◆ NodeIndex

Constructor & Destructor Documentation

◆ GenericMaxFlow() [1/2]

◆ GenericMaxFlow() [2/2]

Member Function Documentation

◆ AugmentingPathExists()

◆ Capacity()

◆ CheckRelabelPrecondition()

◆ CheckResult()

◆ ComputeReachableNodes()

◆ CreateFlowModel()

◆ DebugString()

◆ Discharge()

◆ Flow()

◆ GetAndRemoveFirstActiveNode()

◆ GetOptimalFlow()

◆ GetSinkNodeIndex()

◆ GetSinkSideMinCut()

◆ GetSourceNodeIndex()

◆ GetSourceSideMinCut()

◆ GlobalUpdate()

◆ graph()

◆ Head()

◆ InitializeActiveNodeContainer()

◆ InitializePreflow()

◆ IsActive()

◆ IsAdmissible()

◆ IsArcDirect()

◆ IsArcValid()

◆ IsEmptyActiveNodeContainer()

◆ operator=()

◆ Opposite()

◆ PushActiveNode()

◆ PushAsMuchFlowAsPossible()

◆ PushFlow()

◆ PushFlowExcessBackToSource()

◆ Refine()

◆ RefineWithGlobalUpdate()

◆ Relabel()

◆ SaturateOutgoingArcsFromSource()

◆ SetArcCapacity()

◆ Solve()

◆ status()

◆ Tail()

Member Data Documentation

◆ active_node_by_height_

◆ bfs_queue_

◆ first_admissible_arc_

◆ graph_

◆ initial_capacity_

◆ kMaxFlowSum

◆ node_excess_

◆ node_in_bfs_queue_

◆ node_potential_

◆ residual_arc_capacity_

◆ sink_

◆ source_

◆ stats_

◆ status_