Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::MatchingBlossomV< TWeight > Class Template Reference

Implementation of the Blossom-V algorithm by Kolmogorov (2009) for Minimum Weight Perfect Matching. More...

#include <ogdf/graphalg/MatchingBlossomV.h>

+ Inheritance diagram for ogdf::MatchingBlossomV< TWeight >:

Classes

struct  stats
 Structure to store statistics. More...
 

Public Member Functions

 MatchingBlossomV (bool greedyInit=true)
 Construct a MatchingBlossomV instance. More...
 
- Public Member Functions inherited from ogdf::MatchingModule< TWeight >
virtual ~MatchingModule ()
 
TWeight matchingWeight (const std::unordered_set< edge > &matching, const EdgeArray< TWeight > &weights)
 Calculate the weight of the matching with the weights given in weights. More...
 
TWeight matchingWeight (const std::unordered_set< edge > &matching, const GraphAttributes &GA)
 Calculate the weight of the matching with the weights given in GA. More...
 
TWeight maximumWeightMatching (const Graph &G, const EdgeArray< TWeight > &weights)
 Computes a maximum weight matching in G. More...
 
void maximumWeightMatching (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching)
 Computes a maximum weight matching in G. More...
 
TWeight maximumWeightMatching (const GraphAttributes &GA)
 Computes a maximum weight matching in G. More...
 
void maximumWeightMatching (const GraphAttributes &GA, std::unordered_set< edge > &matching)
 Computes a maximum weight matching in GA. More...
 
std::tuple< bool, TWeight > maximumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights)
 Computes a maximum weight perfect matching in G. More...
 
bool maximumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching)
 Computes a maximum weight perfect matching in G. More...
 
std::tuple< bool, TWeight > maximumWeightPerfectMatching (const GraphAttributes &GA)
 Computes a maximum weight perfect matching in G. More...
 
bool maximumWeightPerfectMatching (const GraphAttributes &GA, std::unordered_set< edge > &matching)
 Computes a maximum weight perfect matching in GA. More...
 
std::tuple< bool, TWeight > minimumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights)
 Computes a minimum weight perfect matching in G. More...
 
bool minimumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching)
 Computes a minimum weight perfect matching in G. More...
 
std::tuple< bool, TWeight > minimumWeightPerfectMatching (const GraphAttributes &GA)
 Computes a minimum weight perfect matching in G. More...
 
bool minimumWeightPerfectMatching (const GraphAttributes &GA, std::unordered_set< edge > &matching)
 Computes a minimum weight perfect matching in GA. More...
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module. More...
 
virtual ~Module ()
 
- Public Member Functions inherited from ogdf::Logger
 Logger ()
 creates a new Logger-object with LogMode::Global and local log-level equal globalLogLevel More...
 
 Logger (Level level)
 creates a new Logger-object with LogMode::Log and given local log-level More...
 
 Logger (LogMode m)
 creates a new Logger-object with given log-mode and local log-level equal globalLogLevel More...
 
 Logger (LogMode m, Level level)
 creates a new Logger-object with given log-mode and given local log-level More...
 
bool is_lout (Level level=Level::Default) const
 returns true if such an lout command will result in text being printed More...
 
std::ostream & lout (Level level=Level::Default, bool indent=true) const
 stream for logging-output (local) More...
 
std::ostream & sout () const
 stream for statistic-output (local) More...
 
std::ostream & fout () const
 stream for forced output (local) More...
 
Level localLogLevel () const
 gives the local log-level More...
 
void localLogLevel (Level level)
 sets the local log-level More...
 
LogMode localLogMode () const
 gives the local log-mode More...
 
void localLogMode (LogMode m)
 sets the local log-mode More...
 
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) More...
 
bool effectiveStatisticMode () const
 returns true if the Logger-object is effectively in statistic-mode (as this might be depending on the global settings) More...
 

Private Member Functions

template<class WeightContainer >
bool _doCall (const Graph &G, const WeightContainer &weights, std::unordered_set< edge > &matching)
 Helper for the main call function since abstract functions cannot be templated. More...
 
void advanceCurrentAuxNode ()
 Helper function to advance the current aux node to the next one. More...
 
void augment (edge augmentationEdge)
 Augment the matching with augmentationEdge. More...
 
