OR-Tools  9.6
Classes | Public Member Functions | Static Public Attributes | List of all members
BlossomGraph

Detailed Description

Definition at line 170 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_t)
 
 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 Edge & GetEdge (int e) const
 
const Node & GetNode (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 125 of file perfect_matching.cc.

Member Function Documentation

◆ AddEdge()

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

Definition at line 135 of file perfect_matching.cc.

◆ Augment()

void Augment ( EdgeIndex  e)

Definition at line 556 of file perfect_matching.cc.

◆ ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue()

CostValue ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue ( )

Definition at line 268 of file perfect_matching.cc.

◆ DebugCheckNoPossiblePrimalUpdates()

void DebugCheckNoPossiblePrimalUpdates ( )

Definition at line 356 of file perfect_matching.cc.

◆ DebugDualsAreFeasible()

bool DebugDualsAreFeasible ( ) const

Definition at line 459 of file perfect_matching.cc.

◆ DebugEdgeIsTightAndExternal()

bool DebugEdgeIsTightAndExternal ( const Edge &  edge) const

Definition at line 472 of file perfect_matching.cc.

◆ DebugString()

std::string DebugString ( ) const

Definition at line 1212 of file perfect_matching.cc.

◆ DebugUpdateNodeDual()

void DebugUpdateNodeDual ( NodeIndex  n,
CostValue  delta 
)

Definition at line 1223 of file perfect_matching.cc.

◆ DEFINE_INT_TYPE() [1/3]

DEFINE_INT_TYPE ( CostValue  ,
int64_t   
)

◆ 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 1276 of file perfect_matching.cc.

◆ Dual()

CostValue Dual ( const Node &  node) const

Definition at line 1255 of file perfect_matching.cc.

◆ DualObjective()

CostValue DualObjective ( ) const

Definition at line 1264 of file perfect_matching.cc.

◆ EdgeDebugString()

std::string EdgeDebugString ( EdgeIndex  e) const

Definition at line 1202 of file perfect_matching.cc.

◆ Expand()

void Expand ( NodeIndex  to_expand)

Definition at line 854 of file perfect_matching.cc.

◆ ExpandAllBlossoms()

void ExpandAllBlossoms ( )

Definition at line 1063 of file perfect_matching.cc.

◆ GetEdge()

const Edge& GetEdge ( int  e) const
inline

Definition at line 395 of file perfect_matching.h.

◆ GetNode()

const Node& GetNode ( int  n) const
inline

Definition at line 396 of file perfect_matching.h.

◆ Grow()

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

Definition at line 479 of file perfect_matching.cc.

◆ Initialize()

bool Initialize ( )

Definition at line 152 of file perfect_matching.cc.

◆ Match()

NodeIndex Match ( NodeIndex  n) const

Definition at line 345 of file perfect_matching.cc.

◆ NodeDebugString()

std::string NodeDebugString ( NodeIndex  n) const

Definition at line 1186 of file perfect_matching.cc.

◆ NodeIsMatched()

bool NodeIsMatched ( NodeIndex  n) const

Definition at line 338 of file perfect_matching.cc.

◆ NumMatched()

int NumMatched ( ) const
inline

Definition at line 357 of file perfect_matching.h.

◆ PrimalUpdates()

void PrimalUpdates ( )

Definition at line 390 of file perfect_matching.cc.

◆ Shrink()

void Shrink ( EdgeIndex  e)

Definition at line 659 of file perfect_matching.cc.

◆ Slack()

CostValue Slack ( const Edge &  edge) const

Definition at line 1237 of file perfect_matching.cc.

◆ UpdateAllTrees()

void UpdateAllTrees ( CostValue  delta)

Definition at line 318 of file perfect_matching.cc.

Member Data Documentation

◆ kMaxCostValue

const BlossomGraph::CostValue kMaxCostValue
static
Initial value:
=
BlossomGraph::CostValue(std::numeric_limits<int64_t>::max())
max
int64_t max
Definition: alldiff_cst.cc:140
operations_research::CostValue
int64_t CostValue
Definition: ebert_graph.h:204

Definition at line 182 of file perfect_matching.h.

◆ kNoEdgeIndex

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

Definition at line 181 of file perfect_matching.h.

◆ kNoNodeIndex

const BlossomGraph::NodeIndex kNoNodeIndex
static
Initial value:
=
BlossomGraph::NodeIndex(-1)
operations_research::NodeIndex
int32_t NodeIndex
Definition: ebert_graph.h:193

Definition at line 180 of file perfect_matching.h.

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