SpringEmbedderFRExact.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/basic/SList.h>
#include <ogdf/energybased/ForceLayoutModule.h>
 
namespace ogdf {
 
class OGDF_EXPORT SpringEmbedderFRExact : public ForceLayoutModule {
public:
    enum class CoolingFunction { Factor, Logarithmic };
 
    SpringEmbedderFRExact();
 
    virtual void call(GraphAttributes& GA) override;
 
    int iterations() const { return m_iterations; }
 
    void iterations(int i) {
        OGDF_ASSERT(i > 0);
        m_iterations = i;
    }
 
    bool noise() const { return m_noise; }
 
    void noise(bool on) { m_noise = on; }
 
    void nodeWeights(bool on) { m_useNodeWeight = on; }
 
    CoolingFunction coolingFunction() const { return m_coolingFunction; }
 
    void coolingFunction(CoolingFunction f) { m_coolingFunction = f; }
 
    double idealEdgeLength() const { return m_idealEdgeLength; }
 
    void idealEdgeLength(double len) { m_idealEdgeLength = len; }
 
    double minDistCC() const { return m_minDistCC; }
 
    void minDistCC(double x) { m_minDistCC = x; }
 
    double pageRatio() { return m_pageRatio; }
 
    void pageRatio(double x) { m_pageRatio = x; }
 
    void checkConvergence(bool b) { m_checkConvergence = b; }
 
    bool checkConvergence() { return m_checkConvergence; }
 
    void convTolerance(double tol) { m_convTolerance = tol; }
 
private:
    class ArrayGraph {
        int m_numNodes;
        int m_numEdges;
        int m_numCC;
 
        GraphAttributes* m_ga;
        node* m_orig;
        Array<SList<node>> m_nodesInCC;
        NodeArray<int> m_mapNode;
 
    public:
        explicit ArrayGraph(GraphAttributes& ga);
        ~ArrayGraph();
 
        void initCC(int i);
 
        int numberOfCCs() const { return m_numCC; }
 
        int numberOfNodes() const { return m_numNodes; }
 
        int numberOfEdges() const { return m_numEdges; }
 
        node original(int v) const { return m_orig[v]; }
 
        const SList<node>& nodesInCC(int i) const { return m_nodesInCC[i]; }
 
        int* m_src;
        int* m_tgt;
        double* m_x;
        double* m_y;
        double* m_nodeWeight;
        //this should be part of a multilevel layout interface class later on
        bool m_useNodeWeight; //should given nodeweights be used or all set to 1.0?
    };
 
    double log2(double x) { return log(x) / log(2.0); }
 
    double mylog2(int x) {
        double result = 0.0;
        while (x > 0) {
            result++;
            x >>= 1;
        }
        return result / 2;
    }
 
    void initialize(ArrayGraph& component);
    void mainStep(ArrayGraph& component);
    void mainStep_sse3(ArrayGraph& component);
 
#if 0
    // Fruchterman, Reingold
    double f_att(double d) { return d*d / m_idealEdgeLength; }
    double f_rep(double d) { return m_idealEdgeLength*m_idealEdgeLength / d; }
 
    // Eades
    double f_att(double d) { return 5.0 * d * log2(d/m_idealEdgeLength); }
    double f_rep(double d) { return 20.0 / d; }
#endif
 
    // cooling function
    void cool(double& tx, double& ty, int& cF);
 
    int m_iterations; 
    bool m_noise; 
    CoolingFunction m_coolingFunction; 
 
#if 0
    double m_tx;
    double m_ty;
#endif
 
    double m_coolFactor_x;
    double m_coolFactor_y;
 
    double m_idealEdgeLength; 
    double m_minDistCC; 
    double m_pageRatio; 
 
#if 0
    int m_cF;
#endif
    double m_txNull;
    double m_tyNull;
    //see above at ArrayGraph
    bool m_useNodeWeight;
    bool m_checkConvergence; //<! If set to true, computation is stopped if movement falls below threshold
    double m_convTolerance; //<! Fraction of ideal edge length below which convergence is achieved
};
 
}