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

Public Member Functions
	AlternatingTree (BlossomHelper< TWeight > &helper, node root=nullptr)

void	augmentMatching (edge startingEdge)
	Augment the matching along the path from `startingEdge` to the root. `startingEdge` must be incident to a free node.

node	commonNode (edge e)
	Finds the common node between `e` and the tree. If both nodes are in the tree, only the source node is returned.

bool	contains (node v)

edge	evenBackEdge (node v)

void	expand (Pseudonode *pseudonode)
	Expand the given `pseudonode` in this tree.

Cycle *	getCycle (edge cycleEdge)
	Return the odd-length cycle which is closed in this tree with `cycleEdge`.

void	grow (node u, edge e, edge f)
	Grow the tree by adding e and f.

bool	hasRoot ()

bool	isEven (node v)

bool	isOdd (node v)

edge	oddBackEdge (node v)

void	reset (node root=nullptr)
	Reset the tree with new the new `root`. If `root` is nullptr, the tree will be invalid.

node	root ()

Pseudonode *	shrink (Cycle *cycle, std::vector< std::tuple< edge, bool > > &_selfLoops)
	Shrink the `cycle` in this tree and return the generated pseudonode.

Public Attributes
KeyIteratorContainer< node, edge >	evenNodes

KeyIteratorContainer< node, edge >	oddNodes

Private Types
using	IteratorCallback = std::function< void(edge, bool)>
	Type of callback function when iterating the tree.

Private Member Functions
node	findCycleStartNode (edge e)
	Find the node where the paths from both endpoints of `e` to the root first meet.

node	getNextEvenNode (node v, IteratorCallback callback=nullptr)
	Return the next even node in root direction. `v` must be even. `callback` is executed for both edges on the path, if given.

void	iterateTree (node start, node end, IteratorCallback callback)
	Iterate the tree from `start` to `end`. `callback` is executed for each edge on the path. Both `start` and `end` must be even.

void	moveEdge (edge e, node oldNode, node newNode)
	Exchange the end node `oldNode` of edge `e` in graph `graph` for node `newNode`.

Private Attributes
EpsilonTest	m_eps
	Epsilon test for floating point numbers.

std::unordered_map< node, edge >	m_evenNodes
	All even nodes, mapped to their respective back edge in the tree (or nullptr for the root).

BlossomHelper< TWeight > &	m_helper
	Reference to the helper class.

std::unordered_map< node, edge >	m_oddNodes
	All odd nodes, mapped to their respective back edge in the tree.

node	m_root
	The root of the tree. May be empty to signalize an invalid tree which needs to be rebuild.

Detailed Description

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

Definition at line 59 of file AlternatingTree.h.

Member Typedef Documentation

◆ IteratorCallback

template<class TWeight >

using ogdf::matching_blossom::AlternatingTree< TWeight >::IteratorCallback = std::function<void(edge, bool)>

private

Type of callback function when iterating the tree.

Definition at line 61 of file AlternatingTree.h.

Constructor & Destructor Documentation

◆ AlternatingTree()

template<class TWeight >

ogdf::matching_blossom::AlternatingTree< TWeight >::AlternatingTree	(	BlossomHelper< TWeight > &	helper,
		node	root = `nullptr`
	)

inline

Definition at line 138 of file AlternatingTree.h.

Member Function Documentation

◆ augmentMatching()

template<class TWeight >

void ogdf::matching_blossom::AlternatingTree< TWeight >::augmentMatching ( edge startingEdge )

inline

Augment the matching along the path from startingEdge to the root. startingEdge must be incident to a free node.

Definition at line 210 of file AlternatingTree.h.

◆ commonNode()

template<class TWeight >

node ogdf::matching_blossom::AlternatingTree< TWeight >::commonNode ( edge e )

inline

Finds the common node between e and the tree. If both nodes are in the tree, only the source node is returned.

Definition at line 159 of file AlternatingTree.h.

◆ contains()

template<class TWeight >

bool ogdf::matching_blossom::AlternatingTree< TWeight >::contains ( node v )

inline

Definition at line 155 of file AlternatingTree.h.

◆ evenBackEdge()

template<class TWeight >

edge ogdf::matching_blossom::AlternatingTree< TWeight >::evenBackEdge ( node v )

inline

Definition at line 147 of file AlternatingTree.h.

◆ expand()

template<class TWeight >

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

inline

Expand the given pseudonode in this tree.

Definition at line 311 of file AlternatingTree.h.

◆ findCycleStartNode()

template<class TWeight >

node ogdf::matching_blossom::AlternatingTree< TWeight >::findCycleStartNode ( edge e )

inlineprivate

Find the node where the paths from both endpoints of e to the root first meet.

Definition at line 79 of file AlternatingTree.h.

◆ getCycle()

template<class TWeight >

Cycle * ogdf::matching_blossom::AlternatingTree< TWeight >::getCycle ( edge cycleEdge )

inline

Return the odd-length cycle which is closed in this tree with cycleEdge.

Definition at line 194 of file AlternatingTree.h.

◆ getNextEvenNode()

template<class TWeight >

node ogdf::matching_blossom::AlternatingTree< TWeight >::getNextEvenNode	(	node	v,
		IteratorCallback	callback = `nullptr`
	)

inlineprivate

Return the next even node in root direction. v must be even. callback is executed for both edges on the path, if given.

