Matching.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/basic.h>
 
#include <array>
 
namespace ogdf {
template<class E, class INDEX>
class ArrayBuffer;
template<class E>
class List;
 
namespace Matching {
 
template<typename EdgeContainer>
inline bool isMatching(const Graph& graph, const EdgeContainer& matching) {
    NodeArray<bool> covered {graph, false};
 
    for (edge e : matching) {
        for (node v : e->nodes()) {
            if (covered[v]) {
                return false;
            }
            covered[v] = true;
            if (e->isSelfLoop()) {
                break;
            }
        }
    }
 
    return true;
}
 
template<typename EdgeContainer>
bool isMaximal(const Graph& graph, const EdgeContainer& matching, edge& addable) {
    addable = nullptr;
 
    EdgeArray<bool> covered {graph, false};
 
    for (edge e : matching) {
        for (node v : e->nodes()) {
            for (adjEntry adj : v->adjEntries) {
                covered[adj->theEdge()] = true;
            }
        }
    }
 
    for (edge e : graph.edges) {
        if (!covered[e]) {
            addable = e;
            return false;
        }
    }
 
    return true;
}
 
template<typename EdgeContainer>
inline bool isMaximal(const Graph& graph, const EdgeContainer& matching) {
    edge ignored;
    return isMaximal(graph, matching, ignored);
}
 
template<typename EdgeContainer>
inline bool isMaximalMatching(const Graph& graph, const EdgeContainer& matching) {
    return isMatching(graph, matching) && isMaximal(graph, matching);
}
 
template<typename EdgeContainer>
inline bool isPerfect(const Graph& graph, const EdgeContainer& matching) {
    return 2 * int(matching.size()) == graph.numberOfNodes();
}
 
template<typename EdgeContainer>
inline bool isPerfectMatching(const Graph& graph, const EdgeContainer& matching) {
    return isMatching(graph, matching) && isPerfect(graph, matching);
}
 
OGDF_EXPORT void findMaximalMatching(const Graph& graph, ArrayBuffer<edge>& matching);
 
OGDF_EXPORT int findMaximumCardinalityMatching(const Graph& G, const List<node>& U,
        const List<node>& V, EdgeArray<bool>& matching);
 
}
}