Simple algorithms for matchings (testing properties, obtaining a maximal matching) More...

Functions
void	ogdf::Matching::findMaximalMatching (const Graph &graph, ArrayBuffer< edge > &matching)
	Obtains a maximal matching in O(\|E\|) time.

int	ogdf::Matching::findMaximumCardinalityMatching (const Graph &G, const List< node > &U, const List< node > &V, EdgeArray< bool > &matching)
	Finds a maximum cardinality matching in the bipartite graph `G` = (U+V, E) in O(sqrt(\|U+V\|) * \|E\|) time by using the Hopcroft-Karp-Karzanov algorithm.

template<typename EdgeContainer >
bool	ogdf::Matching::isMatching (const Graph &graph, const EdgeContainer &matching)
	Checks in time O(\|V\| + size of `matching`) if the given set of edges represents a matching.

template<typename EdgeContainer >
bool	ogdf::Matching::isMaximal (const Graph &graph, const EdgeContainer &matching)
	Checks in time O(\|E\|) if there are edges that could be added to `matching`.

template<typename EdgeContainer >
bool	ogdf::Matching::isMaximalMatching (const Graph &graph, const EdgeContainer &matching)
	Checks in O(\|V\| + \|E\|) time if `matching` is a maximal matching.

template<typename EdgeContainer >
bool	ogdf::Matching::isPerfect (const Graph &graph, const EdgeContainer &matching)
	Checks in O(1) if `matching` (assuming it is a matching and the graph is simple and connected) is perfect.

template<typename EdgeContainer >
bool	ogdf::Matching::isPerfectMatching (const Graph &graph, const EdgeContainer &matching)
	Checks in O(\|V\| + size of `matching`) if `matching` is a perfect matching.

Detailed Description

Simple algorithms for matchings (testing properties, obtaining a maximal matching)

Function Documentation

◆ findMaximalMatching()

void ogdf::Matching::findMaximalMatching	(	const Graph &	graph,
		ArrayBuffer< edge > &	matching
	)

Obtains a maximal matching in O(|E|) time.

◆ findMaximumCardinalityMatching()

int ogdf::Matching::findMaximumCardinalityMatching	(	const Graph &	G,
		const List< node > &	U,
		const List< node > &	V,
		EdgeArray< bool > &	matching
	)

Finds a maximum cardinality matching in the bipartite graph G = (U+V, E) in O(sqrt(|U+V|) * |E|) time by using the Hopcroft-Karp-Karzanov algorithm.

Parameters

G	the bipartite graph
U	all nodes in the first half of `G`
V	all nodes in the second half of `G`
matching	will hold the matching

Returns: the cardinality of the matching