GraphCopy.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/DualGraph.h>
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/SList.h>
 
namespace ogdf {
 
template<bool>
class FaceSet;
 
class OGDF_EXPORT GraphCopyBase : public Graph {
protected:
    const Graph* m_pGraph = nullptr; 
    NodeArray<node> m_vOrig; 
    EdgeArray<edge> m_eOrig; 
    NodeArray<node> m_vCopy; 
    bool m_linkCopiesOnInsert =
            true; 
 
public:
    GraphCopyBase() = default;
 
    GraphCopyBase(const GraphCopyBase& other) = delete;
 
    GraphCopyBase(GraphCopyBase&& other) noexcept = delete;
 
    GraphCopyBase& operator=(const GraphCopyBase& other) = delete;
 
    GraphCopyBase& operator=(GraphCopyBase&& other) noexcept = delete;
 
    void init(const Graph& G) {
        Graph::clear();
        setOriginalGraph(&G);
        insert(G);
    }
 
    void init(const Graph* G) {
        Graph::clear();
        setOriginalGraph(G);
        if (G != nullptr) {
            insert(*G);
        }
    }
 
    OGDF_DEPRECATED("setOriginalGraph() should be used instead.")
 
    void createEmpty(const Graph& G) { setOriginalGraph(&G); }
 
    virtual void setOriginalGraph(const Graph* G) = 0;
 
    void setOriginalGraph(const Graph& G) { setOriginalGraph(&G); };
 
    const Graph* getOriginalGraph() const { return m_pGraph; }
 
    void clear() override = 0;
 
    const Graph& original() const {
        OGDF_ASSERT(m_pGraph != nullptr);
        return *m_pGraph;
    }
 
    node original(node v) const { return m_vOrig[v]; }
 
    edge original(edge e) const { return m_eOrig[e]; }
 
    adjEntry original(adjEntry adj) const {
        edge f = m_eOrig[adj->theEdge()];
        return adj->isSource() ? f->adjSource() : f->adjTarget();
    }
 
    node copy(node v) const { return m_vCopy[v]; }
 
    virtual edge copy(edge e) const = 0;
 
    virtual adjEntry copy(adjEntry adj) const = 0;
 
    bool isDummy(node v) const { return m_vOrig[v] == nullptr; }
 
    bool isDummy(edge e) const { return m_eOrig[e] == nullptr; }
 
    bool isDummy(adjEntry adj) const { return isDummy(adj->theEdge()); }
 
    node newNode(node vOrig) {
        OGDF_ASSERT(vOrig != nullptr);
        OGDF_ASSERT(vOrig->graphOf() == m_pGraph);
        node v = Graph::newNode();
        m_vCopy[m_vOrig[v] = vOrig] = v;
        return v;
    }
 
    using Graph::newNode;
 
    void delNode(node v) override {
        node vOrig = m_vOrig[v];
        Graph::delNode(v);
        if (vOrig != nullptr) {
            m_vCopy[vOrig] = nullptr;
        }
    }
 
 
    virtual void setOriginalEmbedding() = 0;
 
    bool getLinkCopiesOnInsert() const { return m_linkCopiesOnInsert; }
 
 
    void setLinkCopiesOnInsert(bool linkCopiesOnInsert) {
        m_linkCopiesOnInsert = linkCopiesOnInsert;
    }
 
protected:
    void* preInsert(bool copyEmbedding, bool copyIDs, bool notifyObservers, bool edgeFilter,
            NodeArray<node>& nodeMap, EdgeArray<edge>& edgeMap, int* newNodes,
            int* newEdges) override;
 
    void nodeInserted(void* userData, node original, node copy) override;
};
 
class OGDF_EXPORT GraphCopySimple : public GraphCopyBase {
public:
    EdgeArray<edge> m_eCopy; 
 
    explicit GraphCopySimple() : GraphCopySimple(nullptr) { }
 
    explicit GraphCopySimple(const Graph& G) : GraphCopySimple(&G) { }
 
    explicit GraphCopySimple(const Graph* G) : GraphCopyBase() {
        if (G) {
            init(*G);
        }
    }
 
    GraphCopySimple(const GraphCopySimple& other) : GraphCopyBase() { *this = other; }
 
    GraphCopySimple& operator=(const GraphCopySimple& other);
 
    using GraphCopyBase::setOriginalGraph;
 
    void setOriginalGraph(const Graph* G) override;
 
    void clear() override;
 
    using GraphCopyBase::copy;
 
    edge copy(edge e) const override { return m_eCopy[e]; }
 
    adjEntry copy(adjEntry adj) const override {
        edge f = m_eCopy[adj->theEdge()];
        if (f == nullptr) {
            return nullptr;
        }
        return adj->isSource() ? f->adjSource() : f->adjTarget();
    }
 
    edge newEdge(edge eOrig) {
        OGDF_ASSERT(eOrig != nullptr);
        OGDF_ASSERT(eOrig->graphOf() == m_pGraph);
 
        edge e = Graph::newEdge(m_vCopy[eOrig->source()], m_vCopy[eOrig->target()]);
        m_eCopy[m_eOrig[e] = eOrig] = e;
 
        return e;
    }
 
    using Graph::newEdge;
 
    void delEdge(edge e) override;
 
    void setOriginalEmbedding() override;
 
    void copyEmbeddingToOriginal(Graph& orig) const;
 
protected:
    void edgeInserted(void* userData, edge original, edge copy) override;
};
 
class OGDF_EXPORT GraphCopy : public GraphCopyBase {
protected:
    EdgeArray<ListIterator<edge>> m_eIterator; 
    EdgeArray<List<edge>> m_eCopy; 
 
public:
    explicit GraphCopy() : GraphCopy(nullptr) { }
 
