Google OR-Tools v9.15
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT > Class Template Reference

Detailed Description

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
class operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >

Definition at line 249 of file generic_max_flow.h.

#include <generic_max_flow.h>

Inheritance diagram for operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >:
operations_research::MaxFlowStatusClass

Public Types

typedef Graph::NodeIndex NodeIndex
typedef Graph::ArcIndex ArcIndex
typedef ArcFlowT ArcFlowType
typedef FlowSumT FlowSumType
typedef NodeIndex NodeHeight
Public Types inherited from operations_research::MaxFlowStatusClass
enum  Status {
  NOT_SOLVED , OPTIMAL , INT_OVERFLOW , BAD_INPUT ,
  BAD_RESULT
}

Public Member Functions

 GenericMaxFlow (const Graph *graph, NodeIndex source, NodeIndex sink)
 GenericMaxFlow (const GenericMaxFlow &)=delete
GenericMaxFlow & operator= (const GenericMaxFlow &)=delete
const Graph * graph () const
Status status () const
NodeIndex GetSourceNodeIndex () const
NodeIndex GetSinkNodeIndex () const
void SetArcCapacity (ArcIndex arc, ArcFlowType new_capacity)
bool Solve ()
FlowSumType GetOptimalFlow () const
FlowSumType Flow (ArcIndex arc) const
ArcFlowType Capacity (ArcIndex arc) const
void GetSourceSideMinCut (std::vector< NodeIndex > *result)
void GetSinkSideMinCut (std::vector< NodeIndex > *result)
bool AugmentingPathExists () const
FlowModelProto CreateFlowModel ()

Protected Member Functions

bool CheckResult () const
bool IsAdmissible (NodeIndex tail, ArcIndex arc, const NodeHeight *potentials) const
bool IsActive (NodeIndex node) const
bool CheckRelabelPrecondition (NodeIndex node) const
std::string DebugString (absl::string_view context, ArcIndex arc) const
void InitializeActiveNodeContainer ()
NodeIndex GetAndRemoveFirstActiveNode ()
void PushActiveNode (const NodeIndex &node)
bool IsEmptyActiveNodeContainer ()
void Refine ()
void RefineWithGlobalUpdate ()
void Discharge (NodeIndex node)
void InitializePreflow ()
void PushFlowExcessBackToSource ()
void GlobalUpdate ()
bool SaturateOutgoingArcsFromSource ()
void PushFlow (ArcFlowType flow, NodeIndex tail, ArcIndex arc)
void PushAsMuchFlowAsPossible (NodeIndex tail, ArcIndex arc, FlowSumType *node_excess)
void Relabel (NodeIndex node)
NodeIndex Head (ArcIndex arc) const
NodeIndex Tail (ArcIndex arc) const
ArcIndex Opposite (ArcIndex arc) const
bool IsArcDirect (ArcIndex arc) const
bool IsArcValid (ArcIndex arc) const
template<bool reverse>
void ComputeReachableNodes (NodeIndex start, std::vector< NodeIndex > *result)

Protected Attributes

const Graph * graph_
std::unique_ptr< FlowSumType[]> node_excess_
std::unique_ptr< NodeHeight[]> node_potential_
ZVector< ArcFlowType > residual_arc_capacity_
std::unique_ptr< ArcFlowType[]> initial_capacity_
std::unique_ptr< ArcIndex[]> first_admissible_arc_
PriorityQueueWithRestrictedPush< NodeIndex, NodeHeight > active_node_by_height_
NodeIndex source_
NodeIndex sink_
Status status_
std::vector< bool > node_in_bfs_queue_
std::vector< NodeIndex > bfs_queue_
StatsGroup stats_

Static Protected Attributes

static constexpr FlowSumType kMaxFlowSum

Member Typedef Documentation

◆ ArcFlowType

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
typedef ArcFlowT operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::ArcFlowType

Definition at line 253 of file generic_max_flow.h.

◆ ArcIndex

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
typedef Graph::ArcIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::ArcIndex

Definition at line 252 of file generic_max_flow.h.

◆ FlowSumType

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
typedef FlowSumT operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::FlowSumType

Definition at line 254 of file generic_max_flow.h.

◆ NodeHeight

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
typedef NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::NodeHeight

Definition at line 260 of file generic_max_flow.h.

◆ NodeIndex

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
typedef Graph::NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::NodeIndex

Definition at line 251 of file generic_max_flow.h.

Constructor & Destructor Documentation

◆ GenericMaxFlow() [1/2]

template<typename Graph, typename ArcFlowT, typename FlowSumT>
operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GenericMaxFlow ( const Graph * graph,
NodeIndex source,
NodeIndex sink )

Definition at line 592 of file generic_max_flow.h.

◆ GenericMaxFlow() [2/2]

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GenericMaxFlow ( const GenericMaxFlow< Graph, ArcFlowT, FlowSumT > & )
delete

Member Function Documentation

◆ AugmentingPathExists()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::AugmentingPathExists ( ) const

Definition at line 712 of file generic_max_flow.h.

◆ Capacity()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
ArcFlowType operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Capacity ( ArcIndex arc) const
inline

Definition at line 321 of file generic_max_flow.h.

◆ CheckRelabelPrecondition()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::CheckRelabelPrecondition ( NodeIndex node) const
protected

Definition at line 739 of file generic_max_flow.h.

◆ CheckResult()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::CheckResult ( ) const
protected

Definition at line 665 of file generic_max_flow.h.

◆ ComputeReachableNodes()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
template<bool reverse>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::ComputeReachableNodes ( NodeIndex start,
std::vector< NodeIndex > * result )
protected

Definition at line 1358 of file generic_max_flow.h.

◆ CreateFlowModel()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
FlowModelProto operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::CreateFlowModel ( )

Definition at line 1390 of file generic_max_flow.h.

◆ DebugString()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
std::string operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::DebugString ( absl::string_view context,
ArcIndex arc ) const
protected

Definition at line 750 of file generic_max_flow.h.

◆ Discharge()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Discharge ( NodeIndex node)
protected

Definition at line 1270 of file generic_max_flow.h.

◆ Flow()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
FlowSumType operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Flow ( ArcIndex arc) const
inline

Definition at line 309 of file generic_max_flow.h.

◆ GetAndRemoveFirstActiveNode()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GetAndRemoveFirstActiveNode ( )
inlineprotected

Definition at line 385 of file generic_max_flow.h.

◆ GetOptimalFlow()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
FlowSumType operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GetOptimalFlow ( ) const
inline

Definition at line 298 of file generic_max_flow.h.

◆ GetSinkNodeIndex()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GetSinkNodeIndex ( ) const
inline

Definition at line 286 of file generic_max_flow.h.

◆ GetSinkSideMinCut()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GetSinkSideMinCut ( std::vector< NodeIndex > * result)

Definition at line 659 of file generic_max_flow.h.

◆ GetSourceNodeIndex()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GetSourceNodeIndex ( ) const
inline

Definition at line 283 of file generic_max_flow.h.

◆ GetSourceSideMinCut()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GetSourceSideMinCut ( std::vector< NodeIndex > * result)

Definition at line 653 of file generic_max_flow.h.

◆ GlobalUpdate()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::GlobalUpdate ( )
protected

Definition at line 1000 of file generic_max_flow.h.

◆ graph()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
const Graph * operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::graph ( ) const
inline

Definition at line 275 of file generic_max_flow.h.

◆ Head()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Head ( ArcIndex arc) const
inlineprotected

Definition at line 452 of file generic_max_flow.h.

◆ InitializeActiveNodeContainer()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::InitializeActiveNodeContainer ( )
protected

Definition at line 1186 of file generic_max_flow.h.

◆ InitializePreflow()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::InitializePreflow ( )
protected

Definition at line 795 of file generic_max_flow.h.

◆ IsActive()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::IsActive ( NodeIndex node) const
inlineprotected

Definition at line 368 of file generic_max_flow.h.

◆ IsAdmissible()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::IsAdmissible ( NodeIndex tail,
ArcIndex arc,
const NodeHeight * potentials ) const
inlineprotected

Definition at line 359 of file generic_max_flow.h.

◆ IsArcDirect()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::IsArcDirect ( ArcIndex arc) const
protected

Definition at line 1346 of file generic_max_flow.h.

◆ IsArcValid()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::IsArcValid ( ArcIndex arc) const
protected

Definition at line 1352 of file generic_max_flow.h.

◆ IsEmptyActiveNodeContainer()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::IsEmptyActiveNodeContainer ( )
inlineprotected

Definition at line 395 of file generic_max_flow.h.

◆ operator=()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
GenericMaxFlow & operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::operator= ( const GenericMaxFlow< Graph, ArcFlowT, FlowSumT > & )
delete

◆ Opposite()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
Graph::ArcIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Opposite ( ArcIndex arc) const
protected

Definition at line 1340 of file generic_max_flow.h.

◆ PushActiveNode()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::PushActiveNode ( const NodeIndex & node)
inlineprotected

Definition at line 390 of file generic_max_flow.h.

◆ PushAsMuchFlowAsPossible()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::PushAsMuchFlowAsPossible ( NodeIndex tail,
ArcIndex arc,
FlowSumType * node_excess )
protected

Definition at line 1164 of file generic_max_flow.h.

◆ PushFlow()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::PushFlow ( ArcFlowType flow,
NodeIndex tail,
ArcIndex arc )
protected

Definition at line 1140 of file generic_max_flow.h.

◆ PushFlowExcessBackToSource()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::PushFlowExcessBackToSource ( )
protected

Definition at line 844 of file generic_max_flow.h.

◆ Refine()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Refine ( )
protected

◆ RefineWithGlobalUpdate()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::RefineWithGlobalUpdate ( )
protected

Definition at line 1202 of file generic_max_flow.h.

◆ Relabel()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Relabel ( NodeIndex node)
protected

Definition at line 1309 of file generic_max_flow.h.

◆ SaturateOutgoingArcsFromSource()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::SaturateOutgoingArcsFromSource ( )
protected

Definition at line 1099 of file generic_max_flow.h.

◆ SetArcCapacity()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
void operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::SetArcCapacity ( ArcIndex arc,
ArcFlowType new_capacity )

Definition at line 628 of file generic_max_flow.h.

◆ Solve()

template<typename Graph, typename ArcFlowT, typename FlowSumT>
bool operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Solve ( )

Definition at line 766 of file generic_max_flow.h.

◆ status()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
Status operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::status ( ) const
inline

Definition at line 280 of file generic_max_flow.h.

◆ Tail()

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::Tail ( ArcIndex arc) const
inlineprotected

Definition at line 453 of file generic_max_flow.h.

Member Data Documentation

◆ active_node_by_height_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
PriorityQueueWithRestrictedPush<NodeIndex, NodeHeight> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::active_node_by_height_
protected

Definition at line 519 of file generic_max_flow.h.

◆ bfs_queue_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
std::vector<NodeIndex> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::bfs_queue_
protected

Definition at line 533 of file generic_max_flow.h.

◆ first_admissible_arc_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
std::unique_ptr<ArcIndex[]> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::first_admissible_arc_
protected

Definition at line 512 of file generic_max_flow.h.

◆ graph_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
const Graph* operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::graph_
protected

Definition at line 468 of file generic_max_flow.h.

◆ initial_capacity_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
std::unique_ptr<ArcFlowType[]> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::initial_capacity_
protected

Definition at line 509 of file generic_max_flow.h.

◆ kMaxFlowSum

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
FlowSumType operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::kMaxFlowSum
staticconstexprprotected
Initial value:
=
std::numeric_limits<FlowSumType>::max()

Definition at line 464 of file generic_max_flow.h.

◆ node_excess_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
std::unique_ptr<FlowSumType[]> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::node_excess_
protected

Definition at line 473 of file generic_max_flow.h.

◆ node_in_bfs_queue_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
std::vector<bool> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::node_in_bfs_queue_
protected

Definition at line 532 of file generic_max_flow.h.

◆ node_potential_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
std::unique_ptr<NodeHeight[]> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::node_potential_
protected

Definition at line 486 of file generic_max_flow.h.

◆ residual_arc_capacity_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
ZVector<ArcFlowType> operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::residual_arc_capacity_
protected

Definition at line 504 of file generic_max_flow.h.

◆ sink_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::sink_
protected

Definition at line 525 of file generic_max_flow.h.

◆ source_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
NodeIndex operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::source_
protected

Definition at line 522 of file generic_max_flow.h.

◆ stats_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
StatsGroup operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::stats_
mutableprotected

Definition at line 536 of file generic_max_flow.h.

◆ status_

template<typename Graph, typename ArcFlowT = int64_t, typename FlowSumT = int64_t>
Status operations_research::GenericMaxFlow< Graph, ArcFlowT, FlowSumT >::status_
protected

Definition at line 528 of file generic_max_flow.h.

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