FMMMLayout.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/geometry.h>
#include <ogdf/energybased/fmmm/EdgeAttributes.h>
#include <ogdf/energybased/fmmm/FMMMOptions.h>
#include <ogdf/energybased/fmmm/FruchtermanReingold.h>
#include <ogdf/energybased/fmmm/NewMultipoleMethod.h>
#include <ogdf/energybased/fmmm/NodeAttributes.h>
#include <ogdf/energybased/fmmm/maar_packing/Rectangle.h>
 
#include <algorithm>
 
namespace ogdf {
class ClusterGraphAttributes;
class GraphAttributes;
template<class E>
class List;
 
class OGDF_EXPORT FMMMLayout : public LayoutModule {
    using Rectangle = energybased::fmmm::Rectangle;
    using NodeAttributes = energybased::fmmm::NodeAttributes;
    using EdgeAttributes = energybased::fmmm::EdgeAttributes;
 
public:
    FMMMLayout();
 
    // destructor
    virtual ~FMMMLayout() { }
 
    virtual void call(GraphAttributes& GA) override;
 
    void call(ClusterGraphAttributes& GA);
 
 
    void call(GraphAttributes& GA, //graph and layout
            const EdgeArray<double>& edgeLength); //factor for desired edge lengths
 
 
    void call(GraphAttributes& GA, char* ps_file);
 
 
    void call(GraphAttributes& GA, //graph and layout
            const EdgeArray<double>& edgeLength, //factor for desired edge lengths
            char* ps_file);
 
    double getCpuTime() { return time_total; }
 
 
    void resetOptions();
 
 
    bool useHighLevelOptions() const { return m_useHighLevelOptions; }
 
    void useHighLevelOptions(bool uho) { m_useHighLevelOptions = uho; }
 
    void setSingleLevel(bool b) { m_singleLevel = b; }
 
 
    FMMMOptions::PageFormatType pageFormat() const { return m_pageFormat; }
 
    void pageFormat(FMMMOptions::PageFormatType t) { m_pageFormat = t; }
 
    double unitEdgeLength() const { return m_unitEdgeLength; }
 
    void unitEdgeLength(double x) { m_unitEdgeLength = ((x > 0.0) ? x : 1); }
 
 
    bool newInitialPlacement() const { return m_newInitialPlacement; }
 
    void newInitialPlacement(bool nip) { m_newInitialPlacement = nip; }
 
 
    FMMMOptions::QualityVsSpeed qualityVersusSpeed() const { return m_qualityVersusSpeed; }
 
    void qualityVersusSpeed(FMMMOptions::QualityVsSpeed qvs) { m_qualityVersusSpeed = qvs; }
 
    void randSeed(int p) { m_randSeed = ((0 <= p) ? p : 1); }
 
    int randSeed() const { return m_randSeed; }
 
    FMMMOptions::EdgeLengthMeasurement edgeLengthMeasurement() const {
        return m_edgeLengthMeasurement;
    }
 
    void edgeLengthMeasurement(FMMMOptions::EdgeLengthMeasurement elm) {
        m_edgeLengthMeasurement = elm;
    }
 
    FMMMOptions::AllowedPositions allowedPositions() const { return m_allowedPositions; }
 
    void allowedPositions(FMMMOptions::AllowedPositions ap) { m_allowedPositions = ap; }
 
 
    int maxIntPosExponent() const { return m_maxIntPosExponent; }
 
    void maxIntPosExponent(int e) { m_maxIntPosExponent = (((e >= 31) && (e <= 51)) ? e : 31); }
 
 
    double pageRatio() const { return m_pageRatio; }
 
    void pageRatio(double r) { m_pageRatio = ((r > 0) ? r : 1); }
 
 
    int stepsForRotatingComponents() const { return m_stepsForRotatingComponents; }
 
    void stepsForRotatingComponents(int n) { m_stepsForRotatingComponents = ((0 <= n) ? n : 0); }
 
    FMMMOptions::TipOver tipOverCCs() const { return m_tipOverCCs; }
 
    void tipOverCCs(FMMMOptions::TipOver to) { m_tipOverCCs = to; }
 
    double minDistCC() const { return m_minDistCC; }
 
    void minDistCC(double x) { m_minDistCC = ((x > 0) ? x : 1); }
 
    FMMMOptions::PreSort presortCCs() const { return m_presortCCs; }
 
