# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
ogdf::Matching Namespace Reference

Simple algorithms for matchings. More...

## Functions

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

int 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 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 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 isMaximal (const Graph &graph, const EdgeContainer &matching, edge &addable)
Checks in time O(|E|) if there are edges that could be added to matching.

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

template<typename EdgeContainer >
bool 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 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.

## ◆ isMaximal()

template<typename EdgeContainer >
 bool ogdf::Matching::isMaximal ( const Graph & graph, const EdgeContainer & matching, edge & addable )

Checks in time O(|E|) if there are edges that could be added to matching.

Sets addable to such an edge or nullptr if none is found.

Definition at line 65 of file Matching.h.