Triconnectivity.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/NodeArray.h>
 
namespace ogdf {
 
class OGDF_EXPORT Triconnectivity {
public:
    explicit Triconnectivity(const Graph& G);
 
    Triconnectivity(const Graph& G, bool& isTric, node& s1, node& s2);
 
    Triconnectivity(const Triconnectivity&) = delete;
 
    ~Triconnectivity();
 
    enum class CompType { bond, polygon, triconnected };
 
    struct CompStruct {
        List<edge> m_edges;
        CompType m_type;
 
        CompStruct& operator<<(edge e) {
            m_edges.pushBack(e);
            return *this;
        }
 
        void finishTricOrPoly(edge e) {
            m_edges.pushBack(e);
            m_type = (m_edges.size() >= 4) ? CompType::triconnected : CompType::polygon;
        }
    };
 
    GraphCopySimple* m_pGC;
    Array<CompStruct> m_component;
    int m_numComp;
 
    bool checkComp();
 
 
private:
    bool checkSepPair(edge eVirt);
 
    void splitMultiEdges();
 
    int *m_TSTACK_h, *m_TSTACK_a, *m_TSTACK_b;
    int m_top;
 
    void TSTACK_push(int h, int a, int b) {
        m_TSTACK_h[++m_top] = h;
        m_TSTACK_a[m_top] = a;
        m_TSTACK_b[m_top] = b;
    }
 
    void TSTACK_pushEOS() { m_TSTACK_a[++m_top] = -1; }
 
    bool TSTACK_notEOS() { return m_TSTACK_a[m_top] != -1; }
 
    CompStruct& newComp() { return m_component[m_numComp++]; }
 
    CompStruct& newComp(CompType t) {
        CompStruct& C = m_component[m_numComp++];
        C.m_type = t;
        return C;
    }
 
    enum class EdgeType { unseen, tree, frond, removed };
 
    void DFS1(const Graph& G, node v, node u);
    void DFS1(const Graph& G, node v, node u, node& s1);
 
    void buildAcceptableAdjStruct(const Graph& G);
    void DFS2(const Graph& G);
    void pathFinder(const Graph& G, node v);
 
    void pathSearch(const Graph& G, node v);
 
    bool pathSearch(const Graph& G, node v, node& s1, node& s2);
 
    void assembleTriconnectedComponents();
 
    void printOs(edge e);
    void printStacks();
 
    int high(node v) { return (m_HIGHPT[v].empty()) ? 0 : m_HIGHPT[v].front(); }
 
    void delHigh(edge e) {
        ListIterator<int> it = m_IN_HIGH[e];
        if (it.valid()) {
            node v = e->target();
            m_HIGHPT[v].del(it);
        }
    }
 
    NodeArray<int> m_NUMBER; 
    NodeArray<int> m_LOWPT1;
    NodeArray<int> m_LOWPT2;
    NodeArray<int> m_ND; 
    NodeArray<int> m_DEGREE; 
    Array<node> m_NODEAT; 
    NodeArray<node> m_FATHER; 
    EdgeArray<EdgeType> m_TYPE; 
    NodeArray<List<edge>> m_A; 
    NodeArray<int> m_NEWNUM; 
    EdgeArray<bool> m_START; 
    NodeArray<edge> m_TREE_ARC; 
    NodeArray<List<int>> m_HIGHPT; 
    EdgeArray<ListIterator<edge>> m_IN_ADJ; 
    EdgeArray<ListIterator<int>> m_IN_HIGH; 
    ArrayBuffer<edge> m_ESTACK; 
 
    node m_start; 
    int m_numCount; 
    bool m_newPath; 
};
 
}