Simple algorithms for matchings (testing properties, obtaining a maximal matching)
More...
|
| 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.
|
| |
Simple algorithms for matchings (testing properties, obtaining a maximal matching)
◆ findMaximalMatching()
Obtains a maximal matching in O(|E|) time.
◆ findMaximumCardinalityMatching()
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
◆ isMatching()
Checks in time O(|V| + size of matching) if the given set of edges represents a matching.
Definition at line 44 of file Matching.h.
◆ isMaximal()
Checks in time O(|E|) if there are edges that could be added to matching.
Definition at line 91 of file Matching.h.
◆ isMaximalMatching()
Checks in O(|V| + |E|) time if matching is a maximal matching.
Definition at line 99 of file Matching.h.
◆ isPerfect()
Checks in O(1) if matching (assuming it is a matching and the graph is simple and connected) is perfect.
Definition at line 106 of file Matching.h.
◆ isPerfectMatching()
Checks in O(|V| + size of matching) if matching is a perfect matching.
Definition at line 113 of file Matching.h.
