GraphCopy.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/DualGraph.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);
};
 
}