    void presortCCs(FMMMOptions::PreSort ps) { m_presortCCs = ps; }
 
 
    int minGraphSize() const { return m_minGraphSize; }
 
    void minGraphSize(int n) { m_minGraphSize = ((n >= 2) ? n : 2); }
 
    FMMMOptions::GalaxyChoice galaxyChoice() const { return m_galaxyChoice; }
 
    void galaxyChoice(FMMMOptions::GalaxyChoice gc) { m_galaxyChoice = gc; }
 
 
    int randomTries() const { return m_randomTries; }
 
    void randomTries(int n) { m_randomTries = ((n >= 1) ? n : 1); }
 
    FMMMOptions::MaxIterChange maxIterChange() const { return m_maxIterChange; }
 
    void maxIterChange(FMMMOptions::MaxIterChange mic) { m_maxIterChange = mic; }
 
 
    int maxIterFactor() const { return m_maxIterFactor; }
 
    void maxIterFactor(int f) { m_maxIterFactor = ((f >= 1) ? f : 1); }
 
    FMMMOptions::InitialPlacementMult initialPlacementMult() const {
        return m_initialPlacementMult;
    }
 
    void initialPlacementMult(FMMMOptions::InitialPlacementMult ipm) {
        m_initialPlacementMult = ipm;
    }
 
    FMMMOptions::ForceModel forceModel() const { return m_forceModel; }
 
    void forceModel(FMMMOptions::ForceModel fm) { m_forceModel = fm; }
 
    double springStrength() const { return m_springStrength; }
 
    void springStrength(double x) { m_springStrength = ((x > 0) ? x : 1); }
 
    double repForcesStrength() const { return m_repForcesStrength; }
 
    void repForcesStrength(double x) { m_repForcesStrength = ((x > 0) ? x : 1); }
 
    FMMMOptions::RepulsiveForcesMethod repulsiveForcesCalculation() const {
        return m_repulsiveForcesCalculation;
    }
 
    void repulsiveForcesCalculation(FMMMOptions::RepulsiveForcesMethod rfc) {
        m_repulsiveForcesCalculation = rfc;
    }
 
    FMMMOptions::StopCriterion stopCriterion() const { return m_stopCriterion; }
 
    void stopCriterion(FMMMOptions::StopCriterion rsc) { m_stopCriterion = rsc; }
 
 
    double threshold() const { return m_threshold; }
 
    void threshold(double x) { m_threshold = ((x > 0) ? x : 0.1); }
 
    int fixedIterations() const { return m_fixedIterations; }
 
    void fixedIterations(int n) { m_fixedIterations = ((n >= 1) ? n : 1); }
 
    double forceScalingFactor() const { return m_forceScalingFactor; }
 
    void forceScalingFactor(double f) { m_forceScalingFactor = ((f > 0) ? f : 1); }
 
 
    bool coolTemperature() const { return m_coolTemperature; }
 
    void coolTemperature(bool b) { m_coolTemperature = b; }
 
 
    double coolValue() const { return m_coolValue; }
 
    void coolValue(double x) { m_coolValue = (((x > 0) && (x <= 1)) ? x : 0.99); }
 
    FMMMOptions::InitialPlacementForces initialPlacementForces() const {
        return m_initialPlacementForces;
    }
 
    void initialPlacementForces(FMMMOptions::InitialPlacementForces ipf) {
        m_initialPlacementForces = ipf;
    }
 
 
    bool resizeDrawing() const { return m_resizeDrawing; }
 
    void resizeDrawing(bool b) { m_resizeDrawing = b; }
 
 
    double resizingScalar() const { return m_resizingScalar; }
 
    void resizingScalar(double s) { m_resizingScalar = ((s > 0) ? s : 1); }
 
    int fineTuningIterations() const { return m_fineTuningIterations; }
 
    void fineTuningIterations(int n) { m_fineTuningIterations = ((n >= 0) ? n : 0); }
 
 
    double fineTuneScalar() const { return m_fineTuneScalar; }
 
    void fineTuneScalar(double s) { m_fineTuneScalar = ((s >= 0) ? s : 1); }
 
 
    bool adjustPostRepStrengthDynamically() const { return m_adjustPostRepStrengthDynamically; }
 
    void adjustPostRepStrengthDynamically(bool b) { m_adjustPostRepStrengthDynamically = b; }
 