bool doCall (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching)
 Main call function for the algorithm with an EdgeArray as weight container. More...
 
bool doCall (const GraphAttributes &GA, std::unordered_set< edge > &matching)
 Main call function for the algorithm with GraphAttrubtes as weight container. More...
 
bool dualChange ()
 Executes a dual change step. More...
 
long long end (std::chrono::high_resolution_clock::time_point start)
 Get the time difference between start and now in nanoseconds. More...
 
void expand (Pseudonode *pseudonode)
 Expand the given pseudonode. More...
 
bool findExpandablePseudonode (AuxNode< TWeight > *auxNode)
 Finds and expands an odd pseudonode in auxNode, if possible. More...
 
bool findMatching (std::unordered_set< edge > &matching)
 Main function of the algorithm. More...
 
bool findMatchingAugmentation (AuxNode< TWeight > *auxNode)
 Finds and executes a matching augmentation in auxNode, if possible. More...
 
bool findShrinkableCycle (AuxNode< TWeight > *auxNode)
 Finds and shrinks an odd cycle in auxNode, if possible. More...
 
bool findTreeAugmentation (AuxNode< TWeight > *auxNode)
 Finds and executes a tree augmentation in auxNode, if possible. More...
 
void grow (edge newEdge)
 Augment the corresponding tree with augmentationEdge. More...
 
std::ostream & lout (Level level=Level::Default, bool indent=true) const
 stream for logging-output (local) More...
 
std::ostream & louth ()
 Helper function to log with high priority. More...
 
std::chrono::high_resolution_clock::time_point now ()
 Get the current time point. More...
 
bool primalChange ()
 Executes a primal change step. More...
 
void printParallelEdgesStats ()
 Print additional statistics about parallel edges. More...
 
void printStatistics ()
 Print all statistics. More...
 
long long processStatisticEntry (const std::string &key)
 Print a single statistics entry. More...
 
void shrink (edge cycleEdge)
 Shrink the odd cycle induced by cycleEdge and the tree determined by its endpoints. More...
 

Private Attributes

AuxGraph< TWeight > m_auxGraph
 
AuxNode< TWeight > * m_currentAuxNode = nullptr
 The current aux node in the main loop. More...
 
EpsilonTest m_eps
 The epsilon test for floating point comparisons. More...
 
BlossomVHelper< TWeight > m_helper
 
std::unordered_map< std::string, statsm_stats
 A mapping of all statistic names to their values. More...
 

Additional Inherited Members

- Public Types inherited from ogdf::Module
enum  ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::Error }
 The return type of a module. More...
 
- Public Types inherited from ogdf::Logger
enum  Level { Level::Minor, Level::Medium, Level::Default, Level::High, Level::Alarm, Level::Force }
 supported log-levels from lowest to highest importance More...
 
enum  LogMode { LogMode::Global, LogMode::GlobalLog, LogMode::Log, LogMode::Statistic }
 Local log-modes. More...
 
- Static Public Member Functions inherited from ogdf::Module
static bool isSolution (ReturnType ret)
 Returns true iff ret indicates that the module returned a feasible solution. More...
 
- Static Public 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 More...
 
static std::ostream & slout (Level level=Level::Default)
 stream for logging-output (global) More...
 
static std::ostream & ssout ()
 stream for statistic-output (global) More...
 
static std::ostream & sfout ()
 stream for forced output (global) More...
 
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 More...
 
static std::ostream & ilout (Level level=Level::Default)
 
static std::ostream & ifout ()
 stream for forced output (global; used by internal libraries, e.g. Abacus) More...
 
static Level globalLogLevel ()
 gives the global log-level More...
 
static void globalLogLevel (Level level)
 sets the global log-level More...
 
static Level globalInternalLibraryLogLevel ()
 gives the internal-library log-level More...
 
static void globalInternalLibraryLogLevel (Level level)
 sets the internal-library log-level More...
 
static Level globalMinimumLogLevel ()
 gives the globally minimally required log-level More...
 
static void globalMinimumLogLevel (Level level)
 sets the globally minimally required log-level More...
 
static bool globalStatisticMode ()
 returns true if we are globally in statistic mode More...
 
static void globalStatisticMode (bool s)
 sets whether we are globally in statistic mode More...
 
