Helper class for the blossom matching algorithms. More...

#include <ogdf/graphalg/matching_blossom/AlternatingTree.h>

Public Member Functions
	BlossomHelper (bool greedyInit)
	Construct a new Blossom V Helper object. More...

	~BlossomHelper ()

void	addPseudonode (Pseudonode *pseudonode)
	Adds a pseudonode to the current representation structure. More...

void	addToMatching (edge e)
	Adds the edge `e` to the matching. More...

TWeight &	c (edge e)
	Returns the base edge weight of `e`. More...

void	expandRepr (Pseudonode *pseudonode)
	Expands a pseudonode in the current representation structure. More...

node	getBaseNode (edge e, node v)
	Returns the original end point of `e` which is currently represented by `v`. More...

std::pair< node, node >	getBaseNodes (edge e, node v=nullptr)
	Return both original end points of `e` where the first end point is currently represented by `v`. More...

node	getOppositeBaseNode (edge e, node v)
	Returns the original end point of `e` where the other end point is currently represented by `v`. More...

void	getOriginalMatching (std::unordered_set< edge > &matching)
	Fills `matching` with the original edges which correspond to the edges in m_matching after expanding it with the correct edges currently contracted in blossoms. More...

virtual TWeight	getRealReducedWeight (edge e)
	Returns the real reduced weight. Can be overridden by subclasses to consider additional factors. More...

TWeight	getReducedWeight (edge e)
	Returns the reduced weight of `e`, taking into account the y values of the endpoints. More...

GraphCopySimple &	graph ()

template<class WeightContainer >
bool	init (const Graph &graph, const WeightContainer &weights)
	Reinitialize the helper class with a new graph and edge weights. Resets all helper members. Returns false if the graph cannot have a perfect matching. More...

virtual bool	isEqualityEdge (edge e)
	Checks whether `e` is an equality edge, i.e. the reduced weight is 0. More...

bool	isPseudonode (node v)
	Checks whether `v` is a pseudonode. More...

bool	isZero (TWeight x)
	Helper function to determine whether a floating point value is 0. More...

bool	isZeroCostNode (node v)
	Checks whether `v` is a zero-cost node, i.e. the y value is 0. More...

NodeArray< edge > &	matching ()

edge &	matching (node v)
	Returns the matching edge of `v`, or nullptr if `v` is not matched. More...

Pseudonode *	pseudonode (node v)
	Returns the pseudonode corresponding to `v`, or nullptr if `v` is not a pseudonode. More...

std::unordered_map< node, Pseudonode * > &	pseudonodes ()

void	removePseudonode (Pseudonode *pseudonode)
	Removes a pseudonode from the current representation structure. More...

node	repr (node v)
	Returns the representative of `v` in the tree induced by the pseudonodes. More...

node	reprChild (node v)
	Returns the child of the representative of `v` in the tree induced by the pseudonodes. More...

TWeight &	y (node v)
	Returns the base y value of `v`. More...

Protected Member Functions
void	deletePseudonodes ()
	Deletes all pseudonodes. More...

node	findParentInRepr (node v, node child=nullptr)
	Finds the parent of `v` in the tree induced by the pseudonodes. More...

bool	initDualSolution (NodeArray< TWeight > &minY)
	Initializes the dual solution with the given y values. More...

Protected Attributes
EdgeArray< TWeight >	m_c
	LP-induced data used by the algorithm. More...

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

GraphCopySimple	m_graph
	A copy of the graph to work on. More...

bool	m_greedyInit
	Whether or not to use the greedy initialization. More...

NodeArray< edge >	m_matching
	The current matching, mapping both endpoints to the corresponding matching edge. More...

std::unordered_map< node, Pseudonode * >	m_pseudonodes
	A mapping of all pseudonodes in the graph. More...

std::vector< node >	m_repr
	The tree induced by the pseudonodes, mapping each node index to its parent. More...

std::vector< node >	m_shortcuts
	A shortcut array for the tree, mapping each node index to the penultimate node. More...

NodeArray< TWeight >	m_y

Static Protected Attributes
static const int	WEIGHT_FACTOR = std::numeric_limits<TWeight>::is_integer ? 4 : 1

