BCTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/SList.h>
 
namespace ogdf {
 
class OGDF_EXPORT BCTree {
public:
    enum class GNodeType {
        Normal,
        CutVertex
    };
 
    enum class BNodeType {
        BComp,
        CComp
    };
 
protected:
    Graph& m_G;
 
    Graph m_B;
 
    mutable Graph m_H;
 
    int m_numB;
 
    int m_numC;
 
    NodeArray<bool> m_gNode_isMarked;
 
    NodeArray<node> m_gNode_hNode;
 
    EdgeArray<edge> m_gEdge_hEdge;
 
    NodeArray<BNodeType> m_bNode_type;
 
    mutable NodeArray<bool> m_bNode_isMarked;
 
    NodeArray<node> m_bNode_hRefNode;
 
    NodeArray<node> m_bNode_hParNode;
 
    NodeArray<SList<edge>> m_bNode_hEdges;
 
    NodeArray<int> m_bNode_numNodes;
 
    mutable NodeArray<node> m_hNode_bNode;
 
    mutable EdgeArray<node> m_hEdge_bNode;
 
    NodeArray<node> m_hNode_gNode;
 
    EdgeArray<edge> m_hEdge_gEdge;
 
    int m_count;
 
    NodeArray<int> m_number;
    NodeArray<int> m_lowpt;
 
    ArrayBuffer<adjEntry> m_eStack;
 
    NodeArray<node> m_gtoh;
 
    SList<node> m_nodes;
 
    void init(node vG);
 
    void initNotConnected(node vG);
 
    void initNotConnected(List<node>& vG);
 
    void biComp(adjEntry adjuG, node vG);
 
    virtual node parent(node vB) const;
 
    node findNCA(node uB, node vB) const;
 
 
public:
    explicit BCTree(Graph& G, bool callInitConnected = false)
        : m_G(G), m_eStack(G.numberOfEdges()) {
        if (!callInitConnected) {
            init(G.firstNode());
        } else {
            initNotConnected(G.firstNode());
        }
    }
 
    BCTree(Graph& G, node vG, bool callInitConnected = false)
        : m_G(G), m_eStack(G.numberOfEdges()) {
        if (!callInitConnected) {
            init(vG);
        } else {
            initNotConnected(vG);
        }
    }
 
    BCTree(Graph& G, List<node>& vG) : m_G(G), m_eStack(G.numberOfEdges()) { initNotConnected(vG); }
 
    virtual ~BCTree() { }
 
    const Graph& originalGraph() const { return m_G; }
 
    const Graph& bcTree() const { return m_B; }
 
    const Graph& auxiliaryGraph() const { return m_H; }
 
 
    int numberOfBComps() const { return m_numB; }
 
    int numberOfCComps() const { return m_numC; }
 
 
    GNodeType typeOfGNode(node vG) const {
        return m_bNode_type[m_hNode_bNode[m_gNode_hNode[vG]]] == BNodeType::BComp
                ? GNodeType::Normal
                : GNodeType::CutVertex;
    }
 
    virtual node bcproper(node vG) const { return m_hNode_bNode[m_gNode_hNode[vG]]; }
 
    virtual node bcproper(edge eG) const { return m_hEdge_bNode[m_gEdge_hEdge[eG]]; }
 
    node rep(node vG) const { return m_gNode_hNode[vG]; }
 
    edge rep(edge eG) const { return m_gEdge_hEdge[eG]; }
 
 
    node original(node vH) { return m_hNode_gNode[vH]; }
 
    edge original(edge eH) const { return m_hEdge_gEdge[eH]; }
 
 
    BNodeType typeOfBNode(node vB) const { return m_bNode_type[vB]; }
 
    const SList<edge>& hEdges(node vB) const { return m_bNode_hEdges[vB]; }
 
    int numberOfEdges(node vB) const { return m_bNode_hEdges[vB].size(); }
 
    int numberOfNodes(node vB) const { return m_bNode_numNodes[vB]; }
 
 
    node bComponent(node uG, node vG) const;
 
    SList<node>& findPath(node sG, node tG) const;
 
    SList<node>* findPathBCTree(node sB, node tB) const;
 
    virtual node repVertex(node uG, node vB) const;
 
    virtual node cutVertex(node uB, node vB) const;
 
private:
    BCTree(const BCTree&) = delete;
 
    BCTree& operator=(const BCTree&) = delete;
 
    void initBasic(node vG);
    void initEdges();
};
 
}