CoffmanGrahamRanking.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/layered/AcyclicSubgraphModule.h>
#include <ogdf/layered/RankingModule.h>
 
#include <memory>
 
namespace ogdf {
template<class E1, class E2>
class Tuple2;
template<class E>
class List;
 
 
class OGDF_EXPORT CoffmanGrahamRanking : public RankingModule {
public:
    CoffmanGrahamRanking();
 
 
    virtual void call(const Graph& G, NodeArray<int>& rank) override;
 
    void setSubgraph(AcyclicSubgraphModule* pSubgraph) { m_subgraph.reset(pSubgraph); }
 
 
    int width() const { return m_w; }
 
    void width(int w) { m_w = w; }
 
 
private:
    // CoffmanGraham data structures
    class _int_set {
        int* m_array;
        int m_length;
        int m_index;
 
    public:
        _int_set() : m_array(nullptr), m_length(0), m_index(0) { }
 
        explicit _int_set(int len) : m_array(nullptr), m_length(len), m_index(len) {
            if (len > 0) {
                m_array = new int[m_length];
            }
        }
 
        ~_int_set() { delete[] m_array; }
 
        void init(int len) {
            delete m_array;
            if ((m_length = len) == 0) {
                m_array = nullptr;
            } else {
                m_array = new int[m_length];
            }
            m_index = len;
        }
 
        int length() const { return m_length; }
 
        int operator[](int i) const { return m_array[i]; }
 
        void insert(int x) { m_array[--m_index] = x; }
 
        bool ready() const { return m_index == 0; }
    };
 
    // CoffmanGraham members
    std::unique_ptr<AcyclicSubgraphModule> m_subgraph;
    int m_w;
    NodeArray<_int_set> m_s;
 
    // dfs members
    NodeArray<int> m_mark;
 
    // CoffmanGraham funktions
    void insert(node u, List<Tuple2<node, int>>& ready_nodes);
    void insert(node u, List<node>& ready, const NodeArray<int>& pi);
 
    // dfs funktions
    void removeTransitiveEdges(Graph& G);
    void dfs(node v);
};
 
}