Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Types | Public Member Functions | List of all members
operations_research::SimpleMaxFlow Class Reference

#include <max_flow.h>

Public Types

enum  Status { OPTIMAL , POSSIBLE_OVERFLOW , BAD_INPUT , BAD_RESULT }
 

Public Member Functions

 SimpleMaxFlow ()
 
 SimpleMaxFlow (const SimpleMaxFlow &)=delete
 This type is neither copyable nor movable.
 
SimpleMaxFlow & operator= (const SimpleMaxFlow &)=delete
 
ArcIndex AddArcWithCapacity (NodeIndex tail, NodeIndex head, FlowQuantity capacity)
 
NodeIndex NumNodes () const
 
ArcIndex NumArcs () const
 Returns the current number of arcs in the graph.
 
NodeIndex Tail (ArcIndex arc) const
 
NodeIndex Head (ArcIndex arc) const
 
FlowQuantity Capacity (ArcIndex arc) const
 
Status Solve (NodeIndex source, NodeIndex sink)
 
FlowQuantity OptimalFlow () const
 
FlowQuantity Flow (ArcIndex arc) const
 
void GetSourceSideMinCut (std::vector< NodeIndex > *result)
 
void GetSinkSideMinCut (std::vector< NodeIndex > *result)
 
void SetArcCapacity (ArcIndex arc, FlowQuantity capacity)
 
FlowModelProto CreateFlowModelProto (NodeIndex source, NodeIndex sink) const
 Creates the protocol buffer representation of the current problem.
 

Detailed Description

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.

Definition at line 151 of file max_flow.h.

Member Enumeration Documentation

◆ Status

enum operations_research::SimpleMaxFlow::Status

Solves the problem (finds the maximum flow from the given source to the given sink), and returns the problem status.

Enumerator
OPTIMAL 

Solve() was called and found an optimal solution. Note that OptimalFlow() may be 0 which means that the sink is not reachable from the source.

POSSIBLE_OVERFLOW 

There is a flow > std::numeric_limits<FlowQuantity>::max(). Note that in this case, the class will contain a solution with a flow reaching that bound.

Todo
(user): rename POSSIBLE_OVERFLOW to INT_OVERFLOW and modify our clients.
BAD_INPUT 

The input is inconsistent (bad tail/head/capacity values).

BAD_RESULT 

This should not happen. There was an error in our code (i.e. file a bug).

Definition at line 185 of file max_flow.h.

Constructor & Destructor Documentation

◆ SimpleMaxFlow() [1/2]

operations_research::SimpleMaxFlow::SimpleMaxFlow ( )

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

Definition at line 30 of file max_flow.cc.

◆ SimpleMaxFlow() [2/2]

operations_research::SimpleMaxFlow::SimpleMaxFlow ( const SimpleMaxFlow & )
delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AddArcWithCapacity()

ArcIndex operations_research::SimpleMaxFlow::AddArcWithCapacity ( 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.

Definition at line 32 of file max_flow.cc.

◆ Capacity()

FlowQuantity operations_research::SimpleMaxFlow::Capacity ( ArcIndex arc) const

Definition at line 51 of file max_flow.cc.

◆ CreateFlowModelProto()

FlowModelProto operations_research::SimpleMaxFlow::CreateFlowModelProto ( NodeIndex source,
NodeIndex sink ) const

Creates the protocol buffer representation of the current problem.

Definition at line 124 of file max_flow.cc.

◆ Flow()

FlowQuantity operations_research::SimpleMaxFlow::Flow ( ArcIndex arc) const

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

Definition at line 112 of file max_flow.cc.

◆ GetSinkSideMinCut()

void operations_research::SimpleMaxFlow::GetSinkSideMinCut ( 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.

Definition at line 119 of file max_flow.cc.

◆ GetSourceSideMinCut()

void operations_research::SimpleMaxFlow::GetSourceSideMinCut ( 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.

Definition at line 114 of file max_flow.cc.

◆ Head()

NodeIndex operations_research::SimpleMaxFlow::Head ( ArcIndex arc) const

Definition at line 49 of file max_flow.cc.

◆ NumArcs()

ArcIndex operations_research::SimpleMaxFlow::NumArcs ( ) const

Returns the current number of arcs in the graph.

Definition at line 45 of file max_flow.cc.

◆ NumNodes()

NodeIndex operations_research::SimpleMaxFlow::NumNodes ( ) const

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

Definition at line 43 of file max_flow.cc.

◆ operator=()

SimpleMaxFlow & operations_research::SimpleMaxFlow::operator= ( const SimpleMaxFlow & )
delete

◆ OptimalFlow()

FlowQuantity operations_research::SimpleMaxFlow::OptimalFlow ( ) const

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

Definition at line 110 of file max_flow.cc.

◆ SetArcCapacity()

void operations_research::SimpleMaxFlow::SetArcCapacity ( 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.

Definition at line 55 of file max_flow.cc.

◆ Solve()

SimpleMaxFlow::Status operations_research::SimpleMaxFlow::Solve ( NodeIndex source,
NodeIndex sink )

Translate the GenericMaxFlow::Status. It is different because NOT_SOLVED does not make sense in the simple api.

Definition at line 59 of file max_flow.cc.

◆ Tail()

NodeIndex operations_research::SimpleMaxFlow::Tail ( ArcIndex arc) const

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

Definition at line 47 of file max_flow.cc.

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