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>
 
#include <ostream>
 
namespace ogdf {
 
class OGDF_EXPORT Triconnectivity {
    explicit Triconnectivity(Graph* G);
 
public:
    explicit Triconnectivity(const Graph& G) : Triconnectivity(new GraphCopySimple(G)) {
        m_deleteGraph = true;
    };
 
    explicit Triconnectivity(Graph& G, bool modifyG = false)
        : Triconnectivity(modifyG ? &G : new GraphCopySimple(G)) {
        m_deleteGraph = !modifyG;
    };
 
    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;
        }
    };
 
    Graph* m_pG;
    Array<CompStruct> m_component;
 
    int m_numComp;
 
    bool checkComp() const;
 
private:
    bool checkSepPair(edge eVirt) const;
 
    void clearStructures();
 
    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(node v, node u);
    void DFS1(node v, node u, node& s1);
 
    void buildAcceptableAdjStruct();
    void DFS2();
    void pathFinder(node v);
 
 
    bool pathSearch(node init_v, bool fail_fast, node& s1, node& s2);
    void afterRecursivePathSearch(const node v, const int vnum, const int outv,
            const ListIterator<edge> it, const edge e, const node w, int wnum);
    bool afterRecursivePathSearch(const node v, const int vnum, const int outv, const edge e,
            const node w, const int wnum, node& s1, node& s2);
 
    void assembleTriconnectedComponents();
 
    void printOs(edge e) const;
    void printStacks() const;
 
    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);
        }
    }
 
    template<typename T>
    T GCoriginal(T n) const {
        if (m_deleteGraph) {
            // TODO use common superclass of all GraphCopies
            return dynamic_cast<GraphCopySimple*>(m_pG)->original(n);
        } else {
            return n;
        }
    }
 
    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; 
    bool m_deleteGraph; 
};
 
OGDF_EXPORT std::ostream& operator<<(std::ostream& os, Triconnectivity::CompType type);
 
}