C++ Reference: class SimpleMaxFlow

This documentation is automatically generated.

A simple and efficient max-cost flow interface. This is as fast as GenericMaxFlow<ReverseArcStaticGraph>, which is the fastest, but uses more memory in order to hide the somewhat involved construction of the static graph.

TODO(user): If the need arises, extend this interface to support warm start.
Method
AddArcWithCapacity

Return type: ArcIndex

Arguments: NodeIndex tail, NodeIndex head, FlowQuantity capacity

Adds a directed arc with the given capacity from tail to head. * Node indices and capacity must be non-negative (>= 0). * Self-looping and duplicate arcs are supported. * After the method finishes, NumArcs() == the returned ArcIndex + 1.

Capacity

Return type: FlowQuantity

Arguments: ArcIndex arc

CreateFlowModelOfLastSolve

Return type: FlowModel

Creates the protocol buffer representation of the problem used by the last Solve() call. This is mainly useful for debugging.

Flow

Return type: FlowQuantity

Arguments: ArcIndex arc

Returns the flow on the given arc in the last OPTIMAL Solve() context. Note: It is possible that there is more than one optimal solution. The algorithm is deterministic so it will always return the same solution for a given problem. However, there is no guarantee of this from one code version to the next (but the code does not change often).

GetSinkSideMinCut

Return type: void

Arguments: std::vector<NodeIndex>* result

Returns the nodes that can reach the sink by non-saturated arcs, the outgoing arcs of this set form a minimum cut. Note that if this is the complement set of GetNodeReachableFromSource(), then the min-cut is unique. This works only if Solve() returned OPTIMAL.

GetSourceSideMinCut

Return type: void

Arguments: std::vector<NodeIndex>* result

Returns the nodes reachable from the source by non-saturated arcs (.i.e. arc with Flow(arc) < Capacity(arc)), the outgoing arcs of this set form a minimum cut. This works only if Solve() returned OPTIMAL.

NumArcs

Return type: ArcIndex

Returns the current number of arcs in the graph.

NumNodes

Return type: NodeIndex

Returns the current number of nodes. This is one more than the largest node index seen so far in AddArcWithCapacity().

OptimalFlow

Return type: FlowQuantity

Returns the maximum flow we can send from the source to the sink in the last OPTIMAL Solve() context.

SetArcCapacity

Return type: void

Arguments: ArcIndex arc, FlowQuantity capacity

Change the capacity of an arc. WARNING: This looks like it enables incremental solves, but as of 2018-02, the next Solve() will restart from scratch anyway. TODO(user): Support incrementality in the max flow implementation.

SimpleMaxFlow

The constructor takes no size. New node indices will be created lazily by AddArcWithCapacity().

Solve

Return type: Status

Arguments: NodeIndex source, NodeIndex sink

Tail

Return type: NodeIndex

Arguments: ArcIndex arc

Returns user-provided data. The implementation will crash if "arc" is not in [0, NumArcs()).

Send feedback about...