CombinatorialEmbedding.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 <ogdf/basic/comparer.h>
#include <ogdf/basic/internal/config_autogen.h>
#include <ogdf/basic/internal/graph_iterators.h>
#include <ogdf/basic/memory.h>
 
#include <functional>
#include <iosfwd>
 
namespace ogdf {
 
using face = FaceElement*;
 
OGDF_EXPORT std::ostream& operator<<(std::ostream& os, ogdf::face f);
 
// Definition of iterator and container types for adjacency entries in a face
// These declarations are just internal representations
namespace internal {
 
class FaceAdjIterator {
    adjEntry m_adj;
    adjEntry m_adjFirst;
 
public:
    FaceAdjIterator() : m_adj(nullptr), m_adjFirst(nullptr) { }
 
    explicit FaceAdjIterator(adjEntry adj) : m_adj(adj), m_adjFirst(adj) { }
 
    FaceAdjIterator(adjEntry adjFirst, adjEntry adj) : m_adj(adj), m_adjFirst(adjFirst) { }
 
    FaceAdjIterator(const FaceAdjIterator&) = default;
    FaceAdjIterator& operator=(const FaceAdjIterator&) = default;
 
    bool operator==(const FaceAdjIterator& other) const { return m_adj == other.m_adj; }
 
    bool operator!=(const FaceAdjIterator& other) const { return m_adj != other.m_adj; }
 
    adjEntry operator*() const { return m_adj; }
 
    FaceAdjIterator& operator++() {
        OGDF_ASSERT(m_adj != nullptr);
        m_adj = m_adj->faceCycleSucc();
        if (m_adj == m_adjFirst) {
            m_adj = nullptr;
        }
        return *this;
    }
};
 
 
class FaceAdjContainer {
    friend class ogdf::FaceElement;
    friend class ogdf::ConstCombinatorialEmbedding;
    friend class ogdf::CombinatorialEmbedding;
 
    adjEntry m_adjFirst;
 
    FaceAdjContainer() : m_adjFirst(nullptr) { }
 
    explicit FaceAdjContainer(adjEntry adjFirst) : m_adjFirst(adjFirst) { }
 
public:
    using iterator = FaceAdjIterator;
 
    iterator begin() const { return iterator(m_adjFirst); }
 
    iterator end() const { return iterator(); }
};
 
}
 
class OGDF_EXPORT FaceElement : private internal::GraphElement {
    friend class ConstCombinatorialEmbedding;
    friend class CombinatorialEmbedding;
    friend class internal::GraphList<FaceElement>;
 
    //adjEntry m_adjFirst; //!< The first adjacency element in the face.
    int m_id; 
    int m_size; 
 
#ifdef OGDF_DEBUG
    const ConstCombinatorialEmbedding* m_pEmbedding;
#endif
 
#ifdef OGDF_DEBUG
    FaceElement(const ConstCombinatorialEmbedding* pEmbedding, adjEntry adjFirst, int id)
        : m_id(id), m_size(0), m_pEmbedding(pEmbedding), entries(adjFirst) { }
#else
    FaceElement(adjEntry adjFirst, int id) : m_id(id), m_size(0), entries(adjFirst) { }
#endif
 
public:
    internal::FaceAdjContainer entries;
 
    int index() const { return m_id; }
 
    adjEntry firstAdj() const { return entries.m_adjFirst; }
 
    int size() const { return m_size; }
 
    face succ() const { return static_cast<face>(m_next); }
 
    face pred() const { return static_cast<face>(m_prev); }
 
    adjEntry nextFaceEdge(adjEntry adj) const {
        adj = adj->faceCycleSucc();
        return (adj != entries.m_adjFirst) ? adj : nullptr;
    }
 
#ifdef OGDF_DEBUG
    const ConstCombinatorialEmbedding* embeddingOf() const { return m_pEmbedding; }
#endif
 
    static int compare(const FaceElement& x, const FaceElement& y) { return x.m_id - y.m_id; }
    OGDF_AUGMENT_COMPARER(FaceElement)
 
    OGDF_NEW_DELETE
};
 
using CombinatorialEmbeddingRegistry =
        RegistryBase<face, ConstCombinatorialEmbedding, internal::GraphIterator<face>>;
 
template<class Value, bool WithDefault>
class FaceArrayBase : public RegisteredArray<ConstCombinatorialEmbedding, Value, WithDefault> {
    using RA = RegisteredArray<ConstCombinatorialEmbedding, Value, WithDefault>;
 
public:
    using RA::RA;
 
    ConstCombinatorialEmbedding* embeddingOf() const { return RA::registeredAt(); }
};
 
#define OGDF_DECL_REG_ARRAY_TYPE(v, c) FaceArrayBase<v, c>
OGDF_DECL_REG_ARRAY(FaceArray)
#undef OGDF_DECL_REG_ARRAY_TYPE
 
class OGDF_EXPORT ConstCombinatorialEmbedding : public CombinatorialEmbeddingRegistry {
protected:
    const Graph* m_cpGraph; 
 
    int m_faceIdCount; 
 