    double postSpringStrength() const { return m_postSpringStrength; }
 
    void postSpringStrength(double x) { m_postSpringStrength = ((x > 0) ? x : 1); }
 
    double postStrengthOfRepForces() const { return m_postStrengthOfRepForces; }
 
    void postStrengthOfRepForces(double x) { m_postStrengthOfRepForces = ((x > 0) ? x : 1); }
 
 
    int frGridQuotient() const { return m_frGridQuotient; }
 
    void frGridQuotient(int p) { m_frGridQuotient = ((0 <= p) ? p : 2); }
 
    FMMMOptions::ReducedTreeConstruction nmTreeConstruction() const { return m_NMTreeConstruction; }
 
    void nmTreeConstruction(FMMMOptions::ReducedTreeConstruction rtc) {
        m_NMTreeConstruction = rtc;
    }
 
    FMMMOptions::SmallestCellFinding nmSmallCell() const { return m_NMSmallCell; }
 
    void nmSmallCell(FMMMOptions::SmallestCellFinding scf) { m_NMSmallCell = scf; }
 
 
    int nmParticlesInLeaves() const { return m_NMParticlesInLeaves; }
 
    void nmParticlesInLeaves(int n) { m_NMParticlesInLeaves = ((n >= 1) ? n : 1); }
 
    int nmPrecision() const { return m_NMPrecision; }
 
    void nmPrecision(int p) { m_NMPrecision = ((p >= 1) ? p : 1); }
 
 
private:
    //high level options
    bool m_useHighLevelOptions; 
    FMMMOptions::PageFormatType m_pageFormat; 
    double m_unitEdgeLength; 
    bool m_newInitialPlacement; 
    FMMMOptions::QualityVsSpeed m_qualityVersusSpeed; 
 
    //low level options
    //general options
    int m_randSeed; 
    FMMMOptions::EdgeLengthMeasurement m_edgeLengthMeasurement; 
    FMMMOptions::AllowedPositions m_allowedPositions; 
    int m_maxIntPosExponent; 
 
    //options for divide et impera step
    double m_pageRatio; 
    int m_stepsForRotatingComponents; 
    FMMMOptions::TipOver m_tipOverCCs; 
    double m_minDistCC; 
    FMMMOptions::PreSort m_presortCCs; 
 
    //options for multilevel step
    bool m_singleLevel; 
    int m_minGraphSize; 
    FMMMOptions::GalaxyChoice m_galaxyChoice; 
    int m_randomTries; 
 
    FMMMOptions::MaxIterChange m_maxIterChange;
 
    int m_maxIterFactor; 
    FMMMOptions::InitialPlacementMult m_initialPlacementMult; 
 
    //options for force calculation step
    FMMMOptions::ForceModel m_forceModel; 
    double m_springStrength; 
    double m_repForcesStrength; 
    FMMMOptions::RepulsiveForcesMethod m_repulsiveForcesCalculation; 
    FMMMOptions::StopCriterion m_stopCriterion; 
    double m_threshold; 
    int m_fixedIterations; 
    double m_forceScalingFactor; 
    bool m_coolTemperature; 
    double m_coolValue; 
    FMMMOptions::InitialPlacementForces m_initialPlacementForces; 
 
    //options for postprocessing step
    bool m_resizeDrawing; 
    double m_resizingScalar; 
    int m_fineTuningIterations; 
    double m_fineTuneScalar; 
    bool m_adjustPostRepStrengthDynamically; 
    double m_postSpringStrength; 
    double m_postStrengthOfRepForces; 
 
    //options for repulsive force approximation methods
    int m_frGridQuotient; 
    FMMMOptions::ReducedTreeConstruction
            m_NMTreeConstruction; 
    FMMMOptions::SmallestCellFinding m_NMSmallCell; 
    int m_NMParticlesInLeaves; 
    int m_NMPrecision; 
 
    //other variables
    double max_integer_position; 
    double cool_factor; 
    double average_ideal_edgelength; 
    double boxlength; 
    int number_of_components; 
    DPoint down_left_corner; 
    NodeArray<double> radius; 
    double time_total; 
 
    energybased::fmmm::FruchtermanReingold FR; 
    energybased::fmmm::NewMultipoleMethod NM; 
 
 
    void call_DIVIDE_ET_IMPERA_step(Graph& G, NodeArray<NodeAttributes>& A,
            EdgeArray<EdgeAttributes>& E);
 
