SpringEmbedderFRExact.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_FR_EXACT_H
#define OGDF_SPRING_EMBEDDER_FR_EXACT_H


#include <ogdf/module/ForceLayoutModule.h>
#include <ogdf/basic/SList.h>


namespace ogdf {


    class OGDF_EXPORT GraphCopyAttributes;
    class OGDF_EXPORT GraphCopy;


class OGDF_EXPORT SpringEmbedderFRExact : public ForceLayoutModule
{
public:
    enum CoolingFunction { cfFactor, cfLogarithmic };

    SpringEmbedderFRExact();

    // destructor
    ~SpringEmbedderFRExact() { }


    void call(GraphAttributes &GA);


    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:
        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 l = 0.0;
        while(x > 0) {
            l++;
            x >>= 1;
        }
        return l/2;
    }

    void initialize(ArrayGraph &component);
    void mainStep(ArrayGraph &component);
    void mainStep_sse3(ArrayGraph &component);

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

    // cooling function
    void cool(double &tx, double &ty, int &cF);

    int    m_iterations; 
    bool   m_noise;      
    CoolingFunction m_coolingFunction; 


    //double m_tx;
    //double m_ty;

    double m_coolFactor_x;
    double m_coolFactor_y;

    double m_idealEdgeLength; 
    double m_minDistCC;       
    double m_pageRatio;       

    //int m_cF;
    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
};


} // end namespace ogdf


#endif