Detailed Description

template<class TWeight>
class ogdf::matching_blossom::BlossomHelper< TWeight >

Helper class for the blossom matching algorithms.

Definition at line 52 of file AlternatingTree.h.

Constructor & Destructor Documentation

◆ BlossomHelper()

template<class TWeight >

ogdf::matching_blossom::BlossomHelper< TWeight >::BlossomHelper ( bool greedyInit )

inline

Construct a new Blossom V Helper object.

Parameters

greedyInit whether or not to use the greedy initialization

Definition at line 190 of file BlossomHelper.h.

◆ ~BlossomHelper()

template<class TWeight >

ogdf::matching_blossom::BlossomHelper< TWeight >::~BlossomHelper ( )

inline

Definition at line 192 of file BlossomHelper.h.

Member Function Documentation

◆ addPseudonode()

template<class TWeight >

void ogdf::matching_blossom::BlossomHelper< TWeight >::addPseudonode ( Pseudonode * pseudonode )

inline

Adds a pseudonode to the current representation structure.

Definition at line 285 of file BlossomHelper.h.

◆ addToMatching()

template<class TWeight >

void ogdf::matching_blossom::BlossomHelper< TWeight >::addToMatching ( edge e )

inline

Adds the edge e to the matching.

Definition at line 399 of file BlossomHelper.h.

◆ c()

template<class TWeight >

TWeight& ogdf::matching_blossom::BlossomHelper< TWeight >::c ( edge e )

inline

Returns the base edge weight of e.

Definition at line 236 of file BlossomHelper.h.

◆ deletePseudonodes()

template<class TWeight >

void ogdf::matching_blossom::BlossomHelper< TWeight >::deletePseudonodes ( )

inlineprotected

Deletes all pseudonodes.

Definition at line 159 of file BlossomHelper.h.

◆ expandRepr()

template<class TWeight >

void ogdf::matching_blossom::BlossomHelper< TWeight >::expandRepr ( Pseudonode * pseudonode )

inline

Expands a pseudonode in the current representation structure.

Definition at line 308 of file BlossomHelper.h.

◆ findParentInRepr()

template<class TWeight >

node ogdf::matching_blossom::BlossomHelper< TWeight >::findParentInRepr	(	node	v,
		node	child = `nullptr`
	)

inlineprotected

Finds the parent of v in the tree induced by the pseudonodes.

Definition at line 146 of file BlossomHelper.h.

◆ getBaseNode()

template<class TWeight >

node ogdf::matching_blossom::BlossomHelper< TWeight >::getBaseNode	(	edge	e,
		node	v
	)

inline

Returns the original end point of e which is currently represented by v.

Definition at line 316 of file BlossomHelper.h.

◆ getBaseNodes()

template<class TWeight >

std::pair<node, node> ogdf::matching_blossom::BlossomHelper< TWeight >::getBaseNodes	(	edge	e,
		node	v = `nullptr`
	)

inline

Return both original end points of e where the first end point is currently represented by v.

Definition at line 322 of file BlossomHelper.h.

◆ getOppositeBaseNode()

template<class TWeight >

node ogdf::matching_blossom::BlossomHelper< TWeight >::getOppositeBaseNode	(	edge	e,
		node	v
	)

inline

Returns the original end point of e where the other end point is currently represented by v.

Definition at line 319 of file BlossomHelper.h.

◆ getOriginalMatching()

template<class TWeight >

void ogdf::matching_blossom::BlossomHelper< TWeight >::getOriginalMatching ( std::unordered_set< edge > & matching )

inline

Fills matching with the original edges which correspond to the edges in m_matching after expanding it with the correct edges currently contracted in blossoms.

Definition at line 351 of file BlossomHelper.h.

◆ getRealReducedWeight()

template<class TWeight >

virtual TWeight ogdf::matching_blossom::BlossomHelper< TWeight >::getRealReducedWeight ( edge e )

inlinevirtual

Returns the real reduced weight. Can be overridden by subclasses to consider additional factors.

Definition at line 341 of file BlossomHelper.h.

◆ getReducedWeight()

template<class TWeight >

