operations_research::BlossomGraph Class Reference

Detailed Description

Definition at line 165 of file perfect_matching.h.

#include <perfect_matching.h>

Classes
struct	Node
struct	Edge

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

operations_research::BlossomGraph::BlossomGraph ( int num_nodes )

explicit

Definition at line 130 of file perfect_matching.cc.

Member Function Documentation

AddEdge()

void operations_research::BlossomGraph::AddEdge	(	NodeIndex	tail,
		NodeIndex	head,
		CostValue	cost )

Definition at line 140 of file perfect_matching.cc.

Augment()

void operations_research::BlossomGraph::Augment

(

EdgeIndex

e

)

Definition at line 561 of file perfect_matching.cc.

ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue()

CostValue operations_research::BlossomGraph::ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue

(

)

Definition at line 273 of file perfect_matching.cc.

DebugCheckNoPossiblePrimalUpdates()

void operations_research::BlossomGraph::DebugCheckNoPossiblePrimalUpdates

(

)

Definition at line 361 of file perfect_matching.cc.

DebugDualsAreFeasible()

bool operations_research::BlossomGraph::DebugDualsAreFeasible

(

)

const

Definition at line 464 of file perfect_matching.cc.

DebugEdgeIsTightAndExternal()

bool operations_research::BlossomGraph::DebugEdgeIsTightAndExternal

(

const Edge &

edge

)

const

Definition at line 477 of file perfect_matching.cc.

DebugString()

std::string operations_research::BlossomGraph::DebugString

(

)

const

Definition at line 1217 of file perfect_matching.cc.

DebugUpdateNodeDual()

void operations_research::BlossomGraph::DebugUpdateNodeDual	(	NodeIndex	n,
		CostValue	delta )

Definition at line 1228 of file perfect_matching.cc.

DEFINE_INT_TYPE() [1/3]

operations_research::BlossomGraph::DEFINE_INT_TYPE	(	CostValue	,
		int64_t	)

DEFINE_INT_TYPE() [2/3]

operations_research::BlossomGraph::DEFINE_INT_TYPE	(	EdgeIndex	,
		int	)

DEFINE_INT_TYPE() [3/3]

operations_research::BlossomGraph::DEFINE_INT_TYPE	(	NodeIndex	,
		int	)

DisplayStats()

void operations_research::BlossomGraph::DisplayStats

(

)

const

Definition at line 1281 of file perfect_matching.cc.

Dual()

CostValue operations_research::BlossomGraph::Dual

(

const Node &

node

)

const

Definition at line 1260 of file perfect_matching.cc.

DualObjective()

CostValue operations_research::BlossomGraph::DualObjective

(

)

const

Definition at line 1269 of file perfect_matching.cc.

EdgeDebugString()

std::string operations_research::BlossomGraph::EdgeDebugString

(

EdgeIndex

e

)

const

Definition at line 1207 of file perfect_matching.cc.

Expand()

void operations_research::BlossomGraph::Expand

(

NodeIndex

to_expand

)

Definition at line 859 of file perfect_matching.cc.

ExpandAllBlossoms()

void operations_research::BlossomGraph::ExpandAllBlossoms

(

)

Definition at line 1068 of file perfect_matching.cc.

GetEdge()

const Edge & operations_research::BlossomGraph::GetEdge ( int e ) const

inline

Definition at line 390 of file perfect_matching.h.

GetNode()

const Node & operations_research::BlossomGraph::GetNode ( int n ) const

inline

Definition at line 391 of file perfect_matching.h.

Grow()

void operations_research::BlossomGraph::Grow	(	EdgeIndex	e,
		NodeIndex	tail,
		NodeIndex	head )

Definition at line 484 of file perfect_matching.cc.

Initialize()

bool operations_research::BlossomGraph::Initialize

(

)

Definition at line 157 of file perfect_matching.cc.

Match()

NodeIndex operations_research::BlossomGraph::Match

(

NodeIndex

n

)

const

Definition at line 350 of file perfect_matching.cc.

NodeDebugString()

std::string operations_research::BlossomGraph::NodeDebugString

(

NodeIndex

n

)

const

Definition at line 1191 of file perfect_matching.cc.

NodeIsMatched()

bool operations_research::BlossomGraph::NodeIsMatched

(

NodeIndex

n

)

const

Definition at line 343 of file perfect_matching.cc.

NumMatched()

int operations_research::BlossomGraph::NumMatched ( ) const

inline

Definition at line 352 of file perfect_matching.h.

PrimalUpdates()

void operations_research::BlossomGraph::PrimalUpdates

(

)

Definition at line 395 of file perfect_matching.cc.

Shrink()

void operations_research::BlossomGraph::Shrink

(

EdgeIndex

e

)

Definition at line 664 of file perfect_matching.cc.

Slack()

CostValue operations_research::BlossomGraph::Slack

(

const Edge &

edge

)

const

Definition at line 1242 of file perfect_matching.cc.

UpdateAllTrees()

void operations_research::BlossomGraph::UpdateAllTrees

(

CostValue

delta

)

Definition at line 323 of file perfect_matching.cc.

Member Data Documentation

kMaxCostValue

const BlossomGraph::CostValue operations_research::BlossomGraph::kMaxCostValue

static

Initial value:

=
    BlossomGraph::CostValue(std::numeric_limits<int64_t>::max())

Definition at line 177 of file perfect_matching.h.

kNoEdgeIndex

const BlossomGraph::EdgeIndex operations_research::BlossomGraph::kNoEdgeIndex

static

Initial value:

=
    BlossomGraph::EdgeIndex(-1)

Definition at line 176 of file perfect_matching.h.

kNoNodeIndex

const BlossomGraph::NodeIndex operations_research::BlossomGraph::kNoNodeIndex

static

Initial value:

=
    BlossomGraph::NodeIndex(-1)

Definition at line 175 of file perfect_matching.h.

---

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

• ortools/graph/perfect_matching.h
• ortools/graph/perfect_matching.cc