SpringEmbedderKK.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/LayoutModule.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/tuples.h>
 
#include <limits>
 
namespace ogdf {
class GraphAttributes;
 
 
class OGDF_EXPORT SpringEmbedderKK : public LayoutModule {
public:
    using dpair = Tuple2<double, double>;
 
    SpringEmbedderKK()
        : m_tolerance(0.001)
        , m_ltolerance(0.0001)
        , m_computeMaxIt(true)
        , m_K(5.0)
        , m_prevEnergy(startVal)
        , m_prevLEnergy(startVal)
        , m_zeroLength(-1.0)
        , m_desLength(0.0)
        , m_distFactor(2.0)
        , m_useLayout(true)
        , m_gItBaseVal(50)
        , m_gItFactor(16) {
        m_maxLocalIt = m_maxGlobalIt = maxVal;
    }
 
    virtual void call(GraphAttributes& GA) override;
 
    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; }
#if 0
    //We could add some noise to the computation
 
    bool noise() const {
        return m_noise;
    }
 
    void noise(bool on) {
        m_noise = on;
    }
#endif
 
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;
        }
 
#if 0
        double diff = m_prevEnergy - maxdelta; // energy difference
        if (diff < 0.0) diff = -diff;
#   ifdef OGDF_DEBUG
        std::cout << "Finished(): maxdelta: " << maxdelta << " diff/prev: " << diff / m_prevEnergy << std::endl;
#   endif
#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;
    }
 
    bool finishedNode(double deltav) {
        if (m_prevLEnergy == startVal) {
            m_prevLEnergy = deltav;
            return deltav == 0.0; // m_ltolerance; locally stable
        }
#if 0
#   ifdef OGDF_DEBUG
        std::cout << "Local delta: " << deltav << "\n";
#   endif
#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;
    }
 
    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, bool simpleBFS);
 
    void mainStep(GraphAttributes& GA, NodeArray<dpair>& partialDer,
            NodeArray<NodeArray<double>>& oLength, NodeArray<NodeArray<double>>& sstrength);
 
    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; 
 
    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 = std::numeric_limits<double>::max());
};
 
#if 0
    //Things that potentially could be added
 
    double pageRatio() { return m_pageRatio; }
 
    void pageRatio(double x) { m_pageRatio = x; }
 
    Scaling scaling() const {
        return m_scaling;
    }
 
    void scaling(Scaling sc) {
        m_scaling = sc;
    }
 
    double scaleFunctionFactor() const {
        return m_scaleFactor;
    }
 
    void scaleFunctionFactor(double f) {
        m_scaleFactor = f;
    }
 
    void userBoundingBox(double xmin, double ymin, double xmax, double ymax) {
        m_bbXmin = xmin;
        m_bbYmin = ymin;
        m_bbXmax = xmax;
        m_bbYmax = ymax;
    }
#endif
}