Implementation of the Blossom-V algorithm by Kolmogorov (2009) for Minimum Weight Perfect Matching. More...

#include <ogdf/graphalg/MatchingBlossomV.h>

Classes
struct	stats
	Structure to store statistics. More...

Public Member Functions
	MatchingBlossomV (bool greedyInit=true)
	Construct a MatchingBlossomV instance. More...

Private Member Functions
template<class WeightContainer >
bool	_doCall (const Graph &G, const WeightContainer &weights, std::unordered_set< edge > &matching)
	Helper for the main call function since abstract functions cannot be templated. More...

void	advanceCurrentAuxNode ()
	Helper function to advance the current aux node to the next one. More...

void	augment (edge augmentationEdge)
	Augment the matching with `augmentationEdge`. More...

bool	doCall (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching)

bool	doCall (const GraphAttributes &GA, std::unordered_set< edge > &matching)

bool	dualChange ()
	Executes a dual change step. More...

long long	end (std::chrono::high_resolution_clock::time_point start)
	Get the time difference between `start` and now in nanoseconds. More...

void	expand (Pseudonode *pseudonode)
	Expand the given `pseudonode`. More...

bool	findExpandablePseudonode (AuxNode< TWeight > *auxNode)
	Finds and expands an odd pseudonode in `auxNode`, if possible. More...

bool	findMatching (std::unordered_set< edge > &matching)
	Main function of the algorithm. More...

bool	findMatchingAugmentation (AuxNode< TWeight > *auxNode)
	Finds and executes a matching augmentation in `auxNode`, if possible. More...

bool	findShrinkableCycle (AuxNode< TWeight > *auxNode)
	Finds and shrinks an odd cycle in `auxNode`, if possible. More...

bool	findTreeAugmentation (AuxNode< TWeight > *auxNode)
	Finds and executes a tree augmentation in `auxNode`, if possible. More...

void	grow (edge newEdge)
	Augment the corresponding tree with `augmentationEdge`. More...

std::ostream &	lout (Level level=Level::Default, bool indent=true) const
	stream for logging-output (local) More...

std::ostream &	louth ()
	Helper function to log with high priority. More...

std::chrono::high_resolution_clock::time_point	now ()
	Get the current time point. More...

bool	primalChange ()
	Executes a primal change step. More...

void	printParallelEdgesStats ()
	Print additional statistics about parallel edges. More...

void	printStatistics ()
	Print all statistics. More...

long long	processStatisticEntry (const std::string &key)
	Print a single statistics entry. More...

void	shrink (edge cycleEdge)
	Shrink the odd cycle induced by `cycleEdge` and the tree determined by its endpoints. More...

Private Attributes
AuxGraph< TWeight >	m_auxGraph

AuxNode< TWeight > *	m_currentAuxNode = nullptr
	The current aux node in the main loop. More...

EpsilonTest	m_eps
	The epsilon test for floating point comparisons. More...

BlossomVHelper< TWeight >	m_helper

std::unordered_map< std::string, stats >	m_stats
	A mapping of all statistic names to their values. More...

Detailed Description

template<typename TWeight>
class ogdf::MatchingBlossomV< TWeight >

Implementation of the Blossom-V algorithm by Kolmogorov (2009) for Minimum Weight Perfect Matching.

Definition at line 64 of file MatchingBlossomV.h.

Constructor & Destructor Documentation

◆ MatchingBlossomV()

template<typename TWeight >

ogdf::MatchingBlossomV< TWeight >::MatchingBlossomV ( bool greedyInit = true )

inline

Construct a MatchingBlossomV instance.

Parameters

greedyInit whether or not to use the greedy initialization

Definition at line 283 of file MatchingBlossomV.h.

Member Function Documentation

◆ _doCall()

template<typename TWeight >

template<class WeightContainer >

bool ogdf::MatchingBlossomV< TWeight >::_doCall	(	const Graph &	G,
		const WeightContainer &	weights,
		std::unordered_set< edge > &	matching
	)

inlineprivate

Helper for the main call function since abstract functions cannot be templated.

Definition at line 297 of file MatchingBlossomV.h.

