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

Public Member Functions
	AuxGraph (BlossomVHelper< TWeight > &helper)

AuxEdge< TWeight > *	assertCurrentEdge (AuxNode< TWeight > auxNode, AuxNode< TWeight > current)
	Creates an AuxEdge between `auxNode` and `current` if it does not exist and sets the currentEdge of `auxNode` accordingly.

AuxEdge< TWeight > *	auxEdge (edge e)
	Returns the AuxEdge corresponding to `e`, which must be an edge of the auxiliary graph.

AuxNode< TWeight > *	auxNode (node v)
	Returns the AuxNode corresponding to `v`, which must be a node of the auxiliary graph.

AuxNode< TWeight > *	auxNodeForEdge (edge e)
	Returns the AuxNode of the auxiliary graph whose tree contains at least one endpoint of `e`. `e` must be part of the actual graph.

void	connectedComponents (std::vector< std::unordered_set< node > > &components)
	Calculates the connected components of the auxiliary graph and stores them in `components`. Only tight even-odd/odd-even edges between different trees are taken into account.

void	deleteNode (AuxNode< TWeight > *auxNode)
	Removes `auxNode` and all incident edges from the auxiliary graph.

const EdgeArray< AuxEdge< TWeight > * > &	edges () const

GraphCopySimple &	graph ()

const NodeArray< AuxNode< TWeight > * > &	nodes () const

void	reset ()
	Rebuilds the auxiliary graph from the current graph.

void	setAuxNode (node v, AuxNode< TWeight > *auxNode)
	Sets the AuxNode of `v` to `auxNode`.

AuxNode< TWeight > *	treeAuxNode (node v)
	Returns the AuxNode of whose tree the node `v` of the actual graph is a part of.

AlternatingTree< TWeight > *	treeOf (node v)
	Returns the tree which contains `v`, or nullptr if `v` is free.

Private Member Functions
AuxEdge< TWeight > *	createAuxEdge (edge e)
	Creates an AuxEdge for `e` and stores it in the appropriate maps.

AuxNode< TWeight > *	createAuxNode (node v)
	Creates an AuxNode for `v` and stores it in the appropriate maps.

Private Attributes
EdgeArray< AuxEdge< TWeight > * >	m_auxGraphEdgeMap
	maps auxiliary graph edges to their AuxEdge objects

NodeArray< AuxNode< TWeight > * >	m_auxGraphNodeMap
	maps auxiliary graph nodes to their AuxNode objects

GraphCopySimple	m_graph

BlossomVHelper< TWeight > &	m_helper

NodeArray< AuxNode< TWeight > * >	m_nodeAuxNodeMap
	maps normal graph nodes to the AuxNode whose tree they belong to

Detailed Description

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

Definition at line 215 of file AuxGraph.h.

Constructor & Destructor Documentation

◆ AuxGraph()

template<class TWeight >

ogdf::matching_blossom::AuxGraph< TWeight >::AuxGraph ( BlossomVHelper< TWeight > & helper )

inline

Definition at line 245 of file AuxGraph.h.

Member Function Documentation

◆ assertCurrentEdge()

template<class TWeight >

AuxEdge< TWeight > * ogdf::matching_blossom::AuxGraph< TWeight >::assertCurrentEdge	(	AuxNode< TWeight > *	auxNode,
		AuxNode< TWeight > *	current
	)

inline

Creates an AuxEdge between auxNode and current if it does not exist and sets the currentEdge of auxNode accordingly.

Definition at line 320 of file AuxGraph.h.

◆ auxEdge()

template<class TWeight >

AuxEdge< TWeight > * ogdf::matching_blossom::AuxGraph< TWeight >::auxEdge ( edge e )

inline

Returns the AuxEdge corresponding to e, which must be an edge of the auxiliary graph.

Definition at line 262 of file AuxGraph.h.

◆ auxNode()

template<class TWeight >

AuxNode< TWeight > * ogdf::matching_blossom::AuxGraph< TWeight >::auxNode ( node v )

inline

Returns the AuxNode corresponding to v, which must be a node of the auxiliary graph.

Definition at line 265 of file AuxGraph.h.

◆ auxNodeForEdge()

template<class TWeight >

AuxNode< TWeight > * ogdf::matching_blossom::AuxGraph< TWeight >::auxNodeForEdge ( edge e )

inline

Returns the AuxNode of the auxiliary graph whose tree contains at least one endpoint of e. e must be part of the actual graph.

Definition at line 303 of file AuxGraph.h.

◆ connectedComponents()

template<class TWeight >

void ogdf::matching_blossom::AuxGraph< TWeight >::connectedComponents ( std::vector< std::unordered_set< node > > & components )

inline

Calculates the connected components of the auxiliary graph and stores them in components. Only tight even-odd/odd-even edges between different trees are taken into account.

