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 b>
class FaceSet;
 
class OGDF_EXPORT GraphCopySimple : public Graph {
    const Graph* m_pGraph; 
    NodeArray<node> m_vOrig; 
    NodeArray<node> m_vCopy; 
    EdgeArray<edge> m_eOrig; 
    EdgeArray<edge> m_eCopy; 
 
public:
    GraphCopySimple();
 
    explicit GraphCopySimple(const Graph& G);
 
    GraphCopySimple(const GraphCopySimple& GC);
 
    virtual ~GraphCopySimple() { }
 
    void init(const Graph& G);
 
    void createEmpty(const Graph& G);
 
    const Graph& original() const { 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]; }
 
    edge copy(edge e) const { return m_eCopy[e]; }
 
    adjEntry copy(adjEntry adj) const {
        edge f = m_eCopy[adj->theEdge()];
        if (f == nullptr) {
            return nullptr;
        }
        return adj->isSource() ? f->adjSource() : f->adjTarget();
    }
 
    bool isDummy(node v) const { return m_vOrig[v] == nullptr; }
 
    bool isDummy(edge e) const { return m_eOrig[e] == nullptr; }
 
    GraphCopySimple& operator=(const GraphCopySimple& GC);
 
    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;
 
    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;
 
    virtual void delEdge(edge e) override;
 
    virtual void delNode(node v) override;
 
private:
    void initGC(const GraphCopySimple& GC, NodeArray<node>& vCopy, EdgeArray<edge>& eCopy);
};
 
class OGDF_EXPORT GraphCopy : public Graph {
protected:
    const Graph* m_pGraph; 
    NodeArray<node> m_vOrig; 
    EdgeArray<edge> m_eOrig; 
    EdgeArray<ListIterator<edge>> m_eIterator; 
 
    NodeArray<node> m_vCopy; 
    EdgeArray<List<edge>> m_eCopy; 
 
public:
 
    explicit GraphCopy(const Graph& G);
 
    GraphCopy() : Graph(), m_pGraph(nullptr) { }
 
 
    GraphCopy(const GraphCopy& GC);
 
    virtual ~GraphCopy() { }
 
 
    const Graph& original() const { 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 e = adj->theEdge();
        edge f = m_eOrig[e];
 
        if (adj->isSource()) {
            OGDF_ASSERT(m_eCopy[f].front() == e);
            return f->adjSource();
        } else {
            OGDF_ASSERT(m_eCopy[f].back() == e);
            return f->adjTarget();
        }
    }
 
    node copy(node v) const { return m_vCopy[v]; }
 
    const List<edge>& chain(edge e) const { return m_eCopy[e]; }
 
    // returns first edge in chain(e)
    edge copy(edge e) const { return m_eCopy[e].empty() ? nullptr : m_eCopy[e].front(); }
 
    adjEntry copy(adjEntry adj) const {
        edge e = adj->theEdge();
 
        if (adj->isSource()) {
            return m_eCopy[e].front()->adjSource();
        } else {
            return m_eCopy[e].back()->adjTarget();
        }
    }
 
    bool isDummy(node v) const { return m_vOrig[v] == nullptr; }
 
    bool isDummy(edge e) const { return m_eOrig[e] == nullptr; }
 
    bool isReversed(edge e) const { return e->source() != original(copy(e)->source()); }
 
    bool isReversedCopyEdge(edge e) const;
 
 
    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;
 
    virtual void delNode(node v) override;
 
    virtual void delEdge(edge e) override;
 
 
    virtual void clear() override;
 
    virtual 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);
 
    OGDF_DEPRECATED("Use ogdf::planarEmbed() instead.")
    bool embed();
 
    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 setOriginalEmbedding();
 
 
    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
 
 
    void init(const Graph& G);
 
 
    void createEmpty(const Graph& G);
 
 
    void initByCC(const CCsInfo& info, int cc, EdgeArray<edge>& eCopy);
 
 
    void initByNodes(const List<node>& origNodes, EdgeArray<edge>& eCopy);
 
 
    void initByActiveNodes(const List<node>& nodeList, const NodeArray<bool>& activeNodes,
            EdgeArray<edge>& eCopy);
 
 
 
 
    GraphCopy& operator=(const GraphCopy& GC);
 
 
 
protected:
    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);
 
private:
    void initGC(const GraphCopy& GC, NodeArray<node>& vCopy, EdgeArray<edge>& eCopy);
};
 
}