FastHierarchyLayout.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_FAST_HIERARCHY_LAYOUT_H
#define OGDF_FAST_HIERARCHY_LAYOUT_H



#include <ogdf/module/HierarchyLayoutModule.h>
#include <ogdf/basic/List.h>


namespace ogdf {

#define ALLOW .00001
    

class withKey {

public:

  int element;
  double key;

  withKey &operator=(const withKey& wk) {
    element=wk.element;
    key=wk.key;
    return *this;
  }
  friend ostream& operator<<(ostream& out,const withKey& wk) {
    out<<wk.element<<"("<<wk.key<<")";
    return out;
  }
  friend istream& operator>>(istream& in,withKey& wk) {
    in>>wk.element>>wk.key;
    return in;
  }
};




class cmpWithKey {
public:
    static int compare(const withKey &wk1, const withKey &wk2) {
        if(wk1.key<wk2.key) return -1;
        if(wk1.key>wk2.key) return 1;
        return 0;
    }
    OGDF_AUGMENT_STATICCOMPARER(withKey)
};





class kList : public List<withKey> {

public:

    bool pop(int& e,double& k) {
        if(empty()) return 0;
        withKey wk=popFrontRet();
        e=wk.element;
        k=wk.key;
        return 1;
    }

    double peek() {
        return front().key;
    }

    void add(int e,double k) {
        withKey wK;
        wK.element=e;
        wK.key=k;
        pushBack(wK);
    }

    double median() const {
        int sz = size();
        if(!sz) 
            return 0;
        ListConstIterator<withKey> it = get(sz/2);
        double k = (*it).key;
        if (sz == 2*(int) (sz/2)) 
            k = (k + (*it.pred()).key) / 2;
        return k;
    }



    void reduce(kList& newList) {
        if(empty()) return;
        withKey oldWK,newWK;
        newWK = oldWK = popFrontRet();
        
        while(!empty()) {
            oldWK = popFrontRet();
            if ((oldWK.key) > (newWK.key) + ALLOW ||
                (oldWK.key) < (newWK.key) - ALLOW) {
                if(newWK.element) 
                    newList.pushBack(newWK);
                    newWK = oldWK;
            }
            else 
                newWK.element += oldWK.element;
        }
        if(newWK.element) 
            newList.pushBack(newWK);
    }

    withKey popFrontRet() {
        //CG: not referenced: int s = List<withKey>::size();
        withKey t = List<withKey>::front();
        List<withKey>::popFront();
        return t;
    }

};



class OGDF_EXPORT FastHierarchyLayout : public HierarchyLayoutModule
{
protected:

    void doCall(const Hierarchy& H,GraphCopyAttributes &AGC);

public:
    FastHierarchyLayout();

    FastHierarchyLayout(const FastHierarchyLayout &);

    // destructor
    virtual ~FastHierarchyLayout();


    FastHierarchyLayout &operator=(const FastHierarchyLayout &);


    double nodeDistance() const;

    void nodeDistance(double x);

    double layerDistance() const;

    void layerDistance(double x);

    bool fixedLayerDistance() const;

    void fixedLayerDistance(bool b);


private:

    int n;      
    int m;      
    int k;      
    int *layer; 
    int *first; 


    // nodes are numbered top down and from left to right.
    // Is called "internal numbering".
    // Nodes and Layeras are number 0 to n-1 and 0 to k-1, respectively.                 
    // For thechnical reasons we set first[k] to n. 

    List<int> *adj[2];

    List<int> **longEdge;

    double m_minNodeDist; 
    double m_minLayerDist;
    double *breadth;      
    double *height;       
    double *y;            
    double *x;            

    double *totalB;
    
    double *mDist; 

    bool m_fixedLayerDist; 
    bool *virt; 

    cmpWithKey _cmp; 

    void decrTo(double&,double);
    void incrTo(double&,double);
    bool sameLayer(int,int) const;
    bool isFirst(int) const;
    bool isLast(int) const;
    void sortLongEdges(int,int,double*,bool&,double&,int*,bool*);
    bool placeSingleNode(int,int,int,double&,int);
    void placeNodes(int,int,int,int,int);
    void moveLongEdge(int,int,bool*);
    void straightenEdge(int,bool*);
    void findPlacement();
};

} // end namespace ogdf


#endif