static void setWorldStream (std::ostream &o)
 change the stream to which allowed output is written (by default: std::cout) More...
 

Detailed Description

template<typename TWeight>
class ogdf::MatchingBlossomV< TWeight >

Implementation of the Blossom-V algorithm by Kolmogorov (2009) for Minimum Weight Perfect Matching.

Definition at line 80 of file MatchingBlossomV.h.

Constructor & Destructor Documentation

◆ MatchingBlossomV()

template<typename TWeight >
ogdf::MatchingBlossomV< TWeight >::MatchingBlossomV ( bool  greedyInit = true)
inline

Construct a MatchingBlossomV instance.

Parameters
greedyInitwhether or not to use the greedy initialization

Definition at line 271 of file MatchingBlossomV.h.

Member Function Documentation

◆ _doCall()

template<typename TWeight >
template<class WeightContainer >
bool ogdf::MatchingBlossomV< TWeight >::_doCall ( const Graph G,
const WeightContainer &  weights,
std::unordered_set< edge > &  matching 
)
inlineprivate

Helper for the main call function since abstract functions cannot be templated.

Definition at line 285 of file MatchingBlossomV.h.

◆ advanceCurrentAuxNode()

template<typename TWeight >
void ogdf::MatchingBlossomV< TWeight >::advanceCurrentAuxNode ( )
inlineprivate

Helper function to advance the current aux node to the next one.

Definition at line 125 of file MatchingBlossomV.h.

◆ augment()

template<typename TWeight >
void ogdf::MatchingBlossomV< TWeight >::augment ( edge  augmentationEdge)
inlineprivate

Augment the matching with augmentationEdge.

Definition at line 536 of file MatchingBlossomV.h.

◆ doCall() [1/2]

template<typename TWeight >
bool ogdf::MatchingBlossomV< TWeight >::doCall ( const Graph G,
const EdgeArray< TWeight > &  weights,
std::unordered_set< edge > &  matching 
)
inlineprivatevirtual

Main call function for the algorithm with an EdgeArray as weight container.

Implements ogdf::MatchingModule< TWeight >.

Definition at line 274 of file MatchingBlossomV.h.

◆ doCall() [2/2]

template<typename TWeight >
bool ogdf::MatchingBlossomV< TWeight >::doCall ( const GraphAttributes GA,
std::unordered_set< edge > &  matching 
)
inlineprivatevirtual

Main call function for the algorithm with GraphAttrubtes as weight container.

Implements ogdf::MatchingModule< TWeight >.

Definition at line 279 of file MatchingBlossomV.h.

◆ dualChange()

template<typename TWeight >
bool ogdf::MatchingBlossomV< TWeight >::dualChange ( )
inlineprivate

Executes a dual change step.

Definition at line 464 of file MatchingBlossomV.h.

◆ end()

template<typename TWeight >
long long ogdf::MatchingBlossomV< TWeight >::end ( std::chrono::high_resolution_clock::time_point  start)
inlineprivate

Get the time difference between start and now in nanoseconds.

Definition at line 113 of file MatchingBlossomV.h.

◆ expand()

template<typename TWeight >
void ogdf::MatchingBlossomV< TWeight >::expand ( Pseudonode pseudonode)
inlineprivate

Expand the given pseudonode.

Definition at line 764 of file MatchingBlossomV.h.

◆ findExpandablePseudonode()

template<typename TWeight >
bool ogdf::MatchingBlossomV< TWeight >::findExpandablePseudonode ( AuxNode< TWeight > *  auxNode)
inlineprivate

Finds and expands an odd pseudonode in auxNode, if possible.

Returns
whether a pseudonode was expanded

Definition at line 449 of file MatchingBlossomV.h.

◆ findMatching()

template<typename TWeight >
bool ogdf::MatchingBlossomV< TWeight >::findMatching ( std::unordered_set< edge > &  matching)
inlineprivate

Main function of the algorithm.

Finds a minimum weight perfect matching in the graph if one exists.

Returns
whether a matching was found

Definition at line 309 of file MatchingBlossomV.h.

◆ findMatchingAugmentation()

template<typename TWeight >
bool ogdf::MatchingBlossomV< TWeight >::findMatchingAugmentation ( AuxNode< TWeight > *  auxNode)
inlineprivate

