LayerBasedUPRLayout.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/layered/FastHierarchyLayout.h>
#include <ogdf/layered/HierarchyLayoutModule.h>
#include <ogdf/layered/OptimalRanking.h>
#include <ogdf/layered/RankingModule.h>
#include <ogdf/upward/UPRLayoutModule.h>
 
#include <memory>
 
namespace ogdf {
class GraphAttributes;
class Hierarchy;
class HierarchyLevels;
class UpwardPlanRep;
template<class E>
class SListPure;
 
class OrderComparer {
public:
    OrderComparer(const UpwardPlanRep& _UPR, Hierarchy& _H);
 
    bool less(node vH1, node vH2) const;
 
private:
    const UpwardPlanRep& m_UPR;
    Hierarchy& H;
    NodeArray<int> m_dfsNum;
#if 0
    EdgeArray<int> outEdgeOrder;
#endif
    mutable NodeArray<bool> crossed;
 
    void dfs_LR(edge e, NodeArray<bool>& visited, NodeArray<int>& dfsNum, int& num);
 
    bool left(node vUPR1, 
            const List<edge>& chain1, 
            node vUPR2, 
            const List<edge>& chain2 
    ) const;
 
    bool left(edge e1UPR, edge e2UPR) const;
 
    bool left(List<edge>& chain1, List<edge>& chain2, int level) const;
 
    bool checkUp(node vUPR, int level) const;
};
 
class OGDF_EXPORT LayerBasedUPRLayout : public UPRLayoutModule {
public:
    // constructor: sets options to default values
    LayerBasedUPRLayout() {
        // set default value
        FastHierarchyLayout* fhl = new FastHierarchyLayout();
        fhl->nodeDistance(40.0);
        fhl->layerDistance(40.0);
        fhl->fixedLayerDistance(true);
        m_layout.reset(fhl);
        OptimalRanking* opRank = new OptimalRanking();
        opRank->separateMultiEdges(false);
        m_ranking.reset(opRank);
        m_numLevels = 0;
        m_maxLevelSize = 0;
    }
 
    // destructor
    ~LayerBasedUPRLayout() { }
 
    // returns the number of crossings in the layout after the algorithm
    // has been applied
    int numberOfCrossings() const { return m_crossings; }
 
    // module option for the computation of the final layout
    void setLayout(HierarchyLayoutModule* pLayout) { m_layout.reset(pLayout); }
 
    void setRanking(RankingModule* pRanking) { m_ranking.reset(pRanking); }
 
    void UPRLayoutSimple(const UpwardPlanRep& UPR, GraphAttributes& AG);
 
    int numberOfLayers() { return m_numLevels; }
 
    int maxLayerSize() { return m_maxLevelSize; }
 
protected:
    /*
     * @param UPR is the upward planarized representation of the input graph.
     * @param AG has to be assigned the hierarchy layout.
     */
    virtual void doCall(const UpwardPlanRep& UPR, GraphAttributes& AG) override;
 
    int m_crossings;
 
    std::unique_ptr<RankingModule> m_ranking;
 
    std::unique_ptr<HierarchyLayoutModule> m_layout;
 
private:
    // compute a ranking of the nodes of UPR.
    // Precond. a ranking module muss be set
    void computeRanking(const UpwardPlanRep& UPR, NodeArray<int>& rank);
 
 
    void postProcessing_sourceReorder(HierarchyLevels& levels, List<node>& sources);
 
    void postProcessing_reduceLED(Hierarchy& H, HierarchyLevels& levels, const List<node>& sources) {
        for (node s : sources) {
            postProcessing_reduceLED(H, levels, s);
        }
    }
 
    void postProcessing_reduceLED(Hierarchy& H, HierarchyLevels& levels, node vH);
 
    void post_processing_reduce(Hierarchy& H, HierarchyLevels& levels, int& i, node s, int minIdx,
            int maxIdx, NodeArray<bool>& markedNodes);
 
    void postProcessing_markUp(HierarchyLevels& levels, node sH, NodeArray<bool>& markedNodes);
 
 
    void post_processing_deleteLvl(Hierarchy& H, HierarchyLevels& levels, int i);
 
    void post_processing_deleteInterval(Hierarchy& H, HierarchyLevels& levels, int beginIdx,
            int endIdx, int& j);
 
    void post_processing_CopyInterval(Hierarchy& H, HierarchyLevels& levels, int i, int beginIdx,
            int endIdx, int pos);
 
    int m_numLevels;
    int m_maxLevelSize;
    ArrayBuffer<node> m_dummies;
 
 
 
    void callSimple(GraphAttributes& AG, adjEntry adj //left most edge of the source
    );
 
    // needed for UPRLayoutSimple
    void dfsSortLevels(adjEntry adj1, const NodeArray<int>& rank, Array<SListPure<node>>& nodes);
 
    // needed for UPRLayoutSimple
    void longestPathRanking(const Graph& G, NodeArray<int>& rank);
 
};
 
}