/* * $Revision: 2583 $ * * last checkin: * $Author: gutwenger $ * $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012) $ ***************************************************************/ /** \file * \brief Declaration of Fast Multipole Multilevel Method (FM^3). * * \author Stefan Hachul * * \par License: * This file is part of the Open Graph Drawing Framework (OGDF). * * \par * Copyright (C)
* See README.txt in the root directory of the OGDF installation for details. * * \par * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * Version 2 or 3 as published by the Free Software Foundation; * see the file LICENSE.txt included in the packaging of this file * for details. * * \par * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * \par * You should have received a copy of the GNU General Public * License along with this program; if not, write to the Free * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * Boston, MA 02110-1301, USA. * * \see http://www.gnu.org/copyleft/gpl.html ***************************************************************/ #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 Rectangle; /** * \brief The fast multipole multilevel layout algorithm. * * The class FMMMLayout implements a force-directed graph drawing * method suited also for very large graphs. It is based on a * combination of an efficient multilevel scheme and a strategy for * approximating the repulsive forces in the system by rapidly * evaluating potential fields. * * The implementation is based on the following publication: * * Stefan Hachul, Michael J�nger: Drawing Large Graphs with a * Potential-Field-Based Multilevel Algorithm. 12th International * Symposium on %Graph Drawing 1998, New York (GD '04), LNCS 3383, * pp. 285-295, 2004. * *

Optional parameters

* The following options are the most important. You can set * useHighLevelOptions to true and just need to adjust a few parameters. * However, you can also adjust all parameters that the implementation * uses (see below), but this requires good knowledge of the algorithm. * * * * * * * * * *
OptionTypeDefaultDescription *
useHighLevelOptionsboolfalse * Whether high-level options are used or not. *
pageFormat #PageFormatType #pfSquare * The desired aspect ratio of the layout. *
unitEdgeLengthdouble100.0 * The unit edge length. *
newInitialPlacementboolfalse * Specifies if initial placement of nodes is varied. *
qualityVersusSpeed #QualityVsSpeed #qvsBeautifulAndFast * Indicates if the algorithm is tuned either for best quality or best speed. *
* * If you want to do more detailed fine-tuning, you can adjust all parameters * used by the algorithm. Please refer to the paper cited above for better * understanding of the algorithm. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
General *
randSeedint100 * The seed of the random number generator. *
edgeLengthMeasurement #EdgeLengthMeasurement #elmBoundingCircle * Indicates how the length of an edge is measured. *
allowedPositions #AllowedPositions #apInteger * Defines which positions for a node are allowed. *
maxIntPosExponentint40 * Defines the exponent used if allowedPositions == apExponent. *
Divide et impera step *
pageRatiodouble1.0 * The desired page ratio. *
stepsForRotatingComponentsint10 * The number of rotations per connected component. *
tipOverCCs #TipOver #toNoGrowingRow * Specifies when it is allowed to tip over drawings. *
minDistCCdouble100 * The minimal distance between connected components. *
presortCCs #PreSort #psDecreasingHeight * Defines if the connected components are sorted before * the packing algorithm is applied. *
Multilevel step *
minGraphSizeint50 * Determines the number of nodes of a graph for which * no more collapsing of galaxies is performed. *
galaxyChoice #GalaxyChoice #gcNonUniformProbLowerMass * Defines how sun nodes of galaxies are selected. *
randomTriesint20 * Defines the number of tries to get a random node with * minimal star mass. *
maxIterChange #MaxIterChange #micLinearlyDecreasing * Defines how MaxIterations is changed in subsequent multilevels. *
maxIterFactorint10 * Defines the factor used for decreasing MaxIterations. *
initialPlacementMult #InitialPlacementMult #ipmAdvanced * Defines how the initial placement is generated. *
Force calculation step *
forceModel #ForceModel #fmNew * The used force model. *
springStrengthdouble1.0 * The strength of the springs. *
repForcesStrengthdouble1.0 * The strength of the repulsive forces. *
repulsiveForcesCalculation #RepulsiveForcesMethod #rfcNMM * Defines how to calculate repulsive forces. *
stopCriterion #StopCriterion #scFixedIterationsOrThreshold * The stop criterion. *
thresholddouble0.01 * The threshold for the stop criterion. *
fixedIterationsint30 * The fixed number of iterations for the stop criterion. *
forceScalingFactordouble0.05 * The scaling factor for the forces. *
coolTemperatureboolfalse * Use coolValue for scaling forces. *
coolValuedouble0.99 * The value by which forces are decreased. *
initialPlacementForces #InitialPlacementForces #ipfRandomRandIterNr * Defines how the initial placement is done. *
Force calculation step *
resizeDrawingbooltrue * Specifies if the resulting drawing is resized. *
resizingScalardouble1 * Defines a parameter to scale the drawing if resizeDrawing is true. *
fineTuningIterationsint20 * The number of iterations for fine tuning. *
fineTuneScalardouble0.2 * Defines a parameter for scaling the forces in the fine-tuning iterations. *
adjustPostRepStrengthDynamicallybooltrue * If set to true, the strength of the repulsive force field is calculated. *
postSpringStrengthdouble2.0 * The strength of the springs in the postprocessing step. *
postStrengthOfRepForcesdouble0.01 * The strength of the repulsive forces in the postprocessing step. *
Repulsive force approximation methods *
frGridQuotientint2 * The grid quotient. *
nmTreeConstruction #ReducedTreeConstruction #rtcSubtreeBySubtree * Defines how the reduced bucket quadtree is constructed. *
nmSmallCell #SmallestCellFinding #scfIteratively * Defines how the smallest quadratic cell that surrounds * the particles of a node in the reduced bucket quadtree is calculated. *
nmParticlesInLeavesint25 * The maximal number of particles that are contained in * a leaf of the reduced bucket quadtree. *
nmPrecisionint4 * The precision \a p for the p-term multipole expansions. *
* *

Running time

* The running time of the algorithm is * O(n log n + m) for graphs with \a n nodes * and \a m edges. The required space is linear in the input size. */ class OGDF_EXPORT FMMMLayout : public LayoutModule { public: //! Possible page formats. enum PageFormatType { pfPortrait, //!< A4 portrait page. pfLandscape, //!< A4 landscape page. pfSquare //!< Square format. }; //! Trade-off between run-time and quality. enum QualityVsSpeed { qvsGorgeousAndEfficient, //!< Best quality. qvsBeautifulAndFast, //!< Medium quality and speed. qvsNiceAndIncredibleSpeed //!< Best speed. }; //! Specifies how the length of an edge is measured. enum EdgeLengthMeasurement { elmMidpoint, //!< Measure from center point of edge end points. elmBoundingCircle //!< Measure from border of circle s surrounding edge end points. }; //! Specifies which positions for a node are allowed. enum AllowedPositions { apAll, apInteger, apExponent }; //! Specifies in which case it is allowed to tip over drawings of connected components. enum TipOver { toNone, toNoGrowingRow, toAlways }; //! Specifies how connected components are sorted before the packing algorithm is applied. enum PreSort { psNone, //!< Do not presort. psDecreasingHeight, //!< Presort by decreasing height of components. psDecreasingWidth, //!< Presort by decreasing width of components. psDecreasingArea //!< Presort by decreasing area of components. }; //! Specifies how sun nodes of galaxies are selected. enum GalaxyChoice { gcUniformProb, gcNonUniformProbLowerMass, gcNonUniformProbHigherMass }; //! Specifies how MaxIterations is changed in subsequent multilevels. enum MaxIterChange { micConstant, micLinearlyDecreasing, micRapidlyDecreasing }; //! Specifies how the initial placement is generated. enum InitialPlacementMult { ipmSimple, ipmAdvanced }; //! Specifies the force model. enum ForceModel { fmFruchtermanReingold, //!< The force-model by Fruchterman, Reingold. fmEades, //!< The force-model by Eades. fmNew //!< The new force-model. }; //! Specifies how to calculate repulsive forces. enum RepulsiveForcesMethod { rfcExact, //!< Exact calculation. rfcGridApproximation, //!< Grid approximation. rfcNMM //!< Calculation as for new multipole method. }; //! Specifies the stop criterion. enum StopCriterion { scFixedIterations, //!< Stop if fixedIterations() is reached. scThreshold, //!< Stop if threshold() is reached. scFixedIterationsOrThreshold //!< Stop if fixedIterations() or threshold() is reached. }; //! Specifies how the initial placement is done. enum InitialPlacementForces { ipfUniformGrid, //!< Uniform placement on a grid. ipfRandomTime, //!< Random placement (based on current time). ipfRandomRandIterNr, //!< Random placement (based on randIterNr()). ipfKeepPositions //!< No change in placement. }; //! Specifies how the reduced bucket quadtree is constructed. enum ReducedTreeConstruction { rtcPathByPath, //!< Path-by-path construction. rtcSubtreeBySubtree //!< Subtree-by-subtree construction. }; //! Specifies how to calculate the smallest quadratic cell surrounding particles of a node in the reduced bucket quadtree. enum SmallestCellFinding { scfIteratively, //!< Iteratively (in constant time). scfAluru //!< According to formula by Aluru et al. (in constant time). }; //! Creates an instance of the layout algorithm. FMMMLayout(); // destructor virtual ~FMMMLayout() { } /** * @name The algorithm call * @{ */ //! Calls the algorithm for graph \a GA and returns the layout information in \a AG. void call(GraphAttributes &GA); //! Calls the algorithm for clustered graph \a GA and returns the layout information in \a AG. //! Models cluster by simple edge length adaption based on least common ancestor //! cluster of end vertices. using LayoutModule::call; void call(ClusterGraphAttributes &GA); //! Extended algorithm call: Allows to pass desired lengths of the edges. /** * @param GA represents the input graph and is assigned the computed layout. * @param edgeLength is an edge array of the graph associated with \a GA * of positive edge length. */ void call( GraphAttributes &GA, //graph and layout const EdgeArray &edgeLength); //factor for desired edge lengths //! Extended algorithm call: Calls the algorithm for graph \a AG. /** * Returns layout information in \a AG and a simple drawing is saved in file \a ps_file * in postscript format (Nodes are drawn as uniformly sized circles). */ void call(GraphAttributes &AG, char* ps_file); //! Extend algorithm call: Allows to pass desired lengths of the edges. /** * The EdgeArray \a edgeLength must be valid for AG.constGraph() and its values must * be positive. * A simple drawing is saved in file ps_file in postscript format (Nodes are drawn * as uniformly sized circles). */ void call( GraphAttributes &AG, //graph and layout const EdgeArray &edgeLength, //factor for desired edge lengths char* ps_file); /** @} * @name Further information. * @{ */ //! Returns the runtime (=CPU-time) of the layout algorithm in seconds. double getCpuTime() { return time_total; } /** @} * @name High-level options * Allow to specify the most relevant parameters. * @{ */ //! Returns the current setting of option useHighLevelOptions. /** * If set to true, the high-level options are used to set all low-level options. * Usually, it is sufficient just to set high-level options; if you want to * be more specific, set this parameter to false and set the low level options. */ bool useHighLevelOptions() const { return m_useHighLevelOptions; } //! Sets the option useHighLevelOptions to \a uho. void useHighLevelOptions(bool uho) { m_useHighLevelOptions = uho; } //! Sets single level option, no multilevel hierarchy is created if b == true void setSingleLevel(bool b) {m_singleLevel = b;} //! Returns the current setting of option pageFormat. /** * This option defines the desired aspect ratio of the drawing area. * - \a pfPortrait: A4 page in portrait orientation * - \a pfLandscape: A4 page in landscape orientation * - \a pfSquare: square page format */ PageFormatType pageFormat() const { return m_pageFormat; } //! Sets the option pageRatio to \a t. void pageFormat(PageFormatType t) { m_pageFormat = t; } //! Returns the current setting of option unitEdgeLength. double unitEdgeLength() const { return m_unitEdgeLength; } //! Sets the option unitEdgeLength to \a x. void unitEdgeLength(double x) {m_unitEdgeLength = (( x > 0.0) ? x : 1);} //! Returns the current setting of option newInitialPlacement. /** * This option defines if the initial placement of the nodes at the * coarsest multilevel is varied for each distinct call of FMMMLayout * or keeps always the same. */ bool newInitialPlacement() const { return m_newInitialPlacement; } //! Sets the option newInitialPlacement to \a nip. void newInitialPlacement(bool nip) { m_newInitialPlacement = nip; } //! Returns the current setting of option qualityVersusSpeed. /** * Indicates if the algorithm is tuned either for best quality or best speed. * - \a qvsGorgeousAndEfficient: gorgeous quality and efficient speed * - \a qvsBeautifulAndFast: beautiful quality and fast speed * - \a qvsNiceAndIncredibleSpeed: nice quality and incredible speed */ QualityVsSpeed qualityVersusSpeed() const { return m_qualityVersusSpeed; } //! Sets the option qualityVersusSpeed to \a qvs. void qualityVersusSpeed(QualityVsSpeed qvs) {m_qualityVersusSpeed = qvs; } /** @} * @name General low-level options * The low-level options in this and the following sections are meant for * experts or interested people only. * @{ */ //! Sets the seed of the random number generator. void randSeed(int p) { m_randSeed = ((0<=p) ? p : 1);} //! Returns the seed of the random number generator. int randSeed() const {return m_randSeed;} //! Returns the current setting of option edgeLengthMeasurement. /** * This option indicates how the length of an edge is measured. * Possible values: * - \a elmMidpoint: from center to center * - \a elmBoundingCircle: the distance between the two tight circles bounding the * graphics of two adjacent nodes */ EdgeLengthMeasurement edgeLengthMeasurement() const { return m_edgeLengthMeasurement; } //! Sets the option edgeLengthMeasurement to \a elm. void edgeLengthMeasurement(EdgeLengthMeasurement elm) { m_edgeLengthMeasurement = elm; } //! Returns the current setting of option allowedPositions. /** * This option defines which positions for a node are allowed. * Possibly values: * - \a apAll: every position is allowed * - \a apInteger: only integer positions in the range depending on the number of * nodes * - \a apExponent: only integer positions in the range of -2^MaxIntPosExponent to * 2^MaxIntPosExponent */ AllowedPositions allowedPositions() const { return m_allowedPositions; } //! Sets the option allowedPositions to \a ap. void allowedPositions(AllowedPositions ap) { m_allowedPositions = ap; } //! Returns the current setting of option maxIntPosExponent. /** * This option defines the exponent used if allowedPositions() == \a apExponent. */ int maxIntPosExponent() const { return m_maxIntPosExponent; } //! Sets the option maxIntPosExponent to \a e. void maxIntPosExponent(int e) { m_maxIntPosExponent = (((e >= 31)&&(e<=51))? e : 31); } /** @} * @name Options for the divide et impera step * @{ */ //! Returns the current setting of option pageRatio. /** * This option defines the desired aspect ratio of the rectangular drawing area. */ double pageRatio() const { return m_pageRatio; } //! Sets the option pageRatio to \a r. void pageRatio(double r) {m_pageRatio = (( r > 0) ? r : 1);} //! Returns the current setting of option stepsForRotatingComponents. /** * This options determines the number of times each connected component is rotated with * angles between 0 and 90 degree to obtain a bounding rectangle with small area. */ int stepsForRotatingComponents() const { return m_stepsForRotatingComponents; } //! Sets the option stepsForRotatingComponents to \a n. void stepsForRotatingComponents(int n) { m_stepsForRotatingComponents = ((0<=n) ? n : 0); } //! Returns the current setting of option tipOverCCs. /** * Defines in which case it is allowed to tip over drawings of connected components. * Possible values: * - \a toNone: not allowed at all * - \a toNoGrowingRow: only if the height of the packing row does not grow * - \a toAlways: always allowed */ TipOver tipOverCCs() const { return m_tipOverCCs; } //! Sets the option tipOverCCs to \a to. void tipOverCCs(TipOver to) { m_tipOverCCs = to; } //! Returns the minimal distance between connected components. double minDistCC() const { return m_minDistCC; } //! Sets the minimal distance between connected components to \a x. void minDistCC(double x) { m_minDistCC = (( x > 0) ? x : 1);} //! Returns the current setting of option presortCCs. /** * This option defines if the connected components are sorted before * the packing algorithm is applied. * Possible values: * - \a psNone: no sorting * - \a psDecreasingHeight: sorted by decreasing height * - \a psDecreasingWidth: sorted by decreasing width * - \a psDecreasingArea: sorted by decreasing area */ PreSort presortCCs() const { return m_presortCCs; } //! Sets the option presortCCs to \a ps. void presortCCs(PreSort ps) { m_presortCCs = ps; } /** @} * @name Options for the multilevel step * @{ */ //! Returns the current setting of option minGraphSize. /** * This option determines the number of nodes of a graph in the * multilevel representation for which no more collapsing of galaxies * is performed (i.e. the graph at the highest level). */ int minGraphSize() const { return m_minGraphSize; } //! Sets the option minGraphSize to \a n. void minGraphSize(int n) { m_minGraphSize = ((n >= 2)? n : 2);} //! Returns the current setting of option galaxyChoice. /** * This option defines how sun nodes of galaxies are selected. * Possible values: * - \a gcUniformProb: selecting by uniform random probability * - \a gcNonUniformProbLowerMass: selecting by non-uniform probability depending on * the star masses (prefering nodes with lower star mass) * - \a gcNonUniformProbHigherMass: as above but prefering nodes with higher star mass */ GalaxyChoice galaxyChoice() const { return m_galaxyChoice; } //! Sets the option galaxyChoice to \a gc. void galaxyChoice(GalaxyChoice gc) { m_galaxyChoice = gc; } //! Returns the current setting of option randomTries. /** * This option defines the number of tries to get a random node with * minimal star mass (used in case of galaxyChoice() == gcNonUniformProbLowerMass * and galaxyChoice() == gcNonUniformProbHigherMass). */ int randomTries() const { return m_randomTries; } //! Sets the option randomTries to \a n. void randomTries(int n) {m_randomTries = ((n>=1)? n: 1);} //! Returns the current setting of option maxIterChange. /** * This option defines how MaxIterations is changed in subsequent multilevels. * Possible values: * - \a micConstant: kept constant at the force calculation step at every level * - \a micLinearlyDecreasing: linearly decreasing from MaxIterFactor*FixedIterations * to FixedIterations * - \a micRapidlyDecreasing: rapdily decreasing from MaxIterFactor*FixedIterations * to FixedIterations */ MaxIterChange maxIterChange() const { return m_maxIterChange; } //! Sets the option maxIterChange to \a mic. void maxIterChange(MaxIterChange mic) { m_maxIterChange = mic; } //! Returns the current setting of option maxIterFactor. /** * This option defines the factor used for decrasing MaxIterations * (in case of maxIterChange() == micLinearlyDecreasing or maxIterChange() * == micRapidlyDecreasing). */ int maxIterFactor() const { return m_maxIterFactor; } //! Sets the option maxIterFactor to \a f. void maxIterFactor(int f) { m_maxIterFactor = ((f>=1) ? f : 1 ); } //! Returns the current setting of option initialPlacementMult. /** * This option defines how the initial placement is generated. * Possible values: * - \a ipmSimple: only using information about placement of nodes on higher levels * - \a ipmAdvanced: using additional information about the placement of all inter * - \a solar system nodes */ InitialPlacementMult initialPlacementMult() const { return m_initialPlacementMult; } //! Sets the option initialPlacementMult to \a ipm. void initialPlacementMult(InitialPlacementMult ipm) { m_initialPlacementMult = ipm; } /** @} * @name Options for the force calculation step * @{ */ //! Returns the used force model. /** * Possibly values: * - \a fmFruchtermanReingold: model of Fruchterman and Reingold * - \a fmEades: model of Eades * - \a fmNew: new model */ ForceModel forceModel() const { return m_forceModel; } //! Sets the used force model to \a fm. void forceModel(ForceModel fm) { m_forceModel = fm; } //! Returns the strength of the springs. double springStrength() const { return m_springStrength; } //! Sets the strength of the springs to \a x. void springStrength(double x) { m_springStrength = ((x > 0)? x : 1);} //! Returns the strength of the repulsive forces. double repForcesStrength() const { return m_repForcesStrength; } //! Sets the strength of the repulsive forces to \a x. void repForcesStrength(double x) { m_repForcesStrength =((x > 0)? x : 1);} //! Returns the current setting of option repulsiveForcesCalculation. /** * This option defines how to calculate repulsive forces. * Possible values: * - \a rfcExact: exact calculation (slow) * - \a rfcGridApproximation: grid approxiamtion (inaccurate) * - \a rfcNMM: like in NMM (= New Multipole Method; fast and accurate) */ RepulsiveForcesMethod repulsiveForcesCalculation() const { return m_repulsiveForcesCalculation; } //! Sets the option repulsiveForcesCalculation to \a rfc. void repulsiveForcesCalculation(RepulsiveForcesMethod rfc) { m_repulsiveForcesCalculation = rfc; } //! Returns the stop criterion. /** * Possible values: * - \a rscFixedIterations: stop if fixedIterations() is reached * - \a rscThreshold: stop if threshold() is reached * - \a rscFixedIterationsOrThreshold: stop if fixedIterations() or threshold() * is reached */ StopCriterion stopCriterion() const { return m_stopCriterion; } //! Sets the stop criterion to \a rsc. void stopCriterion(StopCriterion rsc) { m_stopCriterion = rsc; } //! Returns the threshold for the stop criterion. /** * (If the average absolute value of all forces in * an iteration is less then threshold() then stop.) */ double threshold() const { return m_threshold; } //! Sets the threshold for the stop criterion to \a x. void threshold(double x) {m_threshold = ((x > 0) ? x : 0.1);} //! Returns the fixed number of iterations for the stop criterion. int fixedIterations() const { return m_fixedIterations; } //! Sets the fixed number of iterations for the stop criterion to \a n. void fixedIterations(int n) { m_fixedIterations = ((n >= 1) ? n : 1);} //! Returns the scaling factor for the forces. double forceScalingFactor() const { return m_forceScalingFactor; } //! Sets the scaling factor for the forces to \ f. void forceScalingFactor(double f) { m_forceScalingFactor = ((f > 0) ? f : 1);} //! Returns the current setting of option coolTemperature. /** * If set to true, forces are scaled by coolValue()^(actual iteration) * * forceScalingFactor(); otherwise forces are scaled by forceScalingFactor(). */ bool coolTemperature() const { return m_coolTemperature; } //! Sets the option coolTemperature to \a b. void coolTemperature(bool b) { m_coolTemperature = b; } //! Returns the current setting of option coolValue. /** * This option defines the value by which forces are decreased * if coolTemperature is true. */ double coolValue() const { return m_coolValue; } //! Sets the option coolValue to \a x. void coolValue(double x) { m_coolValue = (((x >0 )&&(x<=1) )? x : 0.99);} //! Returns the current setting of option initialPlacementForces. /** * This option defines how the initial placement is done. * Possible values: * - \a ipfUniformGrid: uniform on a grid * - \a ipfRandomTime: random based on actual time * - \a ipfRandomRandIterNr: random based on randIterNr() * - \a ipfKeepPositions: no change in placement */ InitialPlacementForces initialPlacementForces() const { return m_initialPlacementForces; } //! Sets the option initialPlacementForces to \a ipf. void initialPlacementForces(InitialPlacementForces ipf) { m_initialPlacementForces = ipf; } /** @} * @name Options for the postprocessing step * @{ */ //! Returns the current setting of option resizeDrawing. /** * If set to true, the resulting drawing is resized so that the average edge * length is the desired edge length times resizingScalar(). */ bool resizeDrawing() const { return m_resizeDrawing; } //! Sets the option resizeDrawing to \a b. void resizeDrawing(bool b) { m_resizeDrawing = b; } //! Returns the current setting of option resizingScalar. /** * This option defines a parameter to scale the drawing if * resizeDrawing() is true. */ double resizingScalar() const { return m_resizingScalar; } //! Sets the option resizingScalar to \a s. void resizingScalar(double s) { m_resizingScalar = ((s > 0) ? s : 1);} //! Returns the number of iterations for fine tuning. int fineTuningIterations() const { return m_fineTuningIterations; } //! Sets the number of iterations for fine tuning to \a n. void fineTuningIterations(int n) { m_fineTuningIterations =((n >= 0) ? n : 0);} //! Returns the curent setting of option fineTuneScalar. /** * This option defines a parameter for scaling the forces in the * fine-tuning iterations. */ double fineTuneScalar() const { return m_fineTuneScalar; } //! Sets the option fineTuneScalar to \a s void fineTuneScalar(double s) { m_fineTuneScalar = ((s >= 0) ? s : 1);} //! Returns the current setting of option adjustPostRepStrengthDynamically. /** * If set to true, the strength of the repulsive force field is calculated * dynamically by a formula depending on the number of nodes; otherwise the * strength are scaled by PostSpringStrength and PostStrengthOfRepForces. */ bool adjustPostRepStrengthDynamically() const { return m_adjustPostRepStrengthDynamically; } //! Sets the option adjustPostRepStrengthDynamically to \a b. void adjustPostRepStrengthDynamically(bool b) { m_adjustPostRepStrengthDynamically = b; } //! Returns the strength of the springs in the postprocessing step. double postSpringStrength() const { return m_postSpringStrength; } //! Sets the strength of the springs in the postprocessing step to \a x. void postSpringStrength(double x) { m_postSpringStrength = ((x > 0)? x : 1);} //! Returns the strength of the repulsive forces in the postprocessing step. double postStrengthOfRepForces() const { return m_postStrengthOfRepForces; } //! Sets the strength of the repulsive forces in the postprocessing step to \a x. void postStrengthOfRepForces(double x) { m_postStrengthOfRepForces = ((x > 0)? x : 1); } /** @} * @name Options for repulsive force approximation methods * @{ */ //! Returns the current setting of option frGridQuotient. /** * The number k of rows and columns of the grid is sqrt(|V|) / frGridQuotient(). * (Note that in [Fruchterman,Reingold] frGridQuotient is 2.) */ int frGridQuotient() const {return m_frGridQuotient;} //! Sets the option frGridQuotient to \a p. void frGridQuotient(int p) { m_frGridQuotient = ((0<=p) ? p : 2);} //! Returns the current setting of option nmTreeConstruction. /** * This option defines how the reduced bucket quadtree is constructed. * Possible values: * - \a rtcPathByPath: path by path construction * - \a rtcSubtreeBySubtree: subtree by subtree construction */ ReducedTreeConstruction nmTreeConstruction() const { return m_NMTreeConstruction; } //! Sets the option nmTreeConstruction to \a rtc. void nmTreeConstruction(ReducedTreeConstruction rtc) { m_NMTreeConstruction = rtc; } //! Returns the current setting of option nmSmallCell. /** * This option defines how the smallest quadratic cell that surrounds * the particles of a node in the reduced bucket quadtree is calculated. * Possible values: * - \a scfIteratively: iteratively (in constant time) * - \a scfAluru: by the formula by Aluru et al. (in constant time) */ SmallestCellFinding nmSmallCell() const { return m_NMSmallCell; } //! Sets the option nmSmallCell to \a scf. void nmSmallCell(SmallestCellFinding scf) { m_NMSmallCell = scf; } //! Returns the current setting of option nmParticlesInLeaves. /** * Defines the maximal number of particles that are contained in * a leaf of the reduced bucket quadtree. */ int nmParticlesInLeaves() const { return m_NMParticlesInLeaves; } //! Sets the option nmParticlesInLeaves to \a n. void nmParticlesInLeaves(int n) { m_NMParticlesInLeaves = ((n>= 1)? n : 1);} //! Returns the precision \a p for the p-term multipole expansions. int nmPrecision() const { return m_NMPrecision; } //! Sets the precision for the multipole expansions to \ p. void nmPrecision(int p) { m_NMPrecision = ((p >= 1 ) ? p : 1);} //! @} private: //high level options bool m_useHighLevelOptions; //!< The option for using high-level options. PageFormatType m_pageFormat; //!< The option for the page format. double m_unitEdgeLength; //!< The unit edge length. bool m_newInitialPlacement; //!< The option for new initial placement. QualityVsSpeed m_qualityVersusSpeed; //!< The option for quality-vs-speed trade-off. //low level options //general options int m_randSeed; //!< The random seed. EdgeLengthMeasurement m_edgeLengthMeasurement; //!< The option for edge length measurement. AllowedPositions m_allowedPositions; //!< The option for allowed positions. int m_maxIntPosExponent; //!< The option for the used exponent. //options for divide et impera step double m_pageRatio; //!< The desired page ratio. int m_stepsForRotatingComponents; //!< The number of rotations. TipOver m_tipOverCCs; //!< Option for tip-over of connected components. double m_minDistCC; //!< The separation between connected components. PreSort m_presortCCs; //!< The option for presorting connected components. //options for multilevel step bool m_singleLevel; //!< Option for pure single level. int m_minGraphSize; //!< The option for minimal graph size. GalaxyChoice m_galaxyChoice; //!< The selection of galaxy nodes. int m_randomTries; //!< The number of random tries. MaxIterChange m_maxIterChange; //!< The option for how to change MaxIterations. //!< If maxIterChange != micConstant, the iterations are decreased //!< depending on the level, starting from //!< ((maxIterFactor()-1) * fixedIterations()) int m_maxIterFactor; //!< The factor used for decreasing MaxIterations. InitialPlacementMult m_initialPlacementMult; //!< The option for creating initial placement. //options for force calculation step ForceModel m_forceModel; //!< The used force model. double m_springStrength; //!< The strengths of springs. double m_repForcesStrength; //!< The strength of repulsive forces. RepulsiveForcesMethod m_repulsiveForcesCalculation; //!< Option for how to calculate repulsive forces. StopCriterion m_stopCriterion; //!< The stop criterion. double m_threshold; //!< The threshold for the stop criterion. int m_fixedIterations; //!< The fixed number of iterations for the stop criterion. double m_forceScalingFactor; //!< The scaling factor for the forces. bool m_coolTemperature; //!< The option for how to scale forces. double m_coolValue; //!< The value by which forces are decreased. InitialPlacementForces m_initialPlacementForces; //!< The option for how the initial placement is done. //options for postprocessing step bool m_resizeDrawing; //!< The option for resizing the drawing. double m_resizingScalar; //!< Parameter for resizing the drawing. int m_fineTuningIterations; //!< The number of iterations for fine tuning. double m_fineTuneScalar; //!< Parameter for scaling forces during fine tuning. bool m_adjustPostRepStrengthDynamically; //!< The option adjustPostRepStrengthDynamically. double m_postSpringStrength; //!< The strength of springs during postprocessing. double m_postStrengthOfRepForces; //!< The strength of repulsive forces during postprocessing. //options for repulsive force approximation methods int m_frGridQuotient; //!< The grid quotient. ReducedTreeConstruction m_NMTreeConstruction; //!< The option for how to construct reduced bucket quadtree. SmallestCellFinding m_NMSmallCell; //!< The option for how to calculate smallest quadtratic cells. int m_NMParticlesInLeaves; //!< The maximal number of particles in a leaf. int m_NMPrecision; //!< The precision for multipole expansions. //other variables double max_integer_position; //!< The maximum value for an integer position. double cool_factor; //!< Needed for scaling the forces if coolTemperature is true. double average_ideal_edgelength; //!< Measured from center to center. double boxlength; //!< Holds the length of the quadratic comput. box. int number_of_components; //!< The number of components of the graph. DPoint down_left_corner; //!< Holds down left corner of the comput. box. NodeArray radius; //!< Holds the radius of the surrounding circle for each node. double time_total; //!< The runtime (=CPU-time) of the algorithm in seconds. FruchtermanReingold FR; //!< Class for repulsive force calculation (Fruchterman, Reingold). NMM NM; //!< Class for repulsive force calculation. //------------------- most important functions ---------------------------- //! Calls the divide (decomposition into connected components) and impera (drawing and packing of the componenets) step. void call_DIVIDE_ET_IMPERA_step( Graph& G, NodeArray& A, EdgeArray& E); //! Calls the multilevel step for subGraph \a G. void call_MULTILEVEL_step_for_subGraph( Graph& G, NodeArray& A, EdgeArray& E, int comp_index); //! Calls the force calculation step for \a G, \a A, \a E. /** * If act_level is 0 and resizeDrawing is true the drawing is resized. * Furthermore, the maximum number of force calc. steps is calculated * depending on MaxIterChange, act_level, and max_level. */ void call_FORCE_CALCULATION_step ( Graph& G, NodeArray& A, EdgeArray& E, int act_level, int max_level); //! Calls the postprocessing step. void call_POSTPROCESSING_step( Graph& G, NodeArray& A, EdgeArray& E, NodeArray& F, NodeArray& F_attr, NodeArray& F_rep, NodeArray& last_node_movement); //---------------- functions for pre/pos-processing ----------------------------- //! All parameter options are set to the default values. void initialize_all_options(); //! Updates several low level parameter options due to the settings of the high level parameter options. void update_low_level_options_due_to_high_level_options_settings(); //! Imports for each node \a v of \a G its width, height and position(given from \a GA) in \a A. void import_NodeAttributes( const Graph& G, GraphAttributes& GA, NodeArray& A); //! Imports for each edge e of G its desired length given via edgeLength. void import_EdgeAttributes ( const Graph& G, const EdgeArray& edgeLength, EdgeArray & E); //! Sets the individual ideal edge length for each edge \a e. void init_ind_ideal_edgelength( const Graph& G, NodeArray&A, EdgeArray & E); //! The radii of the surrounding circles of the bounding boxes are computed. void set_radii(const Graph& G,NodeArray& A); //! Exports for each node \a v in \a G_reduced the position of the original_node in \a G. void export_NodeAttributes( Graph& G_reduced, NodeArray& A_reduced, GraphAttributes& GA); //! Creates a simple and loopfree copy of \a G and stores the corresponding node / edge attributes. /** * The corresponding node / edge attributes are stored in \a A_reduced and * \a E_reduced; the links to the copy_node and original node are stored in \a A, * \a A_reduced, too. */ void make_simple_loopfree( const Graph& G, NodeArray& A, EdgeArrayE, Graph& G_reduced, NodeArray& A_reduced, EdgeArray& E_reduced); //! Deletes parallel edges of \a G_reduced. /** * Saves for each set of parallel edges one representative edge in \a S and * saves in \a new_edgelength the new edge length of this edge in \a G_reduced. */ void delete_parallel_edges( const Graph& G, EdgeArray& E, Graph& G_reduced, List& S, EdgeArray& new_edgelength); //! Sets for each edge \a e of \a G_reduced in \a S its edgelength to \a new_edgelength[\a e]. /** * Also stores this information in \a E_reduced. */ void update_edgelength( List& S, EdgeArray & new_edgelength, EdgeArray& E_reduced); //! Returns the value for the strength of the repulsive forces. /** * Used in the postprocessing step; depending on \a n = G.numberOfNodes(). */ double get_post_rep_force_strength(int n) { return min(0.2,400.0/double(n)); } //! Makes the node positions integers. /** * If allowedPositions == apInteger the values are in a range depending on * G.number_of_nodes() and the average_ideal_edgelength. If allowed_positions * == apExponent the values are integers in a bounded integer range. */ void make_positions_integer(Graph& G, NodeArray& A); //! Creates a simple drawing of \a AG in postscript format and saves it in file \a ps_file. void create_postscript_drawing(GraphAttributes& AG, char* ps_file); //------------------ functions for divide et impera step ----------------------- //! Constructs the list of connected components of G. /** * Also constructs the corresponding lists with the node / edge attributes * (containing a pointer to the original node in \a G for each node in a subgraph). */ void create_maximum_connected_subGraphs( Graph& G, NodeArray&A, EdgeArray&E, Graph G_sub[], NodeArray A_sub[], EdgeArray E_sub[], NodeArray& component); //! The drawings of the subgraphs are packed. /** * This is done such that the subgraphs do not overlap and fit into a small * box with the desired aspect ratio. */ void pack_subGraph_drawings( NodeArray& A, Graph G_sub[], NodeArray A_sub[]); //! The bounding rectangles of all connected componenents of \a G are calculated and stored in \a R. void calculate_bounding_rectangles_of_components( List& R, Graph G_sub[], NodeArray A_sub[]); //! The bounding rectangle of the componenet_index-th. component of G is returned. Rectangle calculate_bounding_rectangle( Graph& G, NodeArray& A, int componenet_index); /** * If number_of_components > 1, the subgraphs \a G_sub are rotated and skipped to * find bounding rectangles with minimum area. The information is saved in \a R and * the node positions in \a A_sub are updated. If number_of_components == 1 a rotation * with minimal aspect ratio is found instead. */ void rotate_components_and_calculate_bounding_rectangles( List&R, Graph G_sub[], NodeArray A_sub[]); /** * The positions of the nodes in the subgraphs are calculated by using the * information stored in R and are exported to A. (The coordinates of components * which surrounding rectangles have been tipped over in the packing step are * tipped over here,too) */ void export_node_positions( NodeArray& A, List& R, Graph G_sub[], NodeArray A_sub[]); //! Frees dynamically allocated memory for the connected component subgraphs. void delete_all_subGraphs( Graph G_sub[], NodeArray A_sub[], EdgeArray E_sub[]) { delete [] G_sub; delete [] A_sub; delete [] E_sub; } //------------------ functions for multilevel step -------------------------- /** * Returns the maximum number of iterations for the force calc. step depending * on act_level, max_level, FixedIterations, MaxIterChange, MaxIterFactor, * and the number of nodes of the Graph in the actual mutilevel. */ int get_max_mult_iter(int act_level, int max_level, int node_nr); //------------------ functions for force calculation --------------------------- //! The forces are calculated here. void calculate_forces( Graph& G, NodeArray& A, EdgeArray& E,NodeArray& F, NodeArray& F_attr, NodeArray& F_rep, NodeArray& last_node_movement, int iter, int fine_tuning_step); //! The length of the computational box in the first iteration is set (down left corner is at (0,0). void init_boxlength_and_cornercoordinate(Graph& G,NodeArray& A); //! The initial placements of the nodes are created by using initialPlacementForces(). void create_initial_placement (Graph& G,NodeArray& A); //! Sets all entries of \a F to (0,0). void init_F (Graph& G, NodeArray& F); //! Make initializations for the data structures that are used in the choosen class for rep. force calculation. void make_initialisations_for_rep_calc_classes( Graph& G/*, NodeArray &A, NodeArray& F_rep*/); //! Calculates repulsive forces for each node. void calculate_repulsive_forces( Graph &G, NodeArray& A, NodeArray& F_rep) { if(repulsiveForcesCalculation() == rfcExact ) FR.calculate_exact_repulsive_forces(G,A,F_rep); else if(repulsiveForcesCalculation() == rfcGridApproximation ) FR.calculate_approx_repulsive_forces(G,A,F_rep); else //repulsiveForcesCalculation() == rfcNMM NM.calculate_repulsive_forces(G,A,F_rep); } //! Deallocates dynamically allocated memory of the choosen rep. calculation class. void deallocate_memory_for_rep_calc_classes() { if(repulsiveForcesCalculation() == rfcNMM) NM.deallocate_memory(); } //! Calculates attractive forces for each node. void calculate_attractive_forces( Graph& G, NodeArray & A, EdgeArray& E, NodeArray& F_attr); //! Returns the attractive force scalar. double f_attr_scalar (double d,double ind_ideal_edge_length); //! Add attractive and repulsive forces for each node. void add_attr_rep_forces( Graph& G, NodeArray& F_attr, NodeArray& F_rep, NodeArray& F, int iter, int fine_tuning_step); //! Move the nodes. void move_nodes(Graph& G,NodeArray& A,NodeArray& F); //! Computes a new tight computational square-box. /** * (Guaranteeing, that all midpoints are inside the square.) */ void update_boxlength_and_cornercoordinate(Graph& G,NodeArray& A); //! Describes the max. radius of a move in one time step, depending on the number of iterations. double max_radius(int iter) { return (iter == 1) ? boxlength/1000 : boxlength/5; } //! The average_ideal_edgelength for all edges is computed. void set_average_ideal_edgelength(Graph& G,EdgeArray& E); /** * Calculates the average force on each node in the actual iteration, which is * needed if StopCriterion is scThreshold() or scFixedIterationsOrThreshold(). */ double get_average_forcevector_length (Graph& G, NodeArray& F); /** * Depending on the direction of \a last_node_movement[\a v], the length of the next * displacement of node \a v is restricted. */ void prevent_oscilations( Graph& G, NodeArray& F, NodeArray& last_node_movement, int iter); //! Calculates the angle between \a PQ and \a PS in [0,2pi). double angle(DPoint& P, DPoint& Q, DPoint& R); //! \a last_node_movement is initialized to \a F (used after first iteration). void init_last_node_movement( Graph& G, NodeArray& F, NodeArray& last_node_movement); /** * If resizeDrawing is true, the drawing is adapted to the ideal average * edge length by shrinking respectively expanding the drawing area. */ void adapt_drawing_to_ideal_average_edgelength( Graph& G, NodeArray& A, EdgeArray& E); /** * The force is restricted to have values within the comp. box (needed for * exception handling, if the force is too large for further calculations). */ 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; } //------------------- functions for analytic information ------------------------- //! Sets time_total to zero. void init_time() { time_total = 0; } void fixTwistedSplits(Graph &G, NodeArray& A); std::vector getAdjacentNodes(ogdf::node v); std::vector getAdjacentNodesExcluding(ogdf::node v, ogdf::node ex); void followNodesUntilBranch(ogdf::node start, ogdf::node first, ogdf::node * finish, std::vector * path, int * steps); }; } //end namespace ogdf #endif