SpringEmbedderBase.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/LayoutModule.h>
#include <ogdf/basic/LayoutStandards.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/System.h>
#include <ogdf/basic/geometry.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/energybased/SpringForceModel.h>
#include <ogdf/packing/TileToRowsCCPacker.h>
 
#include <cmath>
 
namespace ogdf {
namespace spring_embedder {
 
class SpringEmbedderBase : public LayoutModule {
public:
    enum class Scaling {
        input, 
        userBoundingBox, 
        scaleFunction, 
        useIdealEdgeLength 
    };
 
    SpringEmbedderBase() {
        // default parameters
        m_iterations = 400;
        m_iterationsImprove = 200;
        m_coolDownFactor = 0.999;
        m_forceLimitStep = 0.25;
 
        m_boundingBox = DRect(0, 0, 250, 250);
        m_noise = true;
 
        m_forceModel = SpringForceModel::FruchtermanReingold;
        m_forceModelImprove = SpringForceModel::FruchtermanReingoldModRep;
 
        m_avgConvergenceFactor = 0.1;
        m_maxConvergenceFactor = 0.2;
 
        m_scaling = Scaling::scaleFunction;
        m_scaleFactor = 4.0;
 
        m_userBoundingBox = DRect(0, 0, 100, 100);
 
        m_minDistCC = LayoutStandards::defaultCCSeparation();
        m_pageRatio = 1.0;
 
        m_maxThreads = System::numberOfProcessors();
 
        double def_nw = LayoutStandards::defaultNodeWidth();
        double def_nh = LayoutStandards::defaultNodeHeight();
        m_idealEdgeLength =
                LayoutStandards::defaultNodeSeparation() + sqrt(def_nw * def_nw + def_nh * def_nh);
    }
 
    virtual void call(GraphAttributes& GA) override {
        const Graph& G = GA.constGraph();
        if (G.empty()) {
            return;
        }
 
        // all edges straight-line
        GA.clearAllBends();
 
        GraphCopy GC;
        GC.setOriginalGraph(G);
 
        // compute connected component of G
        NodeArray<int> component(G);
        int numCC = connectedComponents(G, component);
 
        // intialize the array of lists of nodes contained in a CC
        Array<List<node>> nodesInCC(numCC);
 
        for (node v : G.nodes) {
            nodesInCC[component[v]].pushBack(v);
        }
 
        NodeArray<node> nodeCopy(G);
        EdgeArray<edge> auxCopy(G);
        Array<DPoint> boundingBox(numCC);
 
        for (int i = 0; i < numCC; ++i) {
            nodeCopy.init(G);
            auxCopy.init(G);
            GC.clear();
            GC.insert(nodesInCC[i].begin(), nodesInCC[i].end(), filter_any_edge, nodeCopy, auxCopy);
            makeSimpleUndirected(GC);
 
            const int n = GC.numberOfNodes();
 
            // special case: just one node
            if (n == 1) {
                node vOrig = GC.original(GC.firstNode());
                GA.x(vOrig) = GA.y(vOrig) = 0;
                boundingBox[i] = DPoint(0, 0);
                continue;
            }
 
            callMaster(GC, GA, boundingBox[i]);
            //std::cout << "avg. force: " << master.avgDisplacement() << std::endl;
            //std::cout << "max. force: " << master.maxDisplacement() << std::endl;
        }
 
        Array<DPoint> offset(numCC);
        TileToRowsCCPacker packer;
        packer.call(boundingBox, offset, m_pageRatio);
 
        // The arrangement is given by offset to the origin of the coordinate
        // system. We still have to shift each node and edge by the offset
        // of its connected component.
 
        for (int i = 0; i < numCC; ++i) {
            const List<node>& nodes = nodesInCC[i];
 
            const double dx = offset[i].m_x;
            const double dy = offset[i].m_y;
 
            // iterate over all nodes in ith CC
            ListConstIterator<node> it;
            for (node v : nodes) {
                GA.x(v) += dx;
                GA.y(v) += dy;
            }
        }
    }
 
    SpringForceModel forceModel() const { return m_forceModel; }
 
    void forceModel(SpringForceModel fm) { m_forceModel = fm; }
 
    SpringForceModel forceModelImprove() const { return m_forceModelImprove; }
 
    void forceModelImprove(SpringForceModel fm) { m_forceModelImprove = fm; }
 
 
    double avgConvergenceFactor() const { return m_avgConvergenceFactor; }
 
    void avgConvergenceFactor(double f) {
        if (f >= 0) {
            m_avgConvergenceFactor = f;
        }
    }
 
 
    double maxConvergenceFactor() const { return m_maxConvergenceFactor; }
 
    void maxConvergenceFactor(double f) {
        if (f >= 0) {
            m_maxConvergenceFactor = f;
        }
    }
 
 
    int iterations() const { return m_iterations; }
 
    void iterations(int i) {
        if (i >= 0) {
            m_iterations = i;
        }
    }
 
    int iterationsImprove() const { return m_iterationsImprove; }
 
    void iterationsImprove(int i) {
        if (i >= 0) {
            m_iterationsImprove = i;
        }
    }
 
    double coolDownFactor() const { return m_coolDownFactor; }
 
    double forceLimitStep() const { return m_forceLimitStep; }
 
    double idealEdgeLength() const { return m_idealEdgeLength; }
 
 
    void idealEdgeLength(double len) { m_idealEdgeLength = len; }
 
    bool noise() const { return m_noise; }
 
    void noise(bool on) { m_noise = on; }
 
    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; }
 
    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_userBoundingBox = DRect(xmin, ymin, xmax, ymax);
    }
 
    DRect userBoundingBox() const { return m_userBoundingBox; }
 
    unsigned int maxThreads() const { return m_maxThreads; }
 
    void maxThreads(unsigned int n) { m_maxThreads = n; }
 
protected:
    virtual void callMaster(const GraphCopy& copy, GraphAttributes& attr, DPoint& box) = 0;
 
    int m_iterations; 
    int m_iterationsImprove; 
    double m_idealEdgeLength; 
    double m_coolDownFactor;
    double m_forceLimitStep;
 
    DRect m_boundingBox;
 
    SpringForceModel m_forceModel; 
    SpringForceModel m_forceModelImprove; 
    bool m_noise; 
 
    Scaling m_scaling; 
    double m_scaleFactor; 
 
    DRect m_userBoundingBox;
 
    double m_minDistCC; 
    double m_pageRatio; 
 
    double m_avgConvergenceFactor; 
    double m_maxConvergenceFactor; 
 
    unsigned int m_maxThreads; 
};
 
}
}