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

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

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

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

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

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

Detailed Description

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

Function Documentation