    void call_MULTILEVEL_step_for_subGraph(Graph& G, NodeArray<NodeAttributes>& A,
            EdgeArray<EdgeAttributes>& E);
 
    bool running(int iter, int max_mult_iter, double actforcevectorlength);
 
 
    void call_FORCE_CALCULATION_step(Graph& G, NodeArray<NodeAttributes>& A,
            EdgeArray<EdgeAttributes>& E, int act_level, int max_level);
 
    void call_POSTPROCESSING_step(Graph& G, NodeArray<NodeAttributes>& A,
            EdgeArray<EdgeAttributes>& E, NodeArray<DPoint>& F, NodeArray<DPoint>& F_attr,
            NodeArray<DPoint>& F_rep, NodeArray<DPoint>& last_node_movement);
 
 
    void update_low_level_options_due_to_high_level_options_settings();
 
    void import_NodeAttributes(const Graph& G, GraphAttributes& GA, NodeArray<NodeAttributes>& A);
 
    void import_EdgeAttributes(const Graph& G, const EdgeArray<double>& edgeLength,
            EdgeArray<EdgeAttributes>& E);
 
    void init_ind_ideal_edgelength(const Graph& G, NodeArray<NodeAttributes>& A,
            EdgeArray<EdgeAttributes>& E);
 
    void set_radii(const Graph& G, NodeArray<NodeAttributes>& A);
 
    void export_NodeAttributes(Graph& G_reduced, NodeArray<NodeAttributes>& A_reduced,
            GraphAttributes& GA);
 
 
    void make_simple_loopfree(const Graph& G, NodeArray<NodeAttributes>& A,
            EdgeArray<EdgeAttributes> E, Graph& G_reduced, NodeArray<NodeAttributes>& A_reduced,
            EdgeArray<EdgeAttributes>& E_reduced);
 
 
    void delete_parallel_edges(const Graph& G, EdgeArray<EdgeAttributes>& E, Graph& G_reduced,
            List<edge>& S, EdgeArray<double>& new_edgelength);
 
 
    void update_edgelength(List<edge>& S, EdgeArray<double>& new_edgelength,
            EdgeArray<EdgeAttributes>& E_reduced);
 
 
    double get_post_rep_force_strength(int n) { return min(0.2, 400.0 / double(n)); }
 
    void adjust_positions(const Graph& G, NodeArray<NodeAttributes>& A);
 
    void create_postscript_drawing(GraphAttributes& GA, char* ps_file);
 
 
 
    void create_maximum_connected_subGraphs(Graph& G, NodeArray<NodeAttributes>& A,
            EdgeArray<EdgeAttributes>& E, Graph G_sub[], NodeArray<NodeAttributes> A_sub[],
            EdgeArray<EdgeAttributes> E_sub[], NodeArray<int>& component);
 
 
    void pack_subGraph_drawings(NodeArray<NodeAttributes>& A, Graph G_sub[],
            NodeArray<NodeAttributes> A_sub[]);
 
    void calculate_bounding_rectangles_of_components(List<Rectangle>& R, Graph G_sub[],
            NodeArray<NodeAttributes> A_sub[]);
 
    Rectangle calculate_bounding_rectangle(Graph& G, NodeArray<NodeAttributes>& A,
            int componenet_index);
 
    void rotate_components_and_calculate_bounding_rectangles(List<Rectangle>& R, Graph G_sub[],
            NodeArray<NodeAttributes> A_sub[]);
 
    double calculate_area(double width, double height, int comp_nr) {
        double scaling = 1.0;
        if (comp_nr == 1) { //calculate aspect ratio area of the rectangle
            OGDF_ASSERT(height != 0.0);
            double ratio = width / height;
            if (ratio < pageRatio()) { //scale width
                OGDF_ASSERT(ratio != 0.0);
                scaling = pageRatio() / ratio;
            } else { //scale height
                OGDF_ASSERT(pageRatio() != 0.0);
                scaling = ratio / pageRatio();
            }
        }
        return width * height * scaling;
    }
 
    void export_node_positions(NodeArray<NodeAttributes>& A, List<Rectangle>& R, Graph G_sub[],
            NodeArray<NodeAttributes> A_sub[]);
 