    explicit GraphCopy(const Graph& G) : GraphCopy(&G) { }
 
    explicit GraphCopy(const Graph* G) : GraphCopyBase() {
        if (G) {
            init(*G);
        }
    }
 
    GraphCopy(const GraphCopy& other) : GraphCopyBase() { *this = other; }
 
    GraphCopy& operator=(const GraphCopy& other);
 
    using GraphCopyBase::setOriginalGraph;
 
 
    void setOriginalGraph(const Graph* G) override;
 
    void clear() override;
 
 
    const List<edge>& chain(edge e) const { return m_eCopy[e]; }
 
    using GraphCopyBase::copy;
 
    edge copy(edge e) const override { return m_eCopy[e].empty() ? nullptr : m_eCopy[e].front(); }
 
    adjEntry copy(adjEntry adj) const override {
        auto& el = m_eCopy[adj->theEdge()];
        if (el.empty()) {
            return nullptr;
        } else if (adj->isSource()) {
            return el.front()->adjSource();
        } else {
            return el.back()->adjTarget();
        }
    }
 
    bool isReversed(edge e) const { return e->source() != original(copy(e)->source()); }
 
    bool isReversedCopyEdge(edge e) const;
 
 
    void delEdge(edge e) override;
 
    edge split(edge e) override;
 
    void unsplit(edge eIn, edge eOut) override;
 
    edge newEdge(edge eOrig);
 
    using Graph::newEdge;
 
 
    void setEdge(edge eOrig, edge eCopy);
 
    void setOriginalEmbedding() override;
 
    void removePseudoCrossings();
 
    bool hasSameEdgesCrossings() const;
 
    bool hasAdjacentEdgesCrossings() const;
 
 
    inline bool hasNonSimpleCrossings() const {
        return hasAdjacentEdgesCrossings() || hasSameEdgesCrossings();
    };
 
    void removeNonSimpleCrossings(SListPure<edge>& edgesToCheck,
            DynamicDualGraph* dualGraph = nullptr);
 
    inline void removeNonSimpleCrossings(DynamicDualGraph* dualGraph = nullptr) {
        SListPure<edge> edgesToCheck;
        m_pGraph->allEdges(edgesToCheck);
        removeNonSimpleCrossings(edgesToCheck, dualGraph);
    };
 
    inline void removeNonSimpleCrossings(node origNode, DynamicDualGraph* dualGraph = nullptr) {
        SListPure<edge> edgesToCheck;
        for (adjEntry adj : origNode->adjEntries) {
            edgesToCheck.pushBack(adj->theEdge());
        }
        removeNonSimpleCrossings(edgesToCheck, dualGraph);
    }
 
 
    void insertEdgePath(edge eOrig, const SList<adjEntry>& crossedEdges);
 
    void insertEdgePath(node srcOrig, node tgtOrig, const SList<adjEntry>& crossedEdges);
 
 
    void removeEdgePath(edge eOrig);
 
 
    edge insertCrossing(edge& crossingEdge, edge crossedEdge, bool rightToLeft);
 
 
 
    edge newEdge(node v, adjEntry adj, edge eOrig, CombinatorialEmbedding& E);
 
 
    void insertEdgePathEmbedded(edge eOrig, CombinatorialEmbedding& E,
            const SList<adjEntry>& crossedEdges);
 
    void insertEdgePathEmbedded(edge eOrig, CombinatorialEmbedding& E, DynamicDualGraph& dual,
            const SList<adjEntry>& crossedEdges);
 
 
    void removeEdgePathEmbedded(CombinatorialEmbedding& E, edge eOrig, FaceSet<false>& newFaces);
 
    void removeEdgePathEmbedded(CombinatorialEmbedding& E, DynamicDualGraph& dual, edge eOrig);
 
 
 
#ifdef OGDF_DEBUG
    void consistencyCheck() const;
#endif
 
 
protected:
    void edgeInserted(void* userData, edge original, edge copy) override;
 
 
    void removeUnnecessaryCrossing(adjEntry adjA1, adjEntry adjA2, adjEntry adjB1, adjEntry adjB2);
 
    void removeUnnecessaryCrossing(adjEntry adj, DynamicDualGraph* dualGraph);
 
    void removeAdjacentEdgesCrossing(adjEntry adj1, adjEntry adj2, DynamicDualGraph* dualGraph);
 
    void removeSameEdgesCrossing(adjEntry adjFirstCrossing1, adjEntry adjFirstCrossing2,
            adjEntry adjSecondCrossing1, adjEntry adjSecondCrossing2, DynamicDualGraph* dualGraph);
 
    void swapOriginalEdgesAtCrossing(adjEntry adjCopy1, adjEntry adjCopy2,
            DynamicDualGraph* dual = nullptr);
 
    void swapOriginalEdgesBetweenCrossings(adjEntry adjFirstCrossing1, adjEntry adjFirstCrossing2,
            adjEntry adjSecondCrossing1, adjEntry adjSecondCrossing2,
            DynamicDualGraph* dual = nullptr);
 
    void setOriginalEdgeAlongCrossings(adjEntry adjCopy1, adjEntry adjCopy2, node vCopy,
            edge eOrig1, edge eOrig2);
};
 
OGDF_EXPORT void copyEmbedding(const Graph& from, Graph& to,
        std::function<adjEntry(adjEntry)> adjMapFromTo);
 
}