TWeight ogdf::matching_blossom::BlossomHelper< TWeight >::getReducedWeight ( edge e )

inline

Returns the reduced weight of e, taking into account the y values of the endpoints.

Definition at line 338 of file BlossomHelper.h.

◆ graph()

template<class TWeight >

GraphCopySimple& ogdf::matching_blossom::BlossomHelper< TWeight >::graph ( )

inline

Definition at line 233 of file BlossomHelper.h.

◆ init()

template<class TWeight >

template<class WeightContainer >

bool ogdf::matching_blossom::BlossomHelper< TWeight >::init	(	const Graph &	graph,
		const WeightContainer &	weights
	)

inline

Reinitialize the helper class with a new graph and edge weights. Resets all helper members. Returns false if the graph cannot have a perfect matching.

Definition at line 197 of file BlossomHelper.h.

◆ initDualSolution()

template<class TWeight >

bool ogdf::matching_blossom::BlossomHelper< TWeight >::initDualSolution ( NodeArray< TWeight > & minY )

inlineprotected

Initializes the dual solution with the given y values.

Definition at line 91 of file BlossomHelper.h.

◆ isEqualityEdge()

template<class TWeight >

virtual bool ogdf::matching_blossom::BlossomHelper< TWeight >::isEqualityEdge ( edge e )

inlinevirtual

Checks whether e is an equality edge, i.e. the reduced weight is 0.

Definition at line 344 of file BlossomHelper.h.

◆ isPseudonode()

template<class TWeight >

bool ogdf::matching_blossom::BlossomHelper< TWeight >::isPseudonode ( node v )

inline

Checks whether v is a pseudonode.

Definition at line 252 of file BlossomHelper.h.

◆ isZero()

template<class TWeight >

bool ogdf::matching_blossom::BlossomHelper< TWeight >::isZero ( TWeight x )

inline

Helper function to determine whether a floating point value is 0.

Definition at line 335 of file BlossomHelper.h.

◆ isZeroCostNode()

template<class TWeight >

bool ogdf::matching_blossom::BlossomHelper< TWeight >::isZeroCostNode ( node v )

inline

Checks whether v is a zero-cost node, i.e. the y value is 0.

Definition at line 347 of file BlossomHelper.h.

◆ matching() [1/2]

template<class TWeight >

NodeArray<edge>& ogdf::matching_blossom::BlossomHelper< TWeight >::matching ( )

inline

Definition at line 241 of file BlossomHelper.h.

◆ matching() [2/2]

template<class TWeight >

edge& ogdf::matching_blossom::BlossomHelper< TWeight >::matching ( node v )

inline

Returns the matching edge of v, or nullptr if v is not matched.

Definition at line 244 of file BlossomHelper.h.

◆ pseudonode()

template<class TWeight >

Pseudonode* ogdf::matching_blossom::BlossomHelper< TWeight >::pseudonode ( node v )

inline

Returns the pseudonode corresponding to v, or nullptr if v is not a pseudonode.

Definition at line 249 of file BlossomHelper.h.

◆ pseudonodes()

template<class TWeight >

std::unordered_map<node, Pseudonode*>& ogdf::matching_blossom::BlossomHelper< TWeight >::pseudonodes ( )

inline

Definition at line 246 of file BlossomHelper.h.

◆ removePseudonode()

template<class TWeight >

void ogdf::matching_blossom::BlossomHelper< TWeight >::removePseudonode ( Pseudonode * pseudonode )

inline

Removes a pseudonode from the current representation structure.

Definition at line 296 of file BlossomHelper.h.

◆ repr()

template<class TWeight >

node ogdf::matching_blossom::BlossomHelper< TWeight >::repr ( node v )

inline

Returns the representative of v in the tree induced by the pseudonodes.

Definition at line 257 of file BlossomHelper.h.

◆ reprChild()

template<class TWeight >

node ogdf::matching_blossom::BlossomHelper< TWeight >::reprChild ( node v )

inline

Returns the child of the representative of v in the tree induced by the pseudonodes.

Definition at line 272 of file BlossomHelper.h.

◆ y()

template<class TWeight >

TWeight& ogdf::matching_blossom::BlossomHelper< TWeight >::y ( node v )