    AdjEntryArray<face> m_rightFace; 
    face m_externalFace; 
 
public:
    using face_iterator = internal::GraphIterator<face>;
 
    internal::GraphObjectContainer<FaceElement> faces;
 
    ConstCombinatorialEmbedding();
 
 
    explicit ConstCombinatorialEmbedding(const Graph& G);
 
    ConstCombinatorialEmbedding(const ConstCombinatorialEmbedding& C);
 
    ConstCombinatorialEmbedding& operator=(const ConstCombinatorialEmbedding& C);
 
    virtual ~ConstCombinatorialEmbedding();
 
    bool valid() const { return m_cpGraph != nullptr; }
 
 
    const Graph& getGraph() const {
        OGDF_ASSERT(valid());
        return *m_cpGraph;
    }
 
    operator const Graph&() const { return getGraph(); }
 
    face firstFace() const { return faces.head(); }
 
    face lastFace() const { return faces.tail(); }
 
    int numberOfFaces() const { return faces.size(); }
 
 
    face rightFace(adjEntry adj) const { return m_rightFace[adj]; }
 
    face leftFace(adjEntry adj) const { return m_rightFace[adj->twin()]; }
 
    int maxFaceIndex() const { return m_faceIdCount - 1; }
 
    face chooseFace(
            std::function<bool(face)> includeFace = [](face) { return true; },
            bool isFastTest = true) const;
 
    face maximalFace() const;
 
    face externalFace() const { return m_externalFace; }
 
    void setExternalFace(face f) {
        OGDF_ASSERT(f->embeddingOf() == this);
        m_externalFace = f;
    }
 
    bool isBridge(edge e) const {
        return m_rightFace[e->adjSource()] == m_rightFace[e->adjTarget()];
    }
 
 
    void init(const Graph& G);
 
    void init();
 
    void computeFaces();
 
#ifdef OGDF_DEBUG
    void consistencyCheck() const;
#endif
 
    static inline int keyToIndex(face key) { return key->index(); }
 
    bool isKeyAssociated(face key) const {
        if (key == nullptr) {
            return false;
        }
#ifdef OGDF_DEBUG
        if (key->embeddingOf() == this) {
            OGDF_ASSERT(keyToIndex(key) < this->getArraySize());
            return true;
        } else {
            return false;
        }
#else
        return true;
#endif
    }
 
    int calculateArraySize(int add) const { return calculateTableSize(m_faceIdCount + add); }
 
    int maxKeyIndex() const { return (m_faceIdCount)-1; }
 
    face_iterator begin() const { return faces.begin(); }
 
    face_iterator end() const { return faces.end(); }
 
    adjEntry findCommonFace(const node v, const node w, bool left = true) const {
        adjEntry adj;
        return findCommonFace(v, w, adj, left);
    }
 
    adjEntry findCommonFace(const node v, const node w, adjEntry& adjW, bool left = true) const;
 
protected:
    face createFaceElement(adjEntry adjFirst);
};
 
class OGDF_EXPORT CombinatorialEmbedding : public ConstCombinatorialEmbedding {
    friend class GraphCopy;
 
    Graph* m_pGraph; 
 
    // the following methods are explicitly deleted
    // It is not clear which meaning copying of a comb. embedding should
    // have since we only store a pointer to the topology (Graph)
    CombinatorialEmbedding(const CombinatorialEmbedding&) = delete;
    CombinatorialEmbedding& operator=(const CombinatorialEmbedding&) = delete;
 
public:
    CombinatorialEmbedding() : ConstCombinatorialEmbedding() { m_pGraph = nullptr; }
 
    explicit CombinatorialEmbedding(Graph& G) : ConstCombinatorialEmbedding(G) { m_pGraph = &G; }
 
 
 
    const Graph& getGraph() const {
        OGDF_ASSERT(valid());
        return *m_cpGraph;
    }
 
    Graph& getGraph() {
        OGDF_ASSERT(valid());
        return *m_pGraph;
    }
 
    operator const Graph&() const { return getGraph(); }
 
    operator Graph&() { return getGraph(); }
 
 
 
    void init(Graph& G) {
        ConstCombinatorialEmbedding::init(G);
        m_pGraph = &G;
    }
 
    void clear();
 
 
 
 
    edge split(edge e);
 
    void unsplit(edge eIn, edge eOut);
 
    node splitNode(adjEntry adjStartLeft, adjEntry adjStartRight);
 
    node contract(edge e, bool keepSelfLoops = false);
 
    edge splitFace(adjEntry adjSrc, adjEntry adjTgt, bool sourceAfter = false);
 
    edge addEdgeToIsolatedNode(node v, adjEntry adjTgt);
 
    edge addEdgeToIsolatedNode(adjEntry adjSrc, node v);
 
    face joinFaces(edge e);
 
    face joinFaces(adjEntry adj);
 
    void reverseEdge(edge e);
 
    void moveBridge(adjEntry adjBridge, adjEntry adjBefore);
 
    void removeDeg1(node v);
 
    void updateMerger(edge e, face fRight, face fLeft);
 
 
private:
    edge addEdgeToIsolatedNode(adjEntry adj, node v, bool adjSrc);
};
 
}