C++ Reference: class GenericMaxFlow

This documentation is automatically generated.

Method
AugmentingPathExists

Return type: bool

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

Capacity

Return type: FlowQuantity

Arguments: ArcIndex arc

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

CheckInputConsistency

Return type: bool

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

CheckResult

Return type: bool

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.

CreateFlowModel

Return type: FlowModel

Returns the protocol buffer representation of the current problem.

Flow

Return type: FlowQuantity

Arguments: ArcIndex arc

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

GenericMaxFlow

Arguments: 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.

~GenericMaxFlow

Return type: virtual

GetOptimalFlow

Return type: FlowQuantity

Returns the total flow found by the algorithm.

GetSinkNodeIndex

Return type: NodeIndex

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

GetSinkSideMinCut

Return type: void

Arguments: 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.

GetSourceNodeIndex

Return type: NodeIndex

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

GetSourceSideMinCut

Return type: void

Arguments: 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.

graph

Return type: const Graph*

Returns the graph associated to the current object.

ProcessNodeByHeight

Return type: void

Arguments: bool value

SetArcCapacity

Return type: void

Arguments: ArcIndex arc, FlowQuantity new_capacity

Sets the capacity for arc to new_capacity.

SetArcFlow

Return type: void

Arguments: ArcIndex arc, FlowQuantity new_flow

Sets the flow for arc.

SetCheckInput

Return type: void

Arguments: bool value

SetCheckResult

Return type: void

Arguments: bool value

SetUseGlobalUpdate

Return type: void

Arguments: bool value

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

SetUseTwoPhaseAlgorithm

Return type: void

Arguments: bool value

Solve

Return type: bool

Returns true if a maximum flow was solved.

status

Return type: Status

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.