Hierarchy.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_HIERARCHY_H
#define OGDF_HIERARCHY_H


#include <ogdf/basic/EdgeArray.h>
#include <ogdf/layered/Level.h>
#include <ogdf/basic/GraphCopy.h>


namespace ogdf {



class OGDF_EXPORT Hierarchy {
public:
    friend class Level;     

    friend class LayerBasedUPRLayout;
    friend class HierarchyLayoutModule;

    enum TraversingDir { downward, upward };

private:
    Array<Level *> m_pLevel; 
    GraphCopy m_GC; 
    NodeArray<int> m_pos;  
    NodeArray<int> m_rank; 

    NodeArray<Array<node> > m_lowerAdjNodes;
    NodeArray<Array<node> > m_upperAdjNodes;

    NodeArray<int> m_nSet; 

    NodeArray<ListIterator<node> > m_lastOcc;

    TraversingDir m_direction; 

    bool getMarkedNodes(NodeArray<bool> &markedNodes, int r, List<node> &result, List<int> &positions) {
        result.clear();
        positions.clear();
        bool allDummies = true;
        
        if (r > high() || r < 0)
            return false;

        Level &lvl = *m_pLevel[r];
        
        for(int i = 0; i <= lvl.high(); i++) {
            node v = lvl[i];
            if (markedNodes[v]) {
                result.pushBack(v);
                positions.pushBack(pos(v));
                if (!isLongEdgeDummy(v))
                    allDummies = false;
            }
        }       
        positions.quicksort();
        return allDummies;
    }


public:
    Hierarchy() { }
    Hierarchy(const Graph &G, const NodeArray<int> &rank);

    // destruction
    ~Hierarchy();

    void createEmpty(const Graph &G);
    void initByNodes(const List<node> &nodes,
        EdgeArray<edge> &eCopy,
        const NodeArray<int> &rank);

    operator const GraphCopy &() const { return m_GC; }

    TraversingDir direction() const {
        return m_direction;
    }

    void direction (TraversingDir dir) {
        m_direction = dir;
    }

    int size() const { return m_pLevel.size(); }

    int high() const { return m_pLevel.high(); }

    int rank(node v) const { return m_rank[v]; }

    int pos(node v) const { return m_pos[v]; }

    const Array<node> &adjNodes(node v) {
        return (m_direction == downward) ? m_lowerAdjNodes[v] :
        m_upperAdjNodes[v];
    }
    
    const Array<node> &adjNodes(node v, TraversingDir dir) const {
        return (dir == downward) ? m_lowerAdjNodes[v] :
        m_upperAdjNodes[v];
    }

    const Level &adjLevel(int i) const {
        return (m_direction == downward) ? *m_pLevel[i-1] : *m_pLevel[i+1];
    
    }

    bool isLongEdgeDummy(node v) const {
        return (m_GC.isDummy(v) && v->outdeg() == 1);
    }

    const Level &operator[](int i) const { return *m_pLevel[i]; }

    Level &operator[](int i) { return *m_pLevel[i]; }

    
    int calculateCrossings(int i);
    int calculateCrossings();

    int calculateCrossingsPlaneSweep(int i);
    int calculateCrossingsPlaneSweep();

    int calculateCrossingsSimDraw(int i, const EdgeArray<unsigned int> *edgeSubGraph);
    int calculateCrossingsSimDraw(const EdgeArray<unsigned int> *edgeSubGraph);

    
    void storePos (NodeArray<int> &oldPos);
    void restorePos (const NodeArray<int> &newPos);

    void permute();

    void separateCCs(int numCC, NodeArray<int> &component);

    bool transpose(node v);

    void print(ostream &os);

    void buildAdjNodes(int i);
    void buildAdjNodes();

    void check();

private:
    void doInit(const NodeArray<int> &rank);

    int transposePart(const Array<node> &adjV, const Array<node> &adjW);    

    OGDF_MALLOC_NEW_DELETE
};


} // end namespace ogdf


#endif