    void delete_all_subGraphs(Graph G_sub[], NodeArray<NodeAttributes> A_sub[],
            EdgeArray<EdgeAttributes> E_sub[]) {
        delete[] G_sub;
        delete[] A_sub;
        delete[] E_sub;
    }
 
 
    int get_max_mult_iter(int act_level, int max_level, int node_nr);
 
 
    void calculate_forces(Graph& G, NodeArray<NodeAttributes>& A, EdgeArray<EdgeAttributes>& E,
            NodeArray<DPoint>& F, NodeArray<DPoint>& F_attr, NodeArray<DPoint>& F_rep,
            NodeArray<DPoint>& last_node_movement, int iter, int fine_tuning_step);
 
    void init_boxlength_and_cornercoordinate(Graph& G, NodeArray<NodeAttributes>& A);
 
    void create_initial_placement(Graph& G, NodeArray<NodeAttributes>& A);
 
    void create_initial_placement_uniform_grid(const Graph& G, NodeArray<NodeAttributes>& A);
 
    void create_initial_placement_random(const Graph& G, NodeArray<NodeAttributes>& A);
 
    void init_F(Graph& G, NodeArray<DPoint>& F);
 
 
    void make_initialisations_for_rep_calc_classes(
        Graph& G/*,
        NodeArray<NodeAttributes> &A,
        NodeArray<DPoint>& F_rep*/);
 
    void calculate_repulsive_forces(Graph& G, NodeArray<NodeAttributes>& A, NodeArray<DPoint>& F_rep) {
        switch (repulsiveForcesCalculation()) {
        case FMMMOptions::RepulsiveForcesMethod::Exact:
            FR.calculate_exact_repulsive_forces(G, A, F_rep);
            break;
        case FMMMOptions::RepulsiveForcesMethod::GridApproximation:
            FR.calculate_approx_repulsive_forces(G, A, F_rep);
            break;
        case FMMMOptions::RepulsiveForcesMethod::NMM:
            NM.calculate_repulsive_forces(G, A, F_rep);
            break;
        }
    }
 
    void deallocate_memory_for_rep_calc_classes() {
        if (repulsiveForcesCalculation() == FMMMOptions::RepulsiveForcesMethod::NMM) {
            NM.deallocate_memory();
        }
    }
 
    void calculate_attractive_forces(Graph& G, NodeArray<NodeAttributes>& A,
            EdgeArray<EdgeAttributes>& E, NodeArray<DPoint>& F_attr);
 
    double f_attr_scalar(double d, double ind_ideal_edge_length);
 
    void add_attr_rep_forces(Graph& G, NodeArray<DPoint>& F_attr, NodeArray<DPoint>& F_rep,
            NodeArray<DPoint>& F, int iter, int fine_tuning_step);
 
    void move_nodes(Graph& G, NodeArray<NodeAttributes>& A, NodeArray<DPoint>& F);
 
 
    void update_boxlength_and_cornercoordinate(Graph& G, NodeArray<NodeAttributes>& A);
 
    double max_radius(int iter) { return (iter == 1) ? boxlength / 1000 : boxlength / 5; }
 
    void set_average_ideal_edgelength(Graph& G, EdgeArray<EdgeAttributes>& E);
 
    double get_average_forcevector_length(Graph& G, NodeArray<DPoint>& F);
 
    void prevent_oscillations(Graph& G, NodeArray<DPoint>& F, NodeArray<DPoint>& last_node_movement,
            int iter);
 
    void init_last_node_movement(Graph& G, NodeArray<DPoint>& F,
            NodeArray<DPoint>& last_node_movement);
 
    void adapt_drawing_to_ideal_average_edgelength(Graph& G, NodeArray<NodeAttributes>& A,
            EdgeArray<EdgeAttributes>& E);
 
    void restrict_force_to_comp_box(DPoint& force) {
        double x_min = down_left_corner.m_x;
        double x_max = down_left_corner.m_x + boxlength;
        double y_min = down_left_corner.m_y;
        double y_max = down_left_corner.m_y + boxlength;
        if (force.m_x < x_min) {
            force.m_x = x_min;
        } else if (force.m_x > x_max) {
            force.m_x = x_max;
        }
        if (force.m_y < y_min) {
            force.m_y = y_min;
        } else if (force.m_y > y_max) {
            force.m_y = y_max;
        }
    }
 
 
    void init_time() { time_total = 0; }
 
};
 
}