ShellingOrder.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
 
namespace ogdf {
template<class E>
class List;
 
class ShellingOrderSet : public Array<node> {
public:
    ShellingOrderSet() : Array<node>() {
        m_leftVertex = m_rightVertex = nullptr;
        m_leftAdj = m_rightAdj = nullptr;
    }
 
 
    ShellingOrderSet(int n, adjEntry adjL = nullptr, adjEntry adjR = nullptr) : Array<node>(1, n) {
        m_leftVertex = (adjL != nullptr) ? adjL->twinNode() : nullptr;
        m_rightVertex = (adjR != nullptr) ? adjR->twinNode() : nullptr;
        m_leftAdj = adjL;
        m_rightAdj = adjR;
    }
 
    node left() const { return m_leftVertex; }
 
    node right() const { return m_rightVertex; }
 
    adjEntry leftAdj() const { return m_leftAdj; }
 
    adjEntry rightAdj() const { return m_rightAdj; }
 
    bool hasLeft() const { return m_leftAdj != nullptr; }
 
    bool hasRight() const { return m_rightAdj != nullptr; }
 
    void left(node cl) { m_leftVertex = cl; }
 
    void right(node cr) { m_rightVertex = cr; }
 
    void leftAdj(adjEntry adjL) { m_leftAdj = adjL; }
 
    void rightAdj(adjEntry adjR) { m_rightAdj = adjR; }
 
    int len() const { return high(); }
 
    node operator[](const int i) const { return Array<node>::operator[](i); }
 
    node& operator[](const int i) { return Array<node>::operator[](i); }
 
 
private:
    node m_leftVertex; 
    node m_rightVertex; 
    adjEntry m_leftAdj; 
    adjEntry m_rightAdj; 
};
 
class OGDF_EXPORT ShellingOrder {
public:
    ShellingOrder() { m_pGraph = nullptr; }
 
#if 0
    ShellingOrder(const Graph &G, const List<ShellingOrderSet> &partition);
#endif
 
    ~ShellingOrder() { }
 
    const Graph& getGraph() const { return *m_pGraph; }
 
    int length() const { return m_V.high(); }
 
    int len(int i) const { return m_V[i].len(); }
 
    node operator()(int i, int j) const { return (m_V[i])[j]; }
 
    const ShellingOrderSet& operator[](int i) const { return m_V[i]; }
 
    node left(int i) const { return m_V[i].left(); }
 
    node right(int i) const { return m_V[i].right(); }
 
    int rank(node v) const { return m_rank[v]; }
 
    void init(const Graph& G, const List<ShellingOrderSet>& partition);
 
    void initLeftmost(const Graph& G, const List<ShellingOrderSet>& partition);
 
 
    void push(int k, node v, node tgt);
 
    friend class CompOrderBic;
 
private:
    const Graph* m_pGraph; 
    Array<ShellingOrderSet> m_V; 
    NodeArray<int> m_rank; 
};
 
}