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.
| 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 |
CreateFlowModelProto | Return type: FlowModelProto Arguments: NodeIndex source, NodeIndex sink Creates the protocol buffer representation of the current problem.
|
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.
|
Head | Return type: NodeIndex Arguments: ArcIndex arc |
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()).
|
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["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()). |"]]
