Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Member Functions | Public Attributes | Protected Attributes | Private Member Functions | List of all members
ogdf::matching_blossom::BlossomVHelper< TWeight > Class Template Reference

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

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

Public Member Functions

 BlossomVHelper (bool greedyInit)
 Construct a new Blossom V Helper object. More...
 
TWeight getRealReducedWeight (edge e) override
 Gets the actual reduced weight of the edge, taking into account the delta of the corresponding trees. More...
 
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. More...
 
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. More...
 
template<class WeightContainer >
bool init (const Graph &graph, const WeightContainer &weights, AuxGraph< TWeight > *auxGraph)
 Initialize the helper with the given data. More...
 
bool isZeroCostNode (node v)
 Checks if the realValue of b is zero. More...
 
TWeight realValue (edge e)
 Returns the realReducedWeight of e. More...
 
TWeight realValue (node v)
 Returns the realY of v. More...
 
TWeight realY (node v)
 Returns the actual y value of the node, taking into account the delta of the corresponding tree. More...
 

Public Attributes

long currentIteration
 The current iteration of the algorithm. More...
 

Protected Attributes

AuxGraph< TWeight > * m_auxGraph
 

Private Member Functions

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

Detailed Description

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

Helper class for the blossom matching algorithms.

Definition at line 53 of file AuxGraph.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
greedyInitwhether or not to use the greedy initialization

Definition at line 79 of file BlossomVHelper.h.

Member Function Documentation

◆ getRealReducedWeight()

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

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

Definition at line 95 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 131 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 57 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 118 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 83 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 113 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 107 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 110 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 101 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 72 of file BlossomVHelper.h.

◆ m_auxGraph

template<class TWeight >
AuxGraph<TWeight>* ogdf::matching_blossom::BlossomVHelper< TWeight >::m_auxGraph
protected

Definition at line 65 of file BlossomVHelper.h.

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