Definition at line 98 of file AlternatingTree.h.

◆ grow()

template<class TWeight >

void ogdf::matching_blossom::AlternatingTree< TWeight >::grow	(	node	u,
		edge	e,
		edge	f
	)

inline

Grow the tree by adding e and f.

Parameters

u	the node from which to grow, must be an even node in the tree.
e	the edge connecting u to a node incident to f.
f	a matching edge which should be added to the tree.

Definition at line 186 of file AlternatingTree.h.

◆ hasRoot()

template<class TWeight >

bool ogdf::matching_blossom::AlternatingTree< TWeight >::hasRoot ( )

inline

Definition at line 145 of file AlternatingTree.h.

◆ isEven()

template<class TWeight >

bool ogdf::matching_blossom::AlternatingTree< TWeight >::isEven ( node v )

inline

Definition at line 149 of file AlternatingTree.h.

◆ isOdd()

template<class TWeight >

bool ogdf::matching_blossom::AlternatingTree< TWeight >::isOdd ( node v )

inline

Definition at line 153 of file AlternatingTree.h.

◆ iterateTree()

template<class TWeight >

void ogdf::matching_blossom::AlternatingTree< TWeight >::iterateTree	(	node	start,
		node	end,
		IteratorCallback	callback
	)

inlineprivate

Iterate the tree from start to end. callback is executed for each edge on the path. Both start and end must be even.

Definition at line 117 of file AlternatingTree.h.

◆ moveEdge()

template<class TWeight >

void ogdf::matching_blossom::AlternatingTree< TWeight >::moveEdge	(	edge	e,
		node	oldNode,
		node	newNode
	)

inlineprivate

Exchange the end node oldNode of edge e in graph graph for node newNode.

Definition at line 125 of file AlternatingTree.h.

◆ oddBackEdge()

template<class TWeight >

edge ogdf::matching_blossom::AlternatingTree< TWeight >::oddBackEdge ( node v )

inline

Definition at line 151 of file AlternatingTree.h.

◆ reset()

template<class TWeight >

void ogdf::matching_blossom::AlternatingTree< TWeight >::reset ( node root = nullptr )

inline

Reset the tree with new the new root. If root is nullptr, the tree will be invalid.

Definition at line 169 of file AlternatingTree.h.

◆ root()

template<class TWeight >

node ogdf::matching_blossom::AlternatingTree< TWeight >::root ( )

inline

Definition at line 143 of file AlternatingTree.h.

◆ shrink()

template<class TWeight >

Pseudonode * ogdf::matching_blossom::AlternatingTree< TWeight >::shrink	(	Cycle *	cycle,
		std::vector< std::tuple< edge, bool > > &	_selfLoops
	)

inline

Shrink the cycle in this tree and return the generated pseudonode.

Definition at line 220 of file AlternatingTree.h.

Member Data Documentation

◆ evenNodes

template<class TWeight >

KeyIteratorContainer<node, edge> ogdf::matching_blossom::AlternatingTree< TWeight >::evenNodes

Definition at line 134 of file AlternatingTree.h.

◆ m_eps

template<class TWeight >

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

private

Epsilon test for floating point numbers.

Definition at line 76 of file AlternatingTree.h.

◆ m_evenNodes

template<class TWeight >

std::unordered_map<node, edge> ogdf::matching_blossom::AlternatingTree< TWeight >::m_evenNodes

private

All even nodes, mapped to their respective back edge in the tree (or nullptr for the root).

Definition at line 70 of file AlternatingTree.h.

◆ m_helper

template<class TWeight >

BlossomHelper<TWeight>& ogdf::matching_blossom::AlternatingTree< TWeight >::m_helper

private

Reference to the helper class.

Definition at line 64 of file AlternatingTree.h.

◆ m_oddNodes

template<class TWeight >

std::unordered_map<node, edge> ogdf::matching_blossom::AlternatingTree< TWeight >::m_oddNodes

private

All odd nodes, mapped to their respective back edge in the tree.

Definition at line 73 of file AlternatingTree.h.

◆ m_root

template<class TWeight >

node ogdf::matching_blossom::AlternatingTree< TWeight >::m_root

private

The root of the tree. May be empty to signalize an invalid tree which needs to be rebuild.

Definition at line 67 of file AlternatingTree.h.

◆ oddNodes

template<class TWeight >

KeyIteratorContainer<node, edge> ogdf::matching_blossom::AlternatingTree< TWeight >::oddNodes

Definition at line 136 of file AlternatingTree.h.

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

include/ogdf/graphalg/matching_blossom/AlternatingTree.h

OpenGraph DrawingFramework

Public Member Functions

Public Attributes

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ IteratorCallback

Constructor & Destructor Documentation

◆ AlternatingTree()

Member Function Documentation

◆ augmentMatching()

◆ commonNode()

◆ contains()

◆ evenBackEdge()

◆ expand()

◆ findCycleStartNode()

◆ getCycle()

◆ getNextEvenNode()

◆ grow()

◆ hasRoot()

◆ isEven()

◆ isOdd()

◆ iterateTree()

◆ moveEdge()

◆ oddBackEdge()

◆ reset()

◆ root()

◆ shrink()

Member Data Documentation

◆ evenNodes

◆ m_eps

◆ m_evenNodes

◆ m_helper

◆ m_oddNodes

◆ m_root

◆ oddNodes

Open
Graph Drawing
Framework