BlockOrder.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/layered/CrossingMinInterfaces.h>
 
namespace ogdf {
 
class ArrayLevel : public LevelBase {
private:
    Array<node> m_nodes;
 
public:
    explicit ArrayLevel(unsigned int size) : m_nodes(size) { }
 
    explicit ArrayLevel(const Array<node>& nodes) : m_nodes(nodes) { }
 
    const node& operator[](int i) const override { return m_nodes[i]; }
 
    node& operator[](int i) override { return m_nodes[i]; }
 
    int size() const override { return m_nodes.size(); }
 
    int high() const override { return m_nodes.high(); }
};
 
 
class BlockOrder;
 
class OGDF_EXPORT Block {
    friend class BlockOrder;
 
private:
    int m_index = 0; 
 
    int m_upper = 0; 
 
    int m_lower = 0; 
 
    Array<node> m_nodes; 
 
    Array<int> m_NeighboursIncoming; 
 
    Array<int> m_InvertedIncoming; 
 
    Array<int> m_NeighboursOutgoing; 
 
    Array<int> m_InvertedOutgoing; 
 
    // exactly one of those below is non null!
    node m_Node = nullptr; 
    edge m_Edge = nullptr; 
 
    bool m_isEdgeBlock;
    bool m_isNodeBlock;
 
public:
    ~Block() { }
 
    bool isEdgeBlock() { return m_isEdgeBlock; }
 
    bool isVertexBlock() { return m_isNodeBlock; }
 
    explicit Block(node v);
 
    explicit Block(edge e);
};
 
class OGDF_EXPORT BlockOrder : public HierarchyLevelsBase {
private:
    enum class Direction { Plus, Minus };
 
    GraphCopy m_GC; 
 
    NodeArray<int> m_ranks; 
 
    // Block X -> pi(X)
    Array<int> m_storedPerm; 
    Array<int> m_currentPerm; 
    Array<int> m_bestPerm; 
 
    // int i -> Block X s.t. pi(X) = i
    Array<int> m_currentPermInv; 
 
    int m_storedCrossings; 
    int m_bestCrossings; 
 
#if 0
    unsigned int m_storedCrossings;
    unsigned int m_currentCrossings;
#endif
 
    Array<Block*> m_Blocks; 
    NodeArray<Block*> m_NodeBlocks; 
    EdgeArray<Block*> m_EdgeBlocks; 
 
    EdgeArray<bool> m_isActiveEdge; 
 
#if 0
    unsigned int m_blocksCount;
#endif
    int m_activeBlocksCount;
 
    Hierarchy& m_hierarchy; 
 
    void deconstruct(); 
 
    NodeArray<int> m_pos; 
 
    Array<ArrayLevel*> m_levels; 
 
    NodeArray<Array<node>> m_lowerAdjNodes; 
    NodeArray<Array<node>> m_upperAdjNodes; 
 
    NodeArray<int> m_nSet; 
 
public:
 
    const ArrayLevel& operator[](int i) const override { return *(m_levels[i]); }
 
    int pos(node v) const override { return m_pos[v]; }
 
    int size() const override { return m_levels.size(); }
 
    const Hierarchy& hierarchy() const override { return m_hierarchy; }
 
    const Array<node>& adjNodes(node v, TraversingDir dir) const override {
        if (dir == TraversingDir::upward) {
            return m_upperAdjNodes[v];
        } else {
            return m_lowerAdjNodes[v];
        }
    }
 
 
    // destruction
    ~BlockOrder() { deconstruct(); }
 
    int blocksCount() { return m_Blocks.size(); }
 
#if 0
    BlockOrder(const Graph &G, const NodeArray<int> &rank);
#endif
 
    explicit BlockOrder(Hierarchy& hierarchy, bool longEdgesOnly = true);
 
    void globalSifting(int rho = 1, int nRepeats = 10, int* pNumCrossings = nullptr);
 
private:
    void doInit(bool longEdgesOnly = true);
#if 0
    void doInit( bool longEdgesOnly = true, const NodeArray<int> &ranks);
#endif
 
    void sortAdjacencies();
 
    void updateAdjacencies(Block* blockOfA, Block* blockOfB, Direction d);
 
    int uswap(Block* blockOfA, Block* blockOfB, Direction d, int level);
 
    int siftingSwap(Block* blockOfA, Block* blockOfB);
 
    int siftingStep(Block* blockOfA);
 
    void buildLevels();
 
    void buildDummyNodesLists();
 
    void buildAdjNodes();
 
    void buildHierarchy() {
        buildDummyNodesLists();
        buildLevels();
        buildAdjNodes();
        m_storedCrossings = calculateCrossings();
    }
 
 
    int verticalSwap(Block* b, int level);
 
    int localCountCrossings(const Array<int>& levels);
 
    void verticalStep(Block* b);
 
    Array<int> m_nNodesOnLvls;
 
public:
    int m_verticalStepsBound;
 
    void gridSifting(int nRepeats = 10);
 
};
 
}