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

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

Inheritance diagram for ogdf::matching_blossom::BlossomVHelper< TWeight >:

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

TWeight	getRealReducedWeight (edge e) override
	Gets the actual reduced weight of the edge, taking into account the delta of the corresponding trees.

template<class E >
TWeight	getRealTopPriority (BlossomPQ< E, TWeight > &pq)
	Returns the real value (realReducedWeight or realY) of the top element in the priority queue, or infinity if the queue is empty.

template<class E >
E	getTopEligibleElement (BlossomPQ< E, TWeight > &pq)
	Checks if the top element of the given `pq` has realValue == 0 and returns it, if possible.

template<class WeightContainer >
bool	init (const Graph &graph, const WeightContainer &weights, AuxGraph< TWeight > *auxGraph)
	Initialize the helper with the given data.

bool	isZeroCostNode (node v)
	Checks if the realValue of `b` is zero.

TWeight	realValue (edge e)
	Returns the realReducedWeight of `e`.

TWeight	realValue (node v)
	Returns the realY of `v`.

TWeight	realY (node v)
	Returns the actual y value of the node, taking into account the delta of the corresponding tree.

Public Member Functions inherited from ogdf::matching_blossom::BlossomHelper< TWeight >
	BlossomHelper (bool greedyInit)
	Construct a new Blossom V Helper object.

	~BlossomHelper ()

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

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

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

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

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

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`.

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

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.

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

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.

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

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

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

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

NodeArray< edge > &	matching ()

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

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

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

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

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

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

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

Public Attributes
long	currentIteration
	The current iteration of the algorithm.

Protected Attributes
AuxGraph< TWeight > *	m_auxGraph

Protected Attributes inherited from ogdf::matching_blossom::BlossomHelper< TWeight >
EdgeArray< TWeight >	m_c
	LP-induced data used by the algorithm.

EpsilonTest	m_eps
	The epsilon test used for floating point comparisons.

GraphCopySimple	m_graph
	A copy of the graph to work on.

bool	m_greedyInit
	Whether or not to use the greedy initialization.

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

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

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

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

NodeArray< TWeight >	m_y

Private Member Functions
template<class E >
E	getTopElement (BlossomPQ< E, TWeight > &pq)
	Helper function to get the top element of any priority queue.

Additional Inherited Members
Protected Member Functions inherited from ogdf::matching_blossom::BlossomHelper< TWeight >
void	deletePseudonodes ()
	Deletes all pseudonodes.

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

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

Static Protected Attributes inherited from ogdf::matching_blossom::BlossomHelper< TWeight >
static const int	WEIGHT_FACTOR = std::numeric_limits<TWeight>::is_integer ? 4 : 1

Detailed Description

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

Helper class for the blossom matching algorithms.

Definition at line 49 of file BlossomVHelper.h.

Constructor & Destructor Documentation

◆ BlossomVHelper()

template<class TWeight >

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

inline

Construct a new Blossom V Helper object.

Parameters

greedyInit whether or not to use the greedy initialization

Definition at line 77 of file BlossomVHelper.h.

Member Function Documentation

◆ getRealReducedWeight()

template<class TWeight >

TWeight ogdf::matching_blossom::BlossomVHelper< TWeight >::getRealReducedWeight ( edge e )

inlineoverridevirtual

Gets the actual reduced weight of the edge, taking into account the delta of the corresponding trees.

Reimplemented from ogdf::matching_blossom::BlossomHelper< TWeight >.

Definition at line 93 of file BlossomVHelper.h.

◆ getRealTopPriority()

template<class TWeight >

template<class E >

TWeight ogdf::matching_blossom::BlossomVHelper< TWeight >::getRealTopPriority ( BlossomPQ< E, TWeight > & pq )

inline

Returns the real value (realReducedWeight or realY) of the top element in the priority queue, or infinity if the queue is empty.

Definition at line 129 of file BlossomVHelper.h.

◆ getTopElement()

template<class TWeight >

template<class E >

E ogdf::matching_blossom::BlossomVHelper< TWeight >::getTopElement ( BlossomPQ< E, TWeight > & pq )

inlineprivate

Helper function to get the top element of any priority queue.

Definition at line 55 of file BlossomVHelper.h.

◆ getTopEligibleElement()

template<class TWeight >

template<class E >

E ogdf::matching_blossom::BlossomVHelper< TWeight >::getTopEligibleElement ( BlossomPQ< E, TWeight > & pq )

inline

Checks if the top element of the given pq has realValue == 0 and returns it, if possible.

Definition at line 116 of file BlossomVHelper.h.

◆ init()

template<class TWeight >

template<class WeightContainer >

bool ogdf::matching_blossom::BlossomVHelper< TWeight >::init	(	const Graph &	graph,
		const WeightContainer &	weights,
		AuxGraph< TWeight > *	auxGraph
	)

inline

Initialize the helper with the given data.

Definition at line 81 of file BlossomVHelper.h.

◆ isZeroCostNode()

template<class TWeight >

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

inline

Checks if the realValue of b is zero.

Definition at line 111 of file BlossomVHelper.h.

◆ realValue() [1/2]

template<class TWeight >

TWeight ogdf::matching_blossom::BlossomVHelper< TWeight >::realValue ( edge e )

inline

Returns the realReducedWeight of e.

Definition at line 105 of file BlossomVHelper.h.

◆ realValue() [2/2]

template<class TWeight >

TWeight ogdf::matching_blossom::BlossomVHelper< TWeight >::realValue ( node v )

inline

Returns the realY of v.

Definition at line 108 of file BlossomVHelper.h.

◆ realY()

template<class TWeight >

TWeight ogdf::matching_blossom::BlossomVHelper< TWeight >::realY ( node v )

inline

Returns the actual y value of the node, taking into account the delta of the corresponding tree.

Definition at line 99 of file BlossomVHelper.h.

Member Data Documentation

◆ currentIteration

template<class TWeight >

long ogdf::matching_blossom::BlossomVHelper< TWeight >::currentIteration

The current iteration of the algorithm.

Definition at line 70 of file BlossomVHelper.h.

◆ m_auxGraph

template<class TWeight >

AuxGraph<TWeight>* ogdf::matching_blossom::BlossomVHelper< TWeight >::m_auxGraph

protected

Definition at line 63 of file BlossomVHelper.h.

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

include/ogdf/graphalg/matching_blossom/AuxGraph.h
include/ogdf/graphalg/matching_blossom/BlossomVHelper.h

OpenGraph DrawingFramework

Public Member Functions

Public Attributes

Protected Attributes

Private Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ BlossomVHelper()

Member Function Documentation

◆ getRealReducedWeight()

◆ getRealTopPriority()

◆ getTopElement()

◆ getTopEligibleElement()

◆ init()

◆ isZeroCostNode()

◆ realValue() [1/2]

◆ realValue() [2/2]

◆ realY()

Member Data Documentation

◆ currentIteration

◆ m_auxGraph

Open
Graph Drawing
Framework