SpringEmbedderKK.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_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