StressMajorizationSimple.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_STRESS_MAJORIZATION_H
#define OGDF_STRESS_MAJORIZATION_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  StressMajorization : public LayoutModule
{
public:
    typedef Tuple2<double, double> dpair;
    
    enum Scaling {
        scInput,           
        scUserBoundingBox, 
        scScaleFunction,    
        scScaleAdaptive    
    };
    
    enum Constraints {
        cRadial = 0x0001,   //radial level depending on some centrality measure
        cUpward = 0x0002  //level depending on edge direction
    };
    
     StressMajorization() : m_tolerance(0.001),
                            m_ltolerance(0.0001),
                            m_baseRadius(50.0),
                            m_computeMaxIt(true),
                            m_K(5.0),
                            m_desLength(0.0),
                            m_distFactor(2.0),
                            m_useLayout(false),
                            m_radiiStyle(0),m_radiusFactor(1.1),
                            m_radial(false),
                            m_gItBaseVal(50),
                            m_gItFactor(16),
                            m_numSteps(300),
                            m_itFac(0.0),
                            m_constraints(cUpward),
                            m_upward(false)
                         {
                            m_maxLocalIt = m_maxGlobalIt = maxVal;
                         }
                         
    ~ StressMajorization() {}
    
    void call(GraphAttributes& GA); 
    void call(GraphAttributes& GA, const EdgeArray<double>& eLength); 
    
    void setIterations(int i) { if (i > 0) m_numSteps = i;}
    
    void setGraphSizeIterationFactor(double d) {if (DIsGreaterEqual(d, 0.0)) m_itFac = d; }
        
    void setStopTolerance(double s) {m_tolerance = s;}
    
    void setUseLayout(bool b) {m_useLayout = b;}
    bool useLayout() {return m_useLayout;}
    
    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;
    //}
    void radial(bool b) {m_radial = b;}
    void upward(bool b) {m_upward = b;}
    
protected:
    void doCall(GraphAttributes& GA, const EdgeArray<double>& eLength, bool simpleBFS);

        //radius on level \a level, (1 denotes first level)
        double radius(int level) 
        { 
            if (m_radiiStyle == 0) return m_baseRadius*level;
            else 
            {
                double rad = m_baseRadius;
                for (int i = 1; i < level; i++)
                {
                    rad*= m_radiusFactor;
                }
                rad+=m_baseRadius;
                return rad;
            }
        }
    
    //radius of a specific node, depending on its level
    double radius(node v)
    {
        return m_radii[v];
    }
    //computes radii for all nodes based on closeness and saves them in \a m_radii
    void computeRadii(const Graph& G, const NodeArray< NodeArray<double> >& distances, double diameter);

    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,
                    const EdgeArray<double>& eLength,
                    NodeArray< NodeArray<double> >& oLength,
                    NodeArray< NodeArray<double> >& weights,
                    double & maxDist,
                    bool simpleBFS);
    void mainStep(GraphAttributes& GA,
                NodeArray< NodeArray<double> >& oLength,
                NodeArray< NodeArray<double> >& weights,
                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_constraints; //constraints bit pattern
    
    bool m_radial; 
    
    bool m_upward;
    int m_radiiStyle; 



    NodeArray<double> m_radii; 
    double m_baseRadius; 
    int m_numSteps;     
    double m_itFac;     
    double m_radiusFactor; 
    int m_gItBaseVal; 
    int m_gItFactor;  
    
    
    double allpairsspBFS(const Graph& G, NodeArray< NodeArray<double> >& distance, 
        NodeArray< NodeArray<double> >& weights);
    double allpairssp(const Graph& G, const EdgeArray<double>& eLengths, 
        NodeArray< NodeArray<double> >& distance, NodeArray< NodeArray<double> >& weights,
        const double threshold = DBL_MAX);
        
    static const double startVal;
    static const double minVal;
    static const double desMinLength; 

    static const int maxVal = INT_MAX; 
    
};// StressMajorization

//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