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

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

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

Public Member Functions
	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.

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

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

Protected Member Functions
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.

Protected Attributes
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

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

Additional Inherited Members
Private Types inherited from ogdf::Logger
enum class	Level { Minor , Medium , Default , High , Alarm , Force }
	supported log-levels from lowest to highest importance More...

enum class	LogMode { Global , GlobalLog , Log , Statistic }
	Local log-modes. More...

Private Member Functions inherited from ogdf::Logger
	Logger ()
	creates a new Logger-object with LogMode::Global and local log-level equal globalLogLevel

	Logger (Level level)
	creates a new Logger-object with LogMode::Log and given local log-level

	Logger (LogMode m)
	creates a new Logger-object with given log-mode and local log-level equal globalLogLevel

	Logger (LogMode m, Level level)
	creates a new Logger-object with given log-mode and given local log-level

bool	is_lout (Level level=Level::Default) const
	returns true if such an lout command will result in text being printed

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

std::ostream &	sout () const
	stream for statistic-output (local)

std::ostream &	fout () const
	stream for forced output (local)

Level	localLogLevel () const
	gives the local log-level

void	localLogLevel (Level level)
	sets the local log-level

LogMode	localLogMode () const
	gives the local log-mode

void	localLogMode (LogMode m)
	sets the local log-mode

void	indent (int by=1)

void	dedent (int by=1)

int	getIndent () const

void	setIndent (int indent)

Level	effectiveLogLevel () const
	obtain the effective log-level for the Logger-object (i.e., resolve the dependencies on the global settings)

bool	effectiveStatisticMode () const
	returns true if the Logger-object is effectively in statistic-mode (as this might be depending on the global settings)

Static Private Member Functions inherited from ogdf::Logger
static bool	is_slout (Level level=Level::Default)
	returns true if such an slout command will result in text being printed

static std::ostream &	slout (Level level=Level::Default)
	stream for logging-output (global)

static std::ostream &	ssout ()
	stream for statistic-output (global)

static std::ostream &	sfout ()
	stream for forced output (global)

static bool	is_ilout (Level level=Level::Default)
	stream for logging-output (global; used by internal libraries, e.g. Abacus) returns true if such an ilout command will result in text being printed

static std::ostream &	ilout (Level level=Level::Default)

static std::ostream &	ifout ()
	stream for forced output (global; used by internal libraries, e.g. Abacus)

static Level	globalLogLevel ()
	gives the global log-level

static void	globalLogLevel (Level level)
	sets the global log-level

static Level	globalInternalLibraryLogLevel ()
	gives the internal-library log-level

static void	globalInternalLibraryLogLevel (Level level)
	sets the internal-library log-level

static Level	globalMinimumLogLevel ()
	gives the globally minimally required log-level

static void	globalMinimumLogLevel (Level level)
	sets the globally minimally required log-level

static bool	globalStatisticMode ()
	returns true if we are globally in statistic mode

static void	globalStatisticMode (bool s)
	sets whether we are globally in statistic mode

static void	setWorldStream (std::ostream &o)
	change the stream to which allowed output is written (by default: `std::cout`)

Detailed Description

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

Helper class for the blossom matching algorithms.

Definition at line 60 of file BlossomHelper.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.

Reimplemented in ogdf::matching_blossom::BlossomVHelper< TWeight >.

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

Additional Inherited Members

Detailed Description

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