◆ advanceCurrentAuxNode()

template<typename TWeight >

void ogdf::MatchingBlossomV< TWeight >::advanceCurrentAuxNode ( )

inlineprivate

Helper function to advance the current aux node to the next one.

Definition at line 137 of file MatchingBlossomV.h.

◆ augment()

template<typename TWeight >

void ogdf::MatchingBlossomV< TWeight >::augment ( edge augmentationEdge )

inlineprivate

Augment the matching with augmentationEdge.

Definition at line 548 of file MatchingBlossomV.h.

◆ doCall() [1/2]

template<typename TWeight >

bool ogdf::MatchingBlossomV< TWeight >::doCall	(	const Graph &	G,
		const EdgeArray< TWeight > &	weights,
		std::unordered_set< edge > &	matching
	)

inlineprivate

Definition at line 286 of file MatchingBlossomV.h.

◆ doCall() [2/2]

template<typename TWeight >

bool ogdf::MatchingBlossomV< TWeight >::doCall	(	const GraphAttributes &	GA,
		std::unordered_set< edge > &	matching
	)

inlineprivate

Definition at line 291 of file MatchingBlossomV.h.

◆ dualChange()

template<typename TWeight >

bool ogdf::MatchingBlossomV< TWeight >::dualChange ( )

inlineprivate

Executes a dual change step.

Definition at line 476 of file MatchingBlossomV.h.

◆ end()

template<typename TWeight >

long long ogdf::MatchingBlossomV< TWeight >::end ( std::chrono::high_resolution_clock::time_point start )

inlineprivate

Get the time difference between start and now in nanoseconds.

Definition at line 125 of file MatchingBlossomV.h.

◆ expand()

template<typename TWeight >

void ogdf::MatchingBlossomV< TWeight >::expand ( Pseudonode * pseudonode )

inlineprivate

Expand the given pseudonode.

Definition at line 776 of file MatchingBlossomV.h.

◆ findExpandablePseudonode()

template<typename TWeight >

bool ogdf::MatchingBlossomV< TWeight >::findExpandablePseudonode ( AuxNode< TWeight > * auxNode )

inlineprivate

Finds and expands an odd pseudonode in auxNode, if possible.

Returns: whether a pseudonode was expanded

Definition at line 461 of file MatchingBlossomV.h.

◆ findMatching()

template<typename TWeight >

bool ogdf::MatchingBlossomV< TWeight >::findMatching ( std::unordered_set< edge > & matching )

inlineprivate

Main function of the algorithm.

Finds a minimum weight perfect matching in the graph if one exists.

Returns: whether a matching was found

Definition at line 321 of file MatchingBlossomV.h.

◆ findMatchingAugmentation()

template<typename TWeight >

bool ogdf::MatchingBlossomV< TWeight >::findMatchingAugmentation ( AuxNode< TWeight > * auxNode )

inlineprivate

Finds and executes a matching augmentation in auxNode, if possible.

Returns: whether the matching was augmented

Definition at line 399 of file MatchingBlossomV.h.

◆ findShrinkableCycle()

template<typename TWeight >

bool ogdf::MatchingBlossomV< TWeight >::findShrinkableCycle ( AuxNode< TWeight > * auxNode )

inlineprivate

Finds and shrinks an odd cycle in auxNode, if possible.

Returns: whether a cycle was shrunken

Definition at line 444 of file MatchingBlossomV.h.

◆ findTreeAugmentation()

template<typename TWeight >

bool ogdf::MatchingBlossomV< TWeight >::findTreeAugmentation ( AuxNode< TWeight > * auxNode )

inlineprivate

Finds and executes a tree augmentation in auxNode, if possible.

Returns: whether the tree was augmented

Definition at line 427 of file MatchingBlossomV.h.

◆ grow()

template<typename TWeight >

void ogdf::MatchingBlossomV< TWeight >::grow ( edge newEdge )

inlineprivate

Augment the corresponding tree with augmentationEdge.

Definition at line 585 of file MatchingBlossomV.h.

◆ lout()

template<typename TWeight >

std::ostream& ogdf::Logger::lout

inlineprivate

