Open
Graph Drawing
Framework

 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)

Function Documentation

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