inline

Returns the base y value of v.

Definition at line 239 of file BlossomHelper.h.

Member Data Documentation

◆ m_c

template<class TWeight >

EdgeArray<TWeight> ogdf::matching_blossom::BlossomHelper< TWeight >::m_c

protected

LP-induced data used by the algorithm.

Definition at line 69 of file BlossomHelper.h.

◆ m_eps

template<class TWeight >

EpsilonTest ogdf::matching_blossom::BlossomHelper< TWeight >::m_eps

protected

The epsilon test used for floating point comparisons.

Definition at line 85 of file BlossomHelper.h.

◆ m_graph

template<class TWeight >

GraphCopySimple ogdf::matching_blossom::BlossomHelper< TWeight >::m_graph

protected

A copy of the graph to work on.

Definition at line 66 of file BlossomHelper.h.

◆ m_greedyInit

template<class TWeight >

bool ogdf::matching_blossom::BlossomHelper< TWeight >::m_greedyInit

protected

Whether or not to use the greedy initialization.

Definition at line 63 of file BlossomHelper.h.

◆ m_matching

template<class TWeight >

NodeArray<edge> ogdf::matching_blossom::BlossomHelper< TWeight >::m_matching

protected

The current matching, mapping both endpoints to the corresponding matching edge.

Definition at line 73 of file BlossomHelper.h.

◆ m_pseudonodes

template<class TWeight >

std::unordered_map<node, Pseudonode*> ogdf::matching_blossom::BlossomHelper< TWeight >::m_pseudonodes

protected

A mapping of all pseudonodes in the graph.

Definition at line 76 of file BlossomHelper.h.

◆ m_repr

template<class TWeight >

std::vector<node> ogdf::matching_blossom::BlossomHelper< TWeight >::m_repr

protected

The tree induced by the pseudonodes, mapping each node index to its parent.

Definition at line 79 of file BlossomHelper.h.

◆ m_shortcuts

template<class TWeight >

std::vector<node> ogdf::matching_blossom::BlossomHelper< TWeight >::m_shortcuts

protected

A shortcut array for the tree, mapping each node index to the penultimate node.

Definition at line 82 of file BlossomHelper.h.

◆ m_y

template<class TWeight >

NodeArray<TWeight> ogdf::matching_blossom::BlossomHelper< TWeight >::m_y

protected

Definition at line 70 of file BlossomHelper.h.

◆ WEIGHT_FACTOR

template<class TWeight >

const int ogdf::matching_blossom::BlossomHelper< TWeight >::WEIGHT_FACTOR = std::numeric_limits<TWeight>::is_integer ? 4 : 1

staticprotected

Definition at line 88 of file BlossomHelper.h.

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

include/ogdf/graphalg/matching_blossom/AlternatingTree.h
include/ogdf/graphalg/matching_blossom/BlossomHelper.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

template<class TWeight> class ogdf::matching_blossom::BlossomHelper< TWeight >

Constructor & Destructor Documentation

◆ BlossomHelper()

◆ ~BlossomHelper()

Member Function Documentation

◆ addPseudonode()

◆ addToMatching()

◆ c()

◆ deletePseudonodes()

◆ expandRepr()

◆ findParentInRepr()

◆ getBaseNode()

◆ getBaseNodes()

◆ getOppositeBaseNode()

◆ getOriginalMatching()

◆ getRealReducedWeight()

◆ getReducedWeight()

◆ graph()

◆ init()

◆ initDualSolution()

◆ isEqualityEdge()

◆ isPseudonode()

◆ isZero()

◆ isZeroCostNode()

◆ matching() [1/2]

◆ matching() [2/2]

◆ pseudonode()

◆ pseudonodes()

◆ removePseudonode()

◆ repr()

◆ reprChild()

◆ y()

Member Data Documentation

◆ m_c

◆ m_eps

◆ m_graph

◆ m_greedyInit

◆ m_matching

◆ m_pseudonodes

◆ m_repr

◆ m_shortcuts

◆ m_y

◆ WEIGHT_FACTOR

Open
Graph Drawing
Framework

template<class TWeight>
class ogdf::matching_blossom::BlossomHelper< TWeight >