SpringEmbedderKK.h

Go to the documentation of this file.

/*
 * $Revision: 2524 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-07-03 09:54:22 +0200 (Tue, 03 Jul 2012) $
 ***************************************************************/

#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_SPRING_EMBEDDER_KK_H
#define OGDF_SPRING_EMBEDDER_KK_H


#include <ogdf/module/LayoutModule.h>
#include <ogdf/basic/Array2D.h>
#include <ogdf/basic/tuples.h>


namespace ogdf {


    class OGDF_EXPORT GraphCopyAttributes;
    class OGDF_EXPORT GraphCopy;



class OGDF_EXPORT SpringEmbedderKK : public LayoutModule
{
public:
    typedef Tuple2<double, double> dpair;

    enum Scaling {
        scInput,           
        scUserBoundingBox, 
        scScaleFunction,    
        scScaleAdaptive    
    };

    SpringEmbedderKK() : m_tolerance(0.001), m_ltolerance(0.0001), m_computeMaxIt(true),
        m_K(5.0), m_desLength(0.0), m_distFactor(2.0), m_useLayout(true),
        m_gItBaseVal(50), m_gItFactor(16)
    {
        m_maxLocalIt = m_maxGlobalIt = maxVal;
    }

    ~SpringEmbedderKK() {}

    void call(GraphAttributes& GA);
    void call(GraphAttributes& GA, const EdgeArray<double>& eLength);

    void setStopTolerance(double s) {m_tolerance = s;}

    void setUseLayout(bool b) {m_useLayout = b;}
    bool useLayout() {return m_useLayout;}

    void setZeroLength(double d) {m_zeroLength = d;}
    double zeroLength() {return m_zeroLength;}

    void setDesLength(double d) {m_desLength = d;}


    int maxLocalIterations() const {
        return m_maxLocalIt;
    }
    void setGlobalIterationFactor(int i) {if (i>0) m_gItFactor = i;}
    int maxGlobalIterations() const {
        return m_maxGlobalIt;
    }
    void setMaxGlobalIterations(int i) {
        if (i>0)
            m_maxGlobalIt = i;
    }
    void setMaxLocalIterations(int i) {
        if (i>0)
            m_maxLocalIt = i;
    }
    void computeMaxIterations(bool b)
    {
        m_computeMaxIt = b;
    }
    //We could add some noise to the computation
    // Returns the current setting of nodes.
    //bool noise() const {
    //  return m_noise;
    //}
    // Sets the parameter noise to \a on.
    //void noise(bool on) {
    //  m_noise = on;
    //}


protected:
    void doCall(GraphAttributes& GA, const EdgeArray<double>& eLength, bool simpleBFS);
    bool finished(double maxdelta)
    {
        if (m_prevEnergy == startVal) //first step
        {
            m_prevEnergy = maxdelta;
            return false;
        }

        double diff = m_prevEnergy - maxdelta; //energy difference
        if (diff < 0.0) diff = -diff;
        //#ifdef OGDF_DEBUG
        //        cout << "Finished(): maxdelta: "<< maxdelta<<" diff/prev: "<<diff / m_prevEnergy<<"\n";
        //#endif
        //check if we want to stop
        bool done = (maxdelta < m_tolerance);// || (diff / m_prevEnergy) < m_tolerance);

        m_prevEnergy = maxdelta;   //save previous energy level
        m_prevLEnergy =  startVal; //reset energy level for local node decision

        return done;
    }//finished
    bool finishedNode(double deltav)
    {
        if (m_prevLEnergy == startVal)
        {
            m_prevLEnergy = deltav;
            return deltav == 0.0;//<m_ltolerance; //locally stable
        }
        //#ifdef OGDF_DEBUG
        //        cout << "Local delta: "<<deltav<<"\n";
        //#endif
        double diff = m_prevLEnergy - deltav;
        //check if we want to stop
        bool done = (deltav == 0.0 || (diff / m_prevLEnergy) < m_ltolerance);

        m_prevLEnergy = deltav; //save previous energy level

        return done;
    }//finishedNode
    void adaptLengths(const Graph& G,
        const GraphAttributes& GA,
        const EdgeArray<double>& eLengths,
        EdgeArray<double>& adaptedLengths);
    void shufflePositions(GraphAttributes& GA);
    dpair computeParDer(node m,
        node u,
        GraphAttributes& GA,
        NodeArray< NodeArray<double> >& ss,
        NodeArray< NodeArray<double> >& dist);
    dpair computeParDers(node v,
        GraphAttributes& GA,
        NodeArray< NodeArray<double> >& ss,
        NodeArray< NodeArray<double> >& dist);
    void initialize(GraphAttributes& GA,
        NodeArray<dpair>& partialDer,
        const EdgeArray<double>& eLength,
        NodeArray< NodeArray<double> >& oLength,
        NodeArray< NodeArray<double> >& sstrength,
        double & maxDist,
        bool simpleBFS);
    void mainStep(GraphAttributes& GA,
        NodeArray<dpair>& partialDer,
        NodeArray< NodeArray<double> >& oLength,
        NodeArray< NodeArray<double> >& sstrength,
        const double maxDist);
    void scale(GraphAttributes& GA);

private:
    double m_tolerance;  
    double m_ltolerance;  
    int m_maxGlobalIt;   
    int m_maxLocalIt;   
    bool m_computeMaxIt; 

    double m_K; 
    double m_prevEnergy; 
    double m_prevLEnergy;
    double m_zeroLength; 

    double m_desLength; 
    double m_distFactor; //introduces some distance for scaling in case BFS is used

    bool m_useLayout; 

    int m_gItBaseVal; 
    int m_gItFactor;  

    static const double startVal;
    static const double minVal;
    static const double desMinLength; 

    static const int maxVal = INT_MAX; 

    double allpairsspBFS(const Graph& G, NodeArray< NodeArray<double> >& distance);
    double allpairssp(const Graph& G, const EdgeArray<double>& eLengths,
        NodeArray< NodeArray<double> >& distance,   const double threshold = DBL_MAX);
};//SpringEmbedderKK

//Things that potentially could be added
//  //! Returns the page ratio.
//    double pageRatio() { return m_pageRatio; }
//
//  //! Sets the page ration to \a x.
//    void pageRatio(double x) { m_pageRatio = x; }
//
//  //! Returns the current scaling method.
//  Scaling scaling() const {
//      return m_scaling;
//  }
//
//  //! Sets the method for scaling the inital layout to \a sc.
//  void scaling(Scaling sc) {
//      m_scaling = sc;
//  }
//
//  //! Returns the current scale function factor.
//  double scaleFunctionFactor() const {
//      return m_scaleFactor;
//  }
//
//  //! Sets the scale function factor to \a f.
//  void scaleFunctionFactor(double f) {
//      m_scaleFactor = f;
//  }
//
//  //! Sets the user bounding box (used if scaling method is scUserBoundingBox).
//  void userBoundingBox(double xmin, double ymin, double xmax, double ymax) {
//      m_bbXmin = xmin;
//      m_bbYmin = ymin;
//      m_bbXmax = xmax;
//      m_bbYmax = ymax;
//  }


} // end namespace ogdf


#endif