BCTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
 
#include <iosfwd>
 
namespace ogdf {
template<class E>
class List;
 
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 not_connected = false) : BCTree(G, nullptr, not_connected) {};
 
    BCTree(Graph& G, node vG, bool not_connected = false) : m_G(G), m_eStack(G.numberOfEdges()) {
        if (vG == nullptr) {
            vG = G.firstNode();
        }
        if (not_connected) {
            initNotConnected(vG);
        } else {
            init(vG);
        }
    }
 
    BCTree(Graph& G, List<node>& vG) : m_G(G), m_eStack(G.numberOfEdges()) { initNotConnected(vG); }
 
    virtual ~BCTree() { }
 
    BCTree(const BCTree& copy) = delete;
    BCTree(BCTree&& move) = delete;
    BCTree& operator=(const BCTree& copy) = delete;
    BCTree& operator=(BCTree&& move) = delete;
 
    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;
    }
 
    node bcproper(node vG) const { return bccomp(m_gNode_hNode[vG]); }
 
    node bcproper(edge eG) const { return bccomp(m_gEdge_hEdge[eG]); }
 
    virtual node bccomp(node vH) const { return m_hNode_bNode[vH]; }
 
    virtual node bccomp(edge eH) const { return m_hEdge_bNode[eH]; }
 
    node rep(node vG) const { return m_gNode_hNode[vG]; }
 
    edge rep(edge eG) const { return m_gEdge_hEdge[eG]; }
 
 
    node original(node vH) const { 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;
 
 
#ifdef OGDF_DEBUG
    void consistencyCheck() const;
#endif
 
private:
    void initBasic(node vG);
    void initEdges();
};
 
OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const BCTree::BNodeType& obj);
 
OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const BCTree::GNodeType& obj);
 
}