Implementation of the Blossom-I algorithm by Edmonds (1965) for Minimum Weight Perfect Matching. More...

#include <ogdf/graphalg/MatchingBlossom.h>

Inheritance diagram for ogdf::MatchingBlossom< TWeight >:

Public Member Functions
	MatchingBlossom (bool greedyInit=true)
	Construct a MatchingBlossom 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...

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

void	expand (Pseudonode *pseudonode)
	Expand the pseudonode `pseudonode`. More...

bool	findExpandablePseudonode ()
	Finds and expands an odd pseudonode, if possible. More...

bool	findMatching (std::unordered_set< edge > &matching)
	Main function of the algorithm. More...

bool	findMatchingAugmentation ()
	Finds and executes a matching augmentation, if possible. More...

bool	findShrinkableCycle ()
	Finds and shrinks an odd cycle, if possible. More...

bool	findTreeAugmentation ()
	Finds and executes a tree augmentation, if possible. More...

node	getNewRoot ()
	Helper function to get a new root for the tree. More...

void	hideNonEqualityEdges ()
	Helper function to hide all non-equality edges. More...

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

bool	primalChange ()
	Executes a primal change step. More...

void	restoreNonEqualityEdges ()
	Helper function to restore all non-equality edges. More...

void	shrink (edge cycleEdge)
	Shrink the odd cycle induced by the current tree together with `cycleEdge`. More...

Private Attributes
std::unordered_set< node >	m_graphNodes
	All nodes currently present in the graph. More...

BlossomHelper< TWeight >	m_helper
	Helper class to store the current state of the algorithm. More...

std::unordered_set< edge >	m_nonEqualityEdges
	Set of all non-equality edges. More...

std::unique_ptr< Graph::HiddenEdgeSet >	m_nonEqualityEdgesHiddenSet
	Pointer to the HiddenEdgeSet containing all non-equality edges. More...

std::unordered_set< node >	m_pseudonodes
	All top-level pseudonodes. More...

std::unique_ptr< AlternatingTree< TWeight > >	m_tree
	The alternating tree. More...

std::unordered_set< node >	m_unmatchedNodes
	All nodes which are not part of the matching yet. 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::MatchingBlossom< TWeight >

Implementation of the Blossom-I algorithm by Edmonds (1965) for Minimum Weight Perfect Matching.

Use MatchingBlossomV for a more sophisticated and faster version of this algorithm.

Definition at line 63 of file MatchingBlossom.h.

Constructor & Destructor Documentation

◆ MatchingBlossom()

template<typename TWeight >

ogdf::MatchingBlossom< TWeight >::MatchingBlossom ( bool greedyInit = true )

inline

Construct a MatchingBlossom instance.

Parameters

greedyInit whether or not to use the greedy initialization

Definition at line 175 of file MatchingBlossom.h.

Member Function Documentation

◆ _doCall()

template<typename TWeight >

template<class WeightContainer >

bool ogdf::MatchingBlossom< 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 189 of file MatchingBlossom.h.

◆ doCall() [1/2]

template<typename TWeight >

bool ogdf::MatchingBlossom< 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 178 of file MatchingBlossom.h.

◆ doCall() [2/2]

template<typename TWeight >

bool ogdf::MatchingBlossom< 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 183 of file MatchingBlossom.h.

◆ dualChange()

template<typename TWeight >

bool ogdf::MatchingBlossom< TWeight >::dualChange ( )

inlineprivate

Executes a dual change step.

Definition at line 335 of file MatchingBlossom.h.

◆ expand()

template<typename TWeight >

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

inlineprivate

Expand the pseudonode pseudonode.

Definition at line 433 of file MatchingBlossom.h.

◆ findExpandablePseudonode()

template<typename TWeight >

bool ogdf::MatchingBlossom< TWeight >::findExpandablePseudonode ( )

inlineprivate

Finds and expands an odd pseudonode, if possible.

Returns: whether a pseudonode was expanded

Definition at line 324 of file MatchingBlossom.h.

◆ findMatching()

template<typename TWeight >

bool ogdf::MatchingBlossom< 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 223 of file MatchingBlossom.h.

◆ findMatchingAugmentation()

template<typename TWeight >

bool ogdf::MatchingBlossom< TWeight >::findMatchingAugmentation ( )

inlineprivate

Finds and executes a matching augmentation, if possible.

Returns: whether the matching was augmented

Definition at line 262 of file MatchingBlossom.h.

◆ findShrinkableCycle()

template<typename TWeight >

bool ogdf::MatchingBlossom< TWeight >::findShrinkableCycle ( )

inlineprivate

Finds and shrinks an odd cycle, if possible.

Returns: whether a cycle was shrunken

