DynamicSPQRForest.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_DYNAMIC_SPQR_FOREST_H
#define OGDF_DYNAMIC_SPQR_FOREST_H

#include <ogdf/decomposition/DynamicBCTree.h>
#include <ogdf/decomposition/SPQRTree.h>

namespace ogdf {

class OGDF_EXPORT DynamicSPQRForest : public DynamicBCTree {

public:

    enum TNodeType {
        SComp = SPQRTree::SNode,
        PComp = SPQRTree::PNode,
        RComp = SPQRTree::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 ();
    void createSPQR (node vB) const;

    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:

    DynamicSPQRForest (Graph& G) : DynamicBCTree(G) { init(); }

    node spqrproper (edge eH) const { return m_hEdge_tNode[eH] = findSPQR(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);
    node updateInsertedNode (edge eG, edge fG);

};

}

#endif