Finds and executes a matching augmentation in auxNode, if possible.

Returns
whether the matching was augmented

Definition at line 387 of file MatchingBlossomV.h.

◆ findShrinkableCycle()

template<typename TWeight >
bool ogdf::MatchingBlossomV< TWeight >::findShrinkableCycle ( AuxNode< TWeight > *  auxNode)
inlineprivate

Finds and shrinks an odd cycle in auxNode, if possible.

Returns
whether a cycle was shrunken

Definition at line 432 of file MatchingBlossomV.h.

◆ findTreeAugmentation()

template<typename TWeight >
bool ogdf::MatchingBlossomV< TWeight >::findTreeAugmentation ( AuxNode< TWeight > *  auxNode)
inlineprivate

Finds and executes a tree augmentation in auxNode, if possible.

Returns
whether the tree was augmented

Definition at line 415 of file MatchingBlossomV.h.

◆ grow()

template<typename TWeight >
void ogdf::MatchingBlossomV< TWeight >::grow ( edge  newEdge)
inlineprivate

Augment the corresponding tree with augmentationEdge.

Definition at line 573 of file MatchingBlossomV.h.

◆ lout()

template<typename TWeight >
std::ostream& ogdf::Logger::lout
inlineprivate

stream for logging-output (local)

Definition at line 158 of file Logger.h.

◆ louth()

template<typename TWeight >
std::ostream& ogdf::MatchingBlossomV< TWeight >::louth ( )
inlineprivate

Helper function to log with high priority.

Definition at line 122 of file MatchingBlossomV.h.

◆ now()

template<typename TWeight >
std::chrono::high_resolution_clock::time_point ogdf::MatchingBlossomV< TWeight >::now ( )
inlineprivate

Get the current time point.

Definition at line 108 of file MatchingBlossomV.h.

◆ primalChange()

template<typename TWeight >
bool ogdf::MatchingBlossomV< TWeight >::primalChange ( )
inlineprivate

Executes a primal change step.

Definition at line 354 of file MatchingBlossomV.h.

◆ printParallelEdgesStats()

template<typename TWeight >
void ogdf::MatchingBlossomV< TWeight >::printParallelEdgesStats ( )
inlineprivate

Print additional statistics about parallel edges.

Definition at line 889 of file MatchingBlossomV.h.

◆ printStatistics()

template<typename TWeight >
void ogdf::MatchingBlossomV< TWeight >::printStatistics ( )
inlineprivate

Print all statistics.

Definition at line 860 of file MatchingBlossomV.h.

◆ processStatisticEntry()

template<typename TWeight >
long long ogdf::MatchingBlossomV< TWeight >::processStatisticEntry ( const std::string &  key)
inlineprivate

Print a single statistics entry.

Definition at line 917 of file MatchingBlossomV.h.

◆ shrink()

template<typename TWeight >
void ogdf::MatchingBlossomV< TWeight >::shrink ( edge  cycleEdge)
inlineprivate

Shrink the odd cycle induced by cycleEdge and the tree determined by its endpoints.

Definition at line 645 of file MatchingBlossomV.h.

Member Data Documentation

◆ m_auxGraph

template<typename TWeight >
AuxGraph<TWeight> ogdf::MatchingBlossomV< TWeight >::m_auxGraph
private

Definition at line 82 of file MatchingBlossomV.h.

◆ m_currentAuxNode

template<typename TWeight >
AuxNode<TWeight>* ogdf::MatchingBlossomV< TWeight >::m_currentAuxNode = nullptr
private

The current aux node in the main loop.

Definition at line 85 of file MatchingBlossomV.h.

◆ m_eps

template<typename TWeight >
EpsilonTest ogdf::MatchingBlossomV< TWeight >::m_eps
private

The epsilon test for floating point comparisons.

Definition at line 88 of file MatchingBlossomV.h.

◆ m_helper

template<typename TWeight >
BlossomVHelper<TWeight> ogdf::MatchingBlossomV< TWeight >::m_helper
private

Definition at line 81 of file MatchingBlossomV.h.

◆ m_stats

template<typename TWeight >
std::unordered_map<std::string, stats> ogdf::MatchingBlossomV< TWeight >::m_stats
private

A mapping of all statistic names to their values.

Definition at line 105 of file MatchingBlossomV.h.


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