Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class SimpleMaxFlow
Note: 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.
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.
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).
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.
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.
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.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["\u003cp\u003e\u003ccode\u003eSimpleMaxFlow\u003c/code\u003e is a fast and efficient C++ class for solving maximum flow problems.\u003c/p\u003e\n"],["\u003cp\u003eIt offers methods to add arcs, set capacities, and retrieve flow information.\u003c/p\u003e\n"],["\u003cp\u003e\u003ccode\u003eSolve()\u003c/code\u003e calculates the maximum flow between a source and sink node.\u003c/p\u003e\n"],["\u003cp\u003e\u003ccode\u003eGetSourceSideMinCut()\u003c/code\u003e and \u003ccode\u003eGetSinkSideMinCut()\u003c/code\u003e can be used to identify the minimum cut after solving.\u003c/p\u003e\n"],["\u003cp\u003eWhile seemingly enabling incremental solves, \u003ccode\u003eSetArcCapacity()\u003c/code\u003e currently restarts the solver from scratch.\u003c/p\u003e\n"]]],["The `SimpleMaxFlow` class provides an interface for computing max-cost flow. Key actions include: adding directed arcs with `AddArcWithCapacity`, retrieving arc `Capacity`, `Head`, and `Tail`, and determining `Flow` on arcs. It also allows for querying the current number of `NumArcs` and `NumNodes`, changing arc capacity with `SetArcCapacity`, creating protocol buffers with `CreateFlowModelProto`, finding the `OptimalFlow` between source and sink after `Solve`, and getting `GetSourceSideMinCut` or `GetSinkSideMinCut`.\n"],null,["# SimpleMaxFlow\n\nC++ Reference: class SimpleMaxFlow\n==================================\n\n\nNote: This documentation is automatically generated.\nA simple and efficient max-cost flow interface. This is as fast as GenericMaxFlow\\\u003cReverseArcStaticGraph\\\u003e, which is the fastest, but uses more memory in order to hide the somewhat involved construction of the static graph. \n\nTODO(user): If the need arises, extend this interface to support warm start.\n\n| Method ||\n|------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`AddArcWithCapacity`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L162) | 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 (\\\u003e= 0). \\* Self-looping and duplicate arcs are supported. \\* After the method finishes, NumArcs() == the returned ArcIndex + 1. |\n| [`Capacity`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L176) | Return type: `FlowQuantity ` Arguments: `ArcIndex arc` \u003cbr /\u003e |\n| [`CreateFlowModelProto`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L229) | Return type: `FlowModelProto ` Arguments: `NodeIndex source, NodeIndex sink` Creates the protocol buffer representation of the current problem. |\n| [`Flow`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L208) | 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). |\n| [`GetSinkSideMinCut`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L219) | Return type: `void ` Arguments: `std::vector\u003cNodeIndex\u003e* 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. |\n| [`GetSourceSideMinCut`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L213) | Return type: `void ` Arguments: `std::vector\u003cNodeIndex\u003e* result` Returns the nodes reachable from the source by non-saturated arcs (.i.e. arc with Flow(arc) \\\u003c Capacity(arc)), the outgoing arcs of this set form a minimum cut. This works only if Solve() returned OPTIMAL. |\n| [`Head`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L175) | Return type: `NodeIndex ` Arguments: `ArcIndex arc` \u003cbr /\u003e |\n| [`NumArcs`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L170) | Return type: `ArcIndex ` Returns the current number of arcs in the graph. |\n| [`NumNodes`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L167) | Return type: `NodeIndex ` Returns the current number of nodes. This is one more than the largest node index seen so far in AddArcWithCapacity(). |\n| [`OptimalFlow`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L200) | Return type: `FlowQuantity ` Returns the maximum flow we can send from the source to the sink in the last OPTIMAL Solve() context. |\n| [`SetArcCapacity`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L226) | 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. |\n| [`SimpleMaxFlow`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L156) | The constructor takes no size. New node indices will be created lazily by AddArcWithCapacity(). |\n| [`Solve`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L196) | Return type: `Status ` Arguments: `NodeIndex source, NodeIndex sink` \u003cbr /\u003e |\n| [`Tail`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/max_flow.h#L174) | Return type: `NodeIndex ` Arguments: `ArcIndex arc` Returns user-provided data. The implementation will crash if \"arc\" is not in \\[0, NumArcs()). |"]]