Note: We cannot use connectedComponents from simple_graph_alg.h since we need to iterate the components one after another and not all edges are taken into account.

Definition at line 356 of file AuxGraph.h.

◆ createAuxEdge()

template<class TWeight >

AuxEdge< TWeight > * ogdf::matching_blossom::AuxGraph< TWeight >::createAuxEdge ( edge e )

inlineprivate

Creates an AuxEdge for e and stores it in the appropriate maps.

Definition at line 238 of file AuxGraph.h.

◆ createAuxNode()

template<class TWeight >

AuxNode< TWeight > * ogdf::matching_blossom::AuxGraph< TWeight >::createAuxNode ( node v )

inlineprivate

Creates an AuxNode for v and stores it in the appropriate maps.

Definition at line 229 of file AuxGraph.h.

◆ deleteNode()

template<class TWeight >

void ogdf::matching_blossom::AuxGraph< TWeight >::deleteNode ( AuxNode< TWeight > * auxNode )

inline

Removes auxNode and all incident edges from the auxiliary graph.

Definition at line 335 of file AuxGraph.h.

◆ edges()

template<class TWeight >

const EdgeArray< AuxEdge< TWeight > * > & ogdf::matching_blossom::AuxGraph< TWeight >::edges ( ) const

inline

Definition at line 259 of file AuxGraph.h.

◆ graph()

template<class TWeight >

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

inline

Definition at line 255 of file AuxGraph.h.

◆ nodes()

template<class TWeight >

const NodeArray< AuxNode< TWeight > * > & ogdf::matching_blossom::AuxGraph< TWeight >::nodes ( ) const

inline

Definition at line 257 of file AuxGraph.h.

◆ reset()

template<class TWeight >

void ogdf::matching_blossom::AuxGraph< TWeight >::reset ( )

inline

Rebuilds the auxiliary graph from the current graph.

Definition at line 273 of file AuxGraph.h.

◆ setAuxNode()

template<class TWeight >

void ogdf::matching_blossom::AuxGraph< TWeight >::setAuxNode	(	node	v,
		AuxNode< TWeight > *	auxNode
	)

inline

Sets the AuxNode of v to auxNode.

Definition at line 332 of file AuxGraph.h.

◆ treeAuxNode()

template<class TWeight >

AuxNode< TWeight > * ogdf::matching_blossom::AuxGraph< TWeight >::treeAuxNode ( node v )

inline

Returns the AuxNode of whose tree the node v of the actual graph is a part of.

Definition at line 268 of file AuxGraph.h.

◆ treeOf()

template<class TWeight >

AlternatingTree< TWeight > * ogdf::matching_blossom::AuxGraph< TWeight >::treeOf ( node v )

inline

Returns the tree which contains v, or nullptr if v is free.

Definition at line 313 of file AuxGraph.h.

Member Data Documentation

◆ m_auxGraphEdgeMap

template<class TWeight >

EdgeArray<AuxEdge<TWeight>*> ogdf::matching_blossom::AuxGraph< TWeight >::m_auxGraphEdgeMap

private

maps auxiliary graph edges to their AuxEdge objects

Definition at line 224 of file AuxGraph.h.

◆ m_auxGraphNodeMap

template<class TWeight >

NodeArray<AuxNode<TWeight>*> ogdf::matching_blossom::AuxGraph< TWeight >::m_auxGraphNodeMap

private

maps auxiliary graph nodes to their AuxNode objects

Definition at line 222 of file AuxGraph.h.

◆ m_graph

template<class TWeight >

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

private

Definition at line 219 of file AuxGraph.h.

◆ m_helper

template<class TWeight >

BlossomVHelper<TWeight>& ogdf::matching_blossom::AuxGraph< TWeight >::m_helper

private

Definition at line 216 of file AuxGraph.h.

◆ m_nodeAuxNodeMap

template<class TWeight >

NodeArray<AuxNode<TWeight>*> ogdf::matching_blossom::AuxGraph< TWeight >::m_nodeAuxNodeMap

private

maps normal graph nodes to the AuxNode whose tree they belong to

Definition at line 226 of file AuxGraph.h.

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

include/ogdf/graphalg/matching_blossom/AuxGraph.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ AuxGraph()

Member Function Documentation

◆ assertCurrentEdge()

◆ auxEdge()

◆ auxNode()

◆ auxNodeForEdge()

◆ connectedComponents()

◆ createAuxEdge()

◆ createAuxNode()

◆ deleteNode()

◆ edges()

◆ graph()

◆ nodes()

◆ reset()

◆ setAuxNode()

◆ treeAuxNode()

◆ treeOf()

Member Data Documentation

◆ m_auxGraphEdgeMap

◆ m_auxGraphNodeMap

◆ m_graph

◆ m_helper

◆ m_nodeAuxNodeMap

Open
Graph Drawing
Framework