Definition at line 305 of file MatchingBlossom.h.

◆ findTreeAugmentation()

template<typename TWeight >

bool ogdf::MatchingBlossom< TWeight >::findTreeAugmentation ( )

inlineprivate

Finds and executes a tree augmentation, if possible.

Returns: whether the tree was augmented

Definition at line 285 of file MatchingBlossom.h.

◆ getNewRoot()

template<typename TWeight >

node ogdf::MatchingBlossom< TWeight >::getNewRoot ( )

inlineprivate

Helper function to get a new root for the tree.

Precondition: There must still be unmatched nodes left.

Returns: the new root

Definition at line 167 of file MatchingBlossom.h.

◆ hideNonEqualityEdges()

template<typename TWeight >

void ogdf::MatchingBlossom< TWeight >::hideNonEqualityEdges ( )

inlineprivate

Helper function to hide all non-equality edges.

Definition at line 151 of file MatchingBlossom.h.

◆ lout()

template<typename TWeight >

std::ostream& ogdf::Logger::lout

inlineprivate

stream for logging-output (local)

Definition at line 158 of file Logger.h.

◆ primalChange()

template<typename TWeight >

bool ogdf::MatchingBlossom< TWeight >::primalChange ( )

inlineprivate

Executes a primal change step.

Definition at line 244 of file MatchingBlossom.h.

◆ restoreNonEqualityEdges()

template<typename TWeight >

void ogdf::MatchingBlossom< TWeight >::restoreNonEqualityEdges ( )

inlineprivate

Helper function to restore all non-equality edges.

Definition at line 158 of file MatchingBlossom.h.

◆ shrink()

template<typename TWeight >

void ogdf::MatchingBlossom< TWeight >::shrink ( edge cycleEdge )

inlineprivate

Shrink the odd cycle induced by the current tree together with cycleEdge.

Definition at line 402 of file MatchingBlossom.h.

Member Data Documentation

◆ m_graphNodes

template<typename TWeight >

std::unordered_set<node> ogdf::MatchingBlossom< TWeight >::m_graphNodes

private

All nodes currently present in the graph.

Definition at line 76 of file MatchingBlossom.h.

◆ m_helper

template<typename TWeight >

BlossomHelper<TWeight> ogdf::MatchingBlossom< TWeight >::m_helper

private

Helper class to store the current state of the algorithm.

Definition at line 67 of file MatchingBlossom.h.

◆ m_nonEqualityEdges

template<typename TWeight >

std::unordered_set<edge> ogdf::MatchingBlossom< TWeight >::m_nonEqualityEdges

private

Set of all non-equality edges.

Definition at line 73 of file MatchingBlossom.h.

◆ m_nonEqualityEdgesHiddenSet

template<typename TWeight >

std::unique_ptr<Graph::HiddenEdgeSet> ogdf::MatchingBlossom< TWeight >::m_nonEqualityEdgesHiddenSet

private

Pointer to the HiddenEdgeSet containing all non-equality edges.

Definition at line 70 of file MatchingBlossom.h.

◆ m_pseudonodes

template<typename TWeight >

std::unordered_set<node> ogdf::MatchingBlossom< TWeight >::m_pseudonodes

private

All top-level pseudonodes.

Definition at line 82 of file MatchingBlossom.h.

◆ m_tree

template<typename TWeight >

std::unique_ptr<AlternatingTree<TWeight> > ogdf::MatchingBlossom< TWeight >::m_tree

private

The alternating tree.

Definition at line 85 of file MatchingBlossom.h.

◆ m_unmatchedNodes

template<typename TWeight >

std::unordered_set<node> ogdf::MatchingBlossom< TWeight >::m_unmatchedNodes

private

All nodes which are not part of the matching yet.

Definition at line 79 of file MatchingBlossom.h.

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

include/ogdf/graphalg/MatchingBlossom.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

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

Constructor & Destructor Documentation

◆ MatchingBlossom()

Member Function Documentation

◆ _doCall()

◆ doCall() [1/2]

◆ doCall() [2/2]

◆ dualChange()

◆ expand()

◆ findExpandablePseudonode()

◆ findMatching()

◆ findMatchingAugmentation()

◆ findShrinkableCycle()

◆ findTreeAugmentation()

◆ getNewRoot()

◆ hideNonEqualityEdges()

◆ lout()

◆ primalChange()

◆ restoreNonEqualityEdges()

◆ shrink()

Member Data Documentation

◆ m_graphNodes

◆ m_helper

◆ m_nonEqualityEdges

◆ m_nonEqualityEdgesHiddenSet

◆ m_pseudonodes

◆ m_tree

◆ m_unmatchedNodes

Open
Graph Drawing
Framework

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