# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

Basic Functions for Matchings

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)

## ◆ findMaximalMatching()

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

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

## ◆ isMatching()

template<typename EdgeContainer >
 bool ogdf::Matching::isMatching ( const Graph & graph, const EdgeContainer & matching )
inline

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()

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

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

Definition at line 91 of file Matching.h.

## ◆ isMaximalMatching()

template<typename EdgeContainer >
 bool ogdf::Matching::isMaximalMatching ( const Graph & graph, const EdgeContainer & matching )
inline

Checks in O(|V| + |E|) time if matching is a maximal matching.

Definition at line 99 of file Matching.h.

## ◆ isPerfect()

template<typename EdgeContainer >
 bool ogdf::Matching::isPerfect ( const Graph & graph, const EdgeContainer & matching )
inline

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()

template<typename EdgeContainer >
 bool ogdf::Matching::isPerfectMatching ( const Graph & graph, const EdgeContainer & matching )
inline

Checks in O(|V| + size of matching) if matching is a perfect matching.

Definition at line 113 of file Matching.h.