DynamicSPQRForest.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/decomposition/DynamicBCTree.h>
#include <ogdf/decomposition/SPQRTree.h>
 
#include <iosfwd>
 
namespace ogdf {
template<class E>
class SList;
 
class OGDF_EXPORT DynamicSPQRForest : public DynamicBCTree {
public:
    enum class TNodeType {
        SComp = static_cast<int>(
                SPQRTree::NodeType::SNode), 
        PComp = static_cast<int>(
                SPQRTree::NodeType::PNode), 
        RComp = static_cast<int>(
                SPQRTree::NodeType::RNode) 
    };
 
protected:
    mutable Graph m_T;
 
    mutable NodeArray<node> m_bNode_SPQR;
 
    mutable NodeArray<int> m_bNode_numS;
 
    mutable NodeArray<int> m_bNode_numP;
 
    mutable NodeArray<int> m_bNode_numR;
 
    mutable NodeArray<TNodeType> m_tNode_type;
 
    mutable NodeArray<node> m_tNode_owner;
 
    mutable NodeArray<edge> m_tNode_hRefEdge;
 
    mutable NodeArray<List<edge>*> m_tNode_hEdges;
 
    mutable EdgeArray<ListIterator<edge>> m_hEdge_position;
 
    mutable EdgeArray<node> m_hEdge_tNode;
 
    mutable EdgeArray<edge> m_hEdge_twinEdge;
 
    mutable NodeArray<node> m_htogc;
 
    mutable NodeArray<bool> m_tNode_isMarked;
 
    void init();
 
    inline node newSPQRNode(node vB, const TNodeType spqrNodeType) const {
        node vT = m_T.newNode();
        m_tNode_owner[vT] = vT;
        m_tNode_type[vT] = spqrNodeType;
        m_tNode_hEdges[vT] = new List<edge>;
 
        if (spqrNodeType == TNodeType::PComp) {
            m_bNode_numP[vB]++;
        } else if (spqrNodeType == TNodeType::SComp) {
            m_bNode_numS[vB]++;
        } else if (spqrNodeType == TNodeType::RComp) {
            m_bNode_numR[vB]++;
        }
 
        return vT;
    }
 
    inline void addHEdge(edge eH, node vT) const {
        m_hEdge_position[eH] = m_tNode_hEdges[vT]->pushBack(eH);
        m_hEdge_tNode[eH] = vT;
    }
 
    inline void delHEdge(edge eH, node vT) const {
        m_tNode_hEdges[vT]->del(m_hEdge_position[eH]);
        m_H.delEdge(eH);
    }
 
    inline edge newTwinEdge(edge eH, node vT) const {
        edge fH = m_H.newEdge(eH->source(), eH->target());
        addHEdge(fH, vT);
        m_hEdge_twinEdge[eH] = fH;
        m_hEdge_twinEdge[fH] = eH;
        return fH;
    }
 
    node uniteSPQR(node vB, node sT, node tT);
 
    node findSPQR(node vT) const;
 
    node findNCASPQR(node sT, node tT) const;
 
    SList<node>& findPathSPQR(node sH, node tH, node& rT) const;
 
    edge updateInsertedEdgeSPQR(node vB, edge eG);
 
    node updateInsertedNodeSPQR(node vB, edge eG, edge fG);
 
public:
    explicit DynamicSPQRForest(Graph& G, bool not_connected = false)
        : DynamicSPQRForest(G, nullptr, not_connected) { }
 
    DynamicSPQRForest(Graph& G, node vG, bool not_connected = false)
        : DynamicBCTree(G, vG, not_connected) {
        init();
    }
 
    ~DynamicSPQRForest() {
        for (auto pList : m_tNode_hEdges) {
            delete pList;
        }
    }
 
    node spqrproper(edge eH) const { return m_hEdge_tNode[eH] = findSPQR(m_hEdge_tNode[eH]); }
 
    void createSPQR(node vB) const;
 
    node spqrroot(node vB) const { return m_bNode_SPQR[vB]; }
 
    int numberOfSNodes(node vB) const { return m_bNode_numS[vB]; }
 
    int numberOfPNodes(node vB) const { return m_bNode_numP[vB]; }
 
    int numberOfRNodes(node vB) const { return m_bNode_numR[vB]; }
 
    const Graph& spqrTree() const { return m_T; }
 
    node spqrParent(node vT) const {
        edge p_e = m_tNode_hRefEdge[vT];
        if (p_e == nullptr) {
            return nullptr;
        }
        edge p_et = twinEdge(p_e);
        OGDF_ASSERT(p_et != nullptr);
        node p = m_hEdge_tNode[p_et];
        OGDF_ASSERT(p != nullptr);
        OGDF_ASSERT(m_T.searchEdge(vT, p) != nullptr);
        return p;
    }
 
    edge spqrParentEdge(node vT) const { return m_tNode_hRefEdge[vT]; }
 
    node spqrNodeOf(edge eH) const { return m_hEdge_tNode[eH]; }
 
    edge twinEdge(edge eH) const { return m_hEdge_twinEdge[eH]; }
 
 
    TNodeType typeOfTNode(node vT) const { return m_tNode_type[vT]; }
 
    const List<edge>& hEdgesSPQR(node vT) const { return *m_tNode_hEdges[vT]; }
 
    SList<node>& findPathSPQR(node sH, node tH) const;
 
    edge virtualEdge(node vT, node wT) const;
 
    edge updateInsertedEdge(edge eG) override;
 
    node updateInsertedNode(edge eG, edge fG) override;
 
};
 
OGDF_EXPORT std::ostream& operator<<(std::ostream& os, DynamicSPQRForest::TNodeType t);
 
}