OR-Tools  8.2
BlossomGraph

Detailed Description

Definition at line 165 of file perfect_matching.h.

Classes

struct  Edge
 
struct  Node
 

Public Member Functions

 DEFINE_INT_TYPE (NodeIndex, int)
 
 DEFINE_INT_TYPE (EdgeIndex, int)
 
 DEFINE_INT_TYPE (CostValue, int64)
 
 BlossomGraph (int num_nodes)
 
void AddEdge (NodeIndex tail, NodeIndex head, CostValue cost)
 
ABSL_MUST_USE_RESULT bool Initialize ()
 
void PrimalUpdates ()
 
CostValue ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue ()
 
void UpdateAllTrees (CostValue delta)
 
bool NodeIsMatched (NodeIndex n) const
 
NodeIndex Match (NodeIndex n) const
 
void Grow (EdgeIndex e, NodeIndex tail, NodeIndex head)
 
void Augment (EdgeIndex e)
 
void Shrink (EdgeIndex e)
 
void Expand (NodeIndex to_expand)
 
int NumMatched () const
 
CostValue DualObjective () const
 
void ExpandAllBlossoms ()
 
CostValue Slack (const Edge &edge) const
 
CostValue Dual (const Node &node) const
 
void DisplayStats () const
 
void DebugCheckNoPossiblePrimalUpdates ()
 
bool DebugDualsAreFeasible () const
 
void DebugUpdateNodeDual (NodeIndex n, CostValue delta)
 
bool DebugEdgeIsTightAndExternal (const Edge &edge) const
 
const EdgeGetEdge (int e) const
 
const NodeGetNode (int n) const
 
std::string NodeDebugString (NodeIndex n) const
 
std::string EdgeDebugString (EdgeIndex e) const
 
std::string DebugString () const
 

Static Public Attributes

static const NodeIndex kNoNodeIndex
 
static const EdgeIndex kNoEdgeIndex
 
static const CostValue kMaxCostValue
 

Constructor & Destructor Documentation

◆ BlossomGraph()

BlossomGraph ( int  num_nodes)
explicit

Definition at line 116 of file perfect_matching.cc.

Member Function Documentation

◆ AddEdge()

void AddEdge ( NodeIndex  tail,
NodeIndex  head,
CostValue  cost 
)

Definition at line 126 of file perfect_matching.cc.

◆ Augment()

void Augment ( EdgeIndex  e)

Definition at line 547 of file perfect_matching.cc.

◆ ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue()

CostValue ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue ( )

Definition at line 259 of file perfect_matching.cc.

◆ DebugCheckNoPossiblePrimalUpdates()

void DebugCheckNoPossiblePrimalUpdates ( )

Definition at line 347 of file perfect_matching.cc.

◆ DebugDualsAreFeasible()

bool DebugDualsAreFeasible ( ) const

Definition at line 450 of file perfect_matching.cc.

◆ DebugEdgeIsTightAndExternal()

bool DebugEdgeIsTightAndExternal ( const Edge edge) const

Definition at line 463 of file perfect_matching.cc.

◆ DebugString()

std::string DebugString ( ) const

Definition at line 1203 of file perfect_matching.cc.

◆ DebugUpdateNodeDual()

void DebugUpdateNodeDual ( NodeIndex  n,
CostValue  delta 
)

Definition at line 1214 of file perfect_matching.cc.

◆ DEFINE_INT_TYPE() [1/3]

DEFINE_INT_TYPE ( CostValue  ,
int64   
)

◆ DEFINE_INT_TYPE() [2/3]

DEFINE_INT_TYPE ( EdgeIndex  ,
int   
)

◆ DEFINE_INT_TYPE() [3/3]

DEFINE_INT_TYPE ( NodeIndex  ,
int   
)

◆ DisplayStats()

void DisplayStats ( ) const

Definition at line 1266 of file perfect_matching.cc.

◆ Dual()

CostValue Dual ( const Node node) const

Definition at line 1246 of file perfect_matching.cc.

◆ DualObjective()

CostValue DualObjective ( ) const

Definition at line 1255 of file perfect_matching.cc.

◆ EdgeDebugString()

std::string EdgeDebugString ( EdgeIndex  e) const

Definition at line 1193 of file perfect_matching.cc.

◆ Expand()

void Expand ( NodeIndex  to_expand)

Definition at line 845 of file perfect_matching.cc.

◆ ExpandAllBlossoms()

void ExpandAllBlossoms ( )

Definition at line 1054 of file perfect_matching.cc.

◆ GetEdge()

const Edge& GetEdge ( int  e) const
inline

Definition at line 390 of file perfect_matching.h.

◆ GetNode()

const Node& GetNode ( int  n) const
inline

Definition at line 391 of file perfect_matching.h.

◆ Grow()

void Grow ( EdgeIndex  e,
NodeIndex  tail,
NodeIndex  head 
)

Definition at line 470 of file perfect_matching.cc.

◆ Initialize()

bool Initialize ( )

Definition at line 143 of file perfect_matching.cc.

◆ Match()

NodeIndex Match ( NodeIndex  n) const

Definition at line 336 of file perfect_matching.cc.

◆ NodeDebugString()

std::string NodeDebugString ( NodeIndex  n) const

Definition at line 1177 of file perfect_matching.cc.

◆ NodeIsMatched()

bool NodeIsMatched ( NodeIndex  n) const

Definition at line 329 of file perfect_matching.cc.

◆ NumMatched()

int NumMatched ( ) const
inline

Definition at line 352 of file perfect_matching.h.

◆ PrimalUpdates()

void PrimalUpdates ( )

Definition at line 381 of file perfect_matching.cc.

◆ Shrink()

void Shrink ( EdgeIndex  e)

Definition at line 650 of file perfect_matching.cc.

◆ Slack()

CostValue Slack ( const Edge edge) const

Definition at line 1228 of file perfect_matching.cc.

◆ UpdateAllTrees()

void UpdateAllTrees ( CostValue  delta)

Definition at line 309 of file perfect_matching.cc.

Member Data Documentation

◆ kMaxCostValue

const BlossomGraph::CostValue kMaxCostValue
static
Initial value:
=
static const int64 kint64max

Definition at line 177 of file perfect_matching.h.

◆ kNoEdgeIndex

const BlossomGraph::EdgeIndex kNoEdgeIndex
static
Initial value:
=
BlossomGraph::EdgeIndex(-1)

Definition at line 176 of file perfect_matching.h.

◆ kNoNodeIndex

const BlossomGraph::NodeIndex kNoNodeIndex
static
Initial value:

Definition at line 175 of file perfect_matching.h.


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