FMMMLayout.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_FMMMLAYOUT_H
#define OGDF_FMMMLAYOUT_H

#include <ogdf/basic/Graph.h>
#include <ogdf/cluster/ClusterGraphAttributes.h>
#include <ogdf/module/LayoutModule.h>
#include <ogdf/basic/geometry.h>
#include <ogdf/internal/energybased/FruchtermanReingold.h>
#include <ogdf/internal/energybased/NMM.h>

  
namespace ogdf {

    class OGDF_EXPORT Rectangle;

class OGDF_EXPORT FMMMLayout : public LayoutModule
{
public:
    enum PageFormatType {
        pfPortrait,  
        pfLandscape, 
        pfSquare     
    };

    enum QualityVsSpeed { 
        qvsGorgeousAndEfficient,  
        qvsBeautifulAndFast,      
        qvsNiceAndIncredibleSpeed 
    };

    enum EdgeLengthMeasurement { 
        elmMidpoint,      
        elmBoundingCircle 
    };

    enum AllowedPositions { 
        apAll, 
        apInteger, 
        apExponent 
    };

    enum TipOver { 
        toNone, 
        toNoGrowingRow, 
        toAlways 
    };

    enum PreSort { 
        psNone, 
        psDecreasingHeight, 
        psDecreasingWidth   
    };

    enum GalaxyChoice { 
        gcUniformProb, 
        gcNonUniformProbLowerMass, 
        gcNonUniformProbHigherMass 
    };

    enum MaxIterChange { 
        micConstant, 
        micLinearlyDecreasing, 
        micRapidlyDecreasing 
    };

    enum InitialPlacementMult { 
        ipmSimple, 
        ipmAdvanced 
    };

    enum ForceModel { 
        fmFruchtermanReingold, 
        fmEades,               
        fmNew                  
    };

    enum RepulsiveForcesMethod { 
        rfcExact,             
        rfcGridApproximation, 
        rfcNMM                
    };

    enum StopCriterion { 
        scFixedIterations,           
        scThreshold,                 
        scFixedIterationsOrThreshold 
    };

    enum InitialPlacementForces { 
        ipfUniformGrid,      
        ipfRandomTime,       
        ipfRandomRandIterNr, 
        ipfKeepPositions     
    };

    enum ReducedTreeConstruction { 
        rtcPathByPath,      
        rtcSubtreeBySubtree 
    };

    enum SmallestCellFinding { 
        scfIteratively, 
        scfAluru        
    };
  

    FMMMLayout();
 
    // destructor
    virtual ~FMMMLayout() { }
 
 

    void call(GraphAttributes &GA);
 
        void call(ClusterGraphAttributes &GA);


    void call(GraphAttributes &GA,   //graph and layout
        const EdgeArray<double> &edgeLength); //factor for desired edge lengths 


    void call(GraphAttributes &AG, char* ps_file);
 

    void call(GraphAttributes &AG,   //graph and layout
        const EdgeArray<double> &edgeLength, //factor for desired edge lengths
        char* ps_file); 


    double getCpuTime();




    bool useHighLevelOptions() const { return m_useHighLevelOptions; }

    void useHighLevelOptions(bool uho) { m_useHighLevelOptions = uho; } 


    PageFormatType pageFormat() const { return m_pageFormat; }

    void pageFormat(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; }
  

    QualityVsSpeed qualityVersusSpeed() const { return m_qualityVersusSpeed; }

    void qualityVersusSpeed(QualityVsSpeed qvs) {m_qualityVersusSpeed = qvs; }
        


    void randSeed(int p) { m_randSeed = ((0<=p) ? p : 1);}

    int randSeed() const {return m_randSeed;}
         

    EdgeLengthMeasurement edgeLengthMeasurement() const {
        return m_edgeLengthMeasurement;
    }

    void edgeLengthMeasurement(EdgeLengthMeasurement elm) { m_edgeLengthMeasurement = 
                                   elm; }
 

    AllowedPositions allowedPositions() const { return m_allowedPositions; }

    void allowedPositions(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);
    }
 

    TipOver tipOverCCs() const { return m_tipOverCCs; }

    void tipOverCCs(TipOver to) { m_tipOverCCs = to; }
 
    double minDistCC() const { return m_minDistCC; }

    void minDistCC(double x) { m_minDistCC = (( x > 0) ? x : 1);}
  

    PreSort presortCCs() const { return m_presortCCs; }

    void presortCCs(PreSort ps) { m_presortCCs = ps; }
 
    


    int minGraphSize() const { return m_minGraphSize; }

    void minGraphSize(int n) { m_minGraphSize = ((n >= 2)? n : 2);}
 

    GalaxyChoice galaxyChoice() const { return m_galaxyChoice; }

    void galaxyChoice(GalaxyChoice gc) { m_galaxyChoice = gc; }
 

    int randomTries() const { return m_randomTries; }

    void randomTries(int n) {m_randomTries = ((n>=1)? n: 1);}
 

    MaxIterChange maxIterChange() const { return m_maxIterChange; }

    void maxIterChange(MaxIterChange mic) { m_maxIterChange = mic; }
 

    int maxIterFactor() const { return m_maxIterFactor; }

    void maxIterFactor(int f) { m_maxIterFactor = ((f>=1) ? f : 1 );}   
 

    InitialPlacementMult initialPlacementMult() const {
        return m_initialPlacementMult;
    }
    
    void initialPlacementMult(InitialPlacementMult ipm) { 
      m_initialPlacementMult = ipm; 
    }




    ForceModel forceModel() const { return m_forceModel; }

    void forceModel(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);}
          

    RepulsiveForcesMethod repulsiveForcesCalculation() const {
        return m_repulsiveForcesCalculation;
    }

    void repulsiveForcesCalculation(RepulsiveForcesMethod rfc) {
        m_repulsiveForcesCalculation = rfc;
    }
 

    StopCriterion stopCriterion() const { return m_stopCriterion; }

    void stopCriterion(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);}
 
 

    InitialPlacementForces initialPlacementForces() const {
        return m_initialPlacementForces;
    }

    void initialPlacementForces(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);}


    ReducedTreeConstruction nmTreeConstruction() const { return m_NMTreeConstruction; }

    void nmTreeConstruction(ReducedTreeConstruction rtc) { m_NMTreeConstruction = rtc; }
 

    SmallestCellFinding nmSmallCell() const { return m_NMSmallCell; }

    void nmSmallCell(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; 
    PageFormatType        m_pageFormat; 
    double                m_unitEdgeLength; 
    bool                  m_newInitialPlacement; 
    QualityVsSpeed        m_qualityVersusSpeed; 

    //low level options
    //general options
    int                   m_randSeed; 
    EdgeLengthMeasurement m_edgeLengthMeasurement; 
    AllowedPositions      m_allowedPositions; 
    int                   m_maxIntPosExponent; 

    //options for divide et impera step
    double                m_pageRatio; 
    int                   m_stepsForRotatingComponents; 
    TipOver               m_tipOverCCs; 
    double                m_minDistCC; 
    PreSort               m_presortCCs; 

    //options for multilevel step
    int                   m_minGraphSize; 
    GalaxyChoice          m_galaxyChoice; 
    int                   m_randomTries; 
    MaxIterChange         m_maxIterChange; 



    int                   m_maxIterFactor; 
    InitialPlacementMult m_initialPlacementMult; 

    //options for force calculation step
    ForceModel            m_forceModel; 
    double                m_springStrength; 
    double                m_repForcesStrength; 
    RepulsiveForcesMethod m_repulsiveForcesCalculation; 
    StopCriterion         m_stopCriterion; 
    double                m_threshold; 
    int                   m_fixedIterations; 
    double                m_forceScalingFactor; 
    bool                  m_coolTemperature; 
    double                m_coolValue; 
    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; 
    ReducedTreeConstruction m_NMTreeConstruction; 
    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; 

    FruchtermanReingold FR; 
    NMM NM; 


    //------------------- most important functions ----------------------------

    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, int
                      comp_index);


    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);


    //---------------- functions for pre/pos-processing -----------------------------

    void initialize_all_options();

    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);


    void make_positions_integer(Graph& G, NodeArray<NodeAttributes>& A);

    void create_postscript_drawing(GraphAttributes& AG, char* ps_file);


    //------------------ functions for divide et impera step -----------------------


    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);

    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[]);


    //------------------  functions for multilevel step    --------------------------

    int get_max_mult_iter(int act_level, int max_level, int node_nr);


    //------------------  functions for force calculation ---------------------------

    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  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);

    void deallocate_memory_for_rep_calc_classes();

    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);

    void set_average_ideal_edgelength(Graph& G,EdgeArray<EdgeAttributes>& E);

    double get_average_forcevector_length (Graph& G, NodeArray<DPoint>& F);

    void prevent_oscilations(
        Graph& G, 
        NodeArray<DPoint>& F,
        NodeArray<DPoint>&
        last_node_movement,
        int iter);

    double angle(DPoint& P, DPoint& Q, DPoint& R);

    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);


    //------------------- functions for analytic information -------------------------

    void init_time() { time_total = 0; }
};

} //end namespace ogdf 

#endif