PlanRepExpansion.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/FaceSet.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphSets.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
 
#include <ostream>
 
namespace ogdf {
class CombinatorialEmbedding;
template<class E1, class E2>
class Tuple2;
 
class OGDF_EXPORT PlanRepExpansion : public Graph {
public:
    struct Crossing {
        Crossing() { m_adj = nullptr; }
 
        explicit Crossing(adjEntry adj) { m_adj = adj; }
 
        adjEntry m_adj;
        SList<adjEntry> m_partitionLeft;
        SList<adjEntry> m_partitionRight;
 
        friend std::ostream& operator<<(std::ostream& os, const Crossing& c) {
            os << "(" << c.m_adj << ")";
            return os;
        }
    };
 
    class NodeSplit {
    public:
        NodeSplit() { }
 
        explicit NodeSplit(ListIterator<NodeSplit> it) : m_nsIterator(it) { }
 
        node source() const { return m_path.front()->source(); }
 
        node target() const { return m_path.back()->target(); }
 
        List<edge> m_path; 
        ListIterator<NodeSplit> m_nsIterator; 
    };
 
    using nodeSplit = PlanRepExpansion::NodeSplit*;
 
 
    PlanRepExpansion(const Graph& G);
 
    PlanRepExpansion(const Graph& G, const List<node>& splittableNodes);
 
    ~PlanRepExpansion() { }
 
 
    const Graph& original() const { return *m_pGraph; }
 
    node original(node v) const { return m_vOrig[v]; }
 
    const List<node>& expansion(node vOrig) const { return m_vCopy[vOrig]; }
 
    node copy(node vOrig) const { return m_vCopy[vOrig].front(); }
 
    edge originalEdge(edge e) const { return m_eOrig[e]; }
 
    const List<edge>& chain(edge eOrig) const { return m_eCopy[eOrig]; }
 
    edge copy(edge eOrig) const { return m_eCopy[eOrig].front(); }
 
    bool splittable(node v) const { return m_splittable[v]; }
 
    bool splittableOrig(node vOrig) const { return m_splittableOrig[vOrig]; }
 
    NodeSplit* nodeSplitOf(edge e) const { return m_eNodeSplit[e]; }
 
    int numberOfNodeSplits() const { return m_nodeSplits.size(); }
 
    int numberOfSplittedNodes() const;
 
    List<NodeSplit>& nodeSplits() { return m_nodeSplits; }
 
    List<edge>& setOrigs(edge e, edge& eOrig, nodeSplit& ns);
 
    ListConstIterator<edge> position(edge e) const { return m_eIterator[e]; }
 
    bool isPseudoCrossing(node v) const;
 
    int computeNumberOfCrossings() const;
 
 
 
 
    int numberOfCCs() const { return m_nodesInCC.size(); }
 
    int currentCC() const { return m_currentCC; }
 
    const List<node>& nodesInCC(int i) const { return m_nodesInCC[i]; }
 
    const List<node>& nodesInCC() const { return m_nodesInCC[m_currentCC]; }
 
    void initCC(int i);
 
 
 
 
    edge split(edge e) override;
 
    void unsplit(edge eIn, edge eOut) override;
 
    virtual void delEdge(edge e) override;
 
    bool embed();
 
    void insertEdgePath(edge eOrig, nodeSplit ns, node vStart, node vEnd, List<Crossing>& eip,
            edge eSrc, edge eTgt);
 
    void insertEdgePathEmbedded(edge eOrig, nodeSplit ns, CombinatorialEmbedding& E,
            const List<Tuple2<adjEntry, adjEntry>>& crossedEdges);
 
    void removeEdgePathEmbedded(CombinatorialEmbedding& E, edge eOrig, nodeSplit ns,
            FaceSet<false>& newFaces, NodeSet<false>& mergedNodes, node& oldSrc, node& oldTgt);
 
    void removeEdgePath(edge eOrig, nodeSplit ns, node& oldSrc, node& oldTgt);
 
    void contractSplit(nodeSplit ns, CombinatorialEmbedding& E);
 
    void contractSplit(nodeSplit ns);
 
    edge unsplitExpandNode(node u, edge eContract, edge eExpand, CombinatorialEmbedding& E);
 
    edge unsplitExpandNode(node u, edge eContract, edge eExpand);
 
    edge enlargeSplit(node v, edge e, CombinatorialEmbedding& E);
 
    edge enlargeSplit(node v, edge e);
 
    edge splitNodeSplit(edge e, CombinatorialEmbedding& E);
 
    edge splitNodeSplit(edge e);
 
    void removeSelfLoop(edge e, CombinatorialEmbedding& E);
 
    void removeSelfLoop(edge e);
 
    PlanRepExpansion::nodeSplit convertDummy(node u, node vOrig, PlanRepExpansion::nodeSplit ns);
 
    edge separateDummy(adjEntry adj_1, adjEntry adj_2, node vStraight, bool isSrc);
 
    void resolvePseudoCrossing(node v);
 
 
 
#ifdef OGDF_DEBUG
    void consistencyCheck() const;
#endif
 
 
private:
    void doInit(const Graph& G, const List<node>& splittableNodes);
    void prepareNodeSplit(const SList<adjEntry>& partitionLeft, adjEntry& adjLeft,
            adjEntry& adjRight);
 
    const Graph* m_pGraph; 
    NodeArray<node> m_vOrig; 
    EdgeArray<edge> m_eOrig; 
    EdgeArray<ListIterator<edge>> m_eIterator; 
    EdgeArray<List<edge>> m_eCopy; 
    NodeArray<ListIterator<node>> m_vIterator; 
    NodeArray<List<node>> m_vCopy; 
 
    NodeArray<bool> m_splittable;
    NodeArray<bool> m_splittableOrig;
    EdgeArray<NodeSplit*> m_eNodeSplit;
    List<NodeSplit> m_nodeSplits;
 
    int m_currentCC; 
    int m_numCC; 
 
    Array<List<node>> m_nodesInCC; 
    EdgeArray<edge> m_eAuxCopy; // auxiliary
};
 
}