stream for logging-output (local)

Definition at line 160 of file Logger.h.

◆ louth()

template<typename TWeight >

std::ostream& ogdf::MatchingBlossomV< TWeight >::louth ( )

inlineprivate

Helper function to log with high priority.

Definition at line 134 of file MatchingBlossomV.h.

◆ now()

template<typename TWeight >

std::chrono::high_resolution_clock::time_point ogdf::MatchingBlossomV< TWeight >::now ( )

inlineprivate

Get the current time point.

Definition at line 120 of file MatchingBlossomV.h.

◆ primalChange()

template<typename TWeight >

bool ogdf::MatchingBlossomV< TWeight >::primalChange ( )

inlineprivate

Executes a primal change step.

Definition at line 366 of file MatchingBlossomV.h.

◆ printParallelEdgesStats()

template<typename TWeight >

void ogdf::MatchingBlossomV< TWeight >::printParallelEdgesStats ( )

inlineprivate

Print additional statistics about parallel edges.

Definition at line 901 of file MatchingBlossomV.h.

◆ printStatistics()

template<typename TWeight >

void ogdf::MatchingBlossomV< TWeight >::printStatistics ( )

inlineprivate

Print all statistics.

Definition at line 872 of file MatchingBlossomV.h.

◆ processStatisticEntry()

template<typename TWeight >

long long ogdf::MatchingBlossomV< TWeight >::processStatisticEntry ( const std::string & key )

inlineprivate

Print a single statistics entry.

Definition at line 929 of file MatchingBlossomV.h.

◆ shrink()

template<typename TWeight >

void ogdf::MatchingBlossomV< TWeight >::shrink ( edge cycleEdge )

inlineprivate

Shrink the odd cycle induced by cycleEdge and the tree determined by its endpoints.

Definition at line 657 of file MatchingBlossomV.h.

Member Data Documentation

◆ m_auxGraph

template<typename TWeight >

AuxGraph<TWeight> ogdf::MatchingBlossomV< TWeight >::m_auxGraph

private

Definition at line 94 of file MatchingBlossomV.h.

◆ m_currentAuxNode

template<typename TWeight >

AuxNode<TWeight>* ogdf::MatchingBlossomV< TWeight >::m_currentAuxNode = nullptr

private

The current aux node in the main loop.

Definition at line 97 of file MatchingBlossomV.h.

◆ m_eps

template<typename TWeight >

EpsilonTest ogdf::MatchingBlossomV< TWeight >::m_eps

private

The epsilon test for floating point comparisons.

Definition at line 100 of file MatchingBlossomV.h.

◆ m_helper

template<typename TWeight >

BlossomVHelper<TWeight> ogdf::MatchingBlossomV< TWeight >::m_helper

private

Definition at line 93 of file MatchingBlossomV.h.

◆ m_stats

template<typename TWeight >

std::unordered_map<std::string, stats> ogdf::MatchingBlossomV< TWeight >::m_stats

private

A mapping of all statistic names to their values.

Definition at line 117 of file MatchingBlossomV.h.

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

include/ogdf/graphalg/MatchingBlossomV.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename TWeight> class ogdf::MatchingBlossomV< TWeight >

Constructor & Destructor Documentation

◆ MatchingBlossomV()

Member Function Documentation

◆ _doCall()

◆ advanceCurrentAuxNode()

◆ augment()

◆ doCall() [1/2]

◆ doCall() [2/2]

◆ dualChange()

◆ end()

◆ expand()

◆ findExpandablePseudonode()

◆ findMatching()

◆ findMatchingAugmentation()

◆ findShrinkableCycle()

◆ findTreeAugmentation()

◆ grow()

◆ lout()

◆ louth()

◆ now()

◆ primalChange()

◆ printParallelEdgesStats()

◆ printStatistics()

◆ processStatisticEntry()

◆ shrink()

Member Data Documentation

◆ m_auxGraph

◆ m_currentAuxNode

◆ m_eps

◆ m_helper

◆ m_stats

Open
Graph Drawing
Framework

template<typename TWeight>
class ogdf::MatchingBlossomV< TWeight >