The fast multipole multilevel layout algorithm. More...

#include <ogdf/energybased/FMMMLayout.h>

Inheritance diagram for ogdf::FMMMLayout:

Public Types
enum	PageFormatType { pfPortrait, pfLandscape, pfSquare }
	Possible page formats. More...
enum	QualityVsSpeed { qvsGorgeousAndEfficient, qvsBeautifulAndFast, qvsNiceAndIncredibleSpeed }
	Trade-off between run-time and quality. More...
enum	EdgeLengthMeasurement { elmMidpoint, elmBoundingCircle }
	Specifies how the length of an edge is measured. More...
enum	AllowedPositions { apAll, apInteger, apExponent }
	Specifies which positions for a node are allowed. More...
enum	TipOver { toNone, toNoGrowingRow, toAlways }
	Specifies in which case it is allowed to tip over drawings of connected components. More...
enum	PreSort { psNone, psDecreasingHeight, psDecreasingWidth }
	Specifies how connected components are sorted before the packing algorithm is applied. More...
enum	GalaxyChoice { gcUniformProb, gcNonUniformProbLowerMass, gcNonUniformProbHigherMass }
	Specifies how sun nodes of galaxies are selected. More...
enum	MaxIterChange { micConstant, micLinearlyDecreasing, micRapidlyDecreasing }
	Specifies how MaxIterations is changed in subsequent multilevels. More...
enum	InitialPlacementMult { ipmSimple, ipmAdvanced }
	Specifies how the initial placement is generated. More...
enum	ForceModel { fmFruchtermanReingold, fmEades, fmNew }
	Specifies the force model. More...
enum	RepulsiveForcesMethod { rfcExact, rfcGridApproximation, rfcNMM }
	Specifies how to calculate repulsive forces. More...
enum	StopCriterion { scFixedIterations, scThreshold, scFixedIterationsOrThreshold }
	Specifies the stop criterion. More...
enum	InitialPlacementForces { ipfUniformGrid, ipfRandomTime, ipfRandomRandIterNr, ipfKeepPositions }
	Specifies how the initial placement is done. More...
enum	ReducedTreeConstruction { rtcPathByPath, rtcSubtreeBySubtree }
	Specifies how the reduced bucket quadtree is constructed. More...
enum	SmallestCellFinding { scfIteratively, scfAluru }
	Specifies how to calculate the smallest quadratic cell surrounding particles of a node in the reduced bucket quadtree. More...
Public Member Functions
	FMMMLayout ()
	Creates an instance of the layout algorithm.
virtual	~FMMMLayout ()
The algorithm call

void	call (GraphAttributes &GA)
	Calls the algorithm for graph GA and returns the layout information in AG.
void	call (ClusterGraphAttributes &GA)
void	call (GraphAttributes &GA, const EdgeArray< double > &edgeLength)
	Extended algorithm call: Allows to pass desired lengths of the edges.
void	call (GraphAttributes &AG, char *ps_file)
	Extended algorithm call: Calls the algorithm for graph AG.
void	call (GraphAttributes &AG, const EdgeArray< double > &edgeLength, char *ps_file)
	Extend algorithm call: Allows to pass desired lengths of the edges.
Further information.

double	getCpuTime ()
	Returns the runtime (=CPU-time) of the layout algorithm in seconds.
High-level options
Allow to specify the most relevant parameters.
bool	useHighLevelOptions () const
	Returns the current setting of option useHighLevelOptions.
void	useHighLevelOptions (bool uho)
	Sets the option useHighLevelOptions to uho.
PageFormatType	pageFormat () const
	Returns the current setting of option pageFormat.
void	pageFormat (PageFormatType t)
	Sets the option pageRatio to t.
double	unitEdgeLength () const
	Returns the current setting of option unitEdgeLength.
void	unitEdgeLength (double x)
	Sets the option unitEdgeLength to x.
bool	newInitialPlacement () const
	Returns the current setting of option newInitialPlacement.
void	newInitialPlacement (bool nip)
	Sets the option newInitialPlacement to nip.
QualityVsSpeed	qualityVersusSpeed () const
	Returns the current setting of option qualityVersusSpeed.
void	qualityVersusSpeed (QualityVsSpeed qvs)
	Sets the option qualityVersusSpeed to qvs.
General low-level options
The low-level options in this and the following sections are meant for experts or interested people only.
void	randSeed (int p)
	Sets the seed of the random number generator.
int	randSeed () const
	Returns the seed of the random number generator.
EdgeLengthMeasurement	edgeLengthMeasurement () const
	Returns the current setting of option edgeLengthMeasurement.
void	edgeLengthMeasurement (EdgeLengthMeasurement elm)
	Sets the option edgeLengthMeasurement to elm.
AllowedPositions	allowedPositions () const
	Returns the current setting of option allowedPositions.
void	allowedPositions (AllowedPositions ap)
	Sets the option allowedPositions to ap.
int	maxIntPosExponent () const
	Returns the current setting of option maxIntPosExponent.
void	maxIntPosExponent (int e)
	Sets the option maxIntPosExponent to e.
Options for the divide et impera step

double	pageRatio () const
	Returns the current setting of option pageRatio.
void	pageRatio (double r)
	Sets the option pageRatio to r.
int	stepsForRotatingComponents () const
	Returns the current setting of option stepsForRotatingComponents.
void	stepsForRotatingComponents (int n)
	Sets the option stepsForRotatingComponents to n.
TipOver	tipOverCCs () const
	Returns the current setting of option tipOverCCs.
void	tipOverCCs (TipOver to)
	Sets the option tipOverCCs to to.
double	minDistCC () const
	Returns the minimal distance between connected components.
void	minDistCC (double x)
	Sets the minimal distance between connected components to x.
PreSort	presortCCs () const
	Returns the current setting of option presortCCs.
void	presortCCs (PreSort ps)
	Sets the option presortCCs to ps.
Options for the multilevel step

int	minGraphSize () const
	Returns the current setting of option minGraphSize.
void	minGraphSize (int n)
	Sets the option minGraphSize to n.
GalaxyChoice	galaxyChoice () const
	Returns the current setting of option galaxyChoice.
void	galaxyChoice (GalaxyChoice gc)
	Sets the option galaxyChoice to gc.
int	randomTries () const
	Returns the current setting of option randomTries.
void	randomTries (int n)
	Sets the option randomTries to n.
MaxIterChange	maxIterChange () const
	Returns the current setting of option maxIterChange.
void	maxIterChange (MaxIterChange mic)
	Sets the option maxIterChange to mic.
int	maxIterFactor () const
	Returns the current setting of option maxIterFactor.
void	maxIterFactor (int f)
	Sets the option maxIterFactor to f.
InitialPlacementMult	initialPlacementMult () const
	Returns the current setting of option initialPlacementMult.
void	initialPlacementMult (InitialPlacementMult ipm)
	Sets the option initialPlacementMult to ipm.
Options for the force calculation step

ForceModel	forceModel () const
	Returns the used force model.
void	forceModel (ForceModel fm)
	Sets the used force model to fm.
double	springStrength () const
	Returns the strength of the springs.
void	springStrength (double x)
	Sets the strength of the springs to x.
double	repForcesStrength () const
	Returns the strength of the repulsive forces.
void	repForcesStrength (double x)
	Sets the strength of the repulsive forces to x.
RepulsiveForcesMethod	repulsiveForcesCalculation () const
	Returns the current setting of option repulsiveForcesCalculation.
void	repulsiveForcesCalculation (RepulsiveForcesMethod rfc)
	Sets the option repulsiveForcesCalculation to rfc.
StopCriterion	stopCriterion () const
	Returns the stop criterion.
void	stopCriterion (StopCriterion rsc)
	Sets the stop criterion to rsc.
double	threshold () const
	Returns the threshold for the stop criterion.
void	threshold (double x)
	Sets the threshold for the stop criterion to x.
int	fixedIterations () const
	Returns the fixed number of iterations for the stop criterion.
void	fixedIterations (int n)
	Sets the fixed number of iterations for the stop criterion to n.
double	forceScalingFactor () const
	Returns the scaling factor for the forces.
void	forceScalingFactor (double f)
	Sets the scaling factor for the forces to \ f.
bool	coolTemperature () const
	Returns the current setting of option coolTemperature.
void	coolTemperature (bool b)
	Sets the option coolTemperature to b.
double	coolValue () const
	Returns the current setting of option coolValue.
void	coolValue (double x)
	Sets the option coolValue to x.
InitialPlacementForces	initialPlacementForces () const
	Returns the current setting of option initialPlacementForces.
void	initialPlacementForces (InitialPlacementForces ipf)
	Sets the option initialPlacementForces to ipf.
Options for the postprocessing step

bool	resizeDrawing () const
	Returns the current setting of option resizeDrawing.
void	resizeDrawing (bool b)
	Sets the option resizeDrawing to b.
double	resizingScalar () const
	Returns the current setting of option resizingScalar.
void	resizingScalar (double s)
	Sets the option resizingScalar to s.
int	fineTuningIterations () const
	Returns the number of iterations for fine tuning.
void	fineTuningIterations (int n)
	Sets the number of iterations for fine tuning to n.
double	fineTuneScalar () const
	Returns the curent setting of option fineTuneScalar.
void	fineTuneScalar (double s)
	Sets the option fineTuneScalar to s.
bool	adjustPostRepStrengthDynamically () const
	Returns the current setting of option adjustPostRepStrengthDynamically.
void	adjustPostRepStrengthDynamically (bool b)
	Sets the option adjustPostRepStrengthDynamically to b.
double	postSpringStrength () const
	Returns the strength of the springs in the postprocessing step.
void	postSpringStrength (double x)
	Sets the strength of the springs in the postprocessing step to x.
double	postStrengthOfRepForces () const
	Returns the strength of the repulsive forces in the postprocessing step.
void	postStrengthOfRepForces (double x)
	Sets the strength of the repulsive forces in the postprocessing step to x.
Options for repulsive force approximation methods

int	frGridQuotient () const
	Returns the current setting of option frGridQuotient.
void	frGridQuotient (int p)
	Sets the option frGridQuotient to p.
ReducedTreeConstruction	nmTreeConstruction () const
	Returns the current setting of option nmTreeConstruction.
void	nmTreeConstruction (ReducedTreeConstruction rtc)
	Sets the option nmTreeConstruction to rtc.
SmallestCellFinding	nmSmallCell () const
	Returns the current setting of option nmSmallCell.
void	nmSmallCell (SmallestCellFinding scf)
	Sets the option nmSmallCell to scf.
int	nmParticlesInLeaves () const
	Returns the current setting of option nmParticlesInLeaves.
void	nmParticlesInLeaves (int n)
	Sets the option nmParticlesInLeaves to n.
int	nmPrecision () const
	Returns the precision p for the p-term multipole expansions.
void	nmPrecision (int p)
	Sets the precision for the multipole expansions to \ p.
Private Member Functions
void	call_DIVIDE_ET_IMPERA_step (Graph &G, NodeArray< NodeAttributes > &A, EdgeArray< EdgeAttributes > &E)
	Calls the divide (decomposition into connected components) and impera (drawing and packing of the componenets) step.
void	call_MULTILEVEL_step_for_subGraph (Graph &G, NodeArray< NodeAttributes > &A, EdgeArray< EdgeAttributes > &E, int comp_index)
	Calls the multilevel step for subGraph G.
void	call_FORCE_CALCULATION_step (Graph &G, NodeArray< NodeAttributes > &A, EdgeArray< EdgeAttributes > &E, int act_level, int max_level)
	Calls the force calculation step for G, A, E.
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)
	Calls the postprocessing step.
void	initialize_all_options ()
	All parameter options are set to the default values.
void	update_low_level_options_due_to_high_level_options_settings ()
	Updates several low level parameter options due to the settings of the high level parameter options.
void	import_NodeAttributes (const Graph &G, GraphAttributes &GA, NodeArray< NodeAttributes > &A)
	Imports for each node v of G its width, height and position(given from GA) in A.
void	import_EdgeAttributes (const Graph &G, const EdgeArray< double > &edgeLength, EdgeArray< EdgeAttributes > &E)
	Imports for each edge e of G its desired length given via edgeLength.
void	init_ind_ideal_edgelength (const Graph &G, NodeArray< NodeAttributes > &A, EdgeArray< EdgeAttributes > &E)
	Sets the individual ideal edge length for each edge e.
void	set_radii (const Graph &G, NodeArray< NodeAttributes > &A)
	The radii of the surrounding circles of the bounding boxes are computed.
void	export_NodeAttributes (Graph &G_reduced, NodeArray< NodeAttributes > &A_reduced, GraphAttributes &GA)
	Exports for each node v in G_reduced the position of the original_node in G.
void	make_simple_loopfree (const Graph &G, NodeArray< NodeAttributes > &A, EdgeArray< EdgeAttributes >E, Graph &G_reduced, NodeArray< NodeAttributes > &A_reduced, EdgeArray< EdgeAttributes > &E_reduced)
	Creates a simple and loopfree copy of G and stores the corresponding node / edge attributes.
void	delete_parallel_edges (const Graph &G, EdgeArray< EdgeAttributes > &E, Graph &G_reduced, List< edge > &S, EdgeArray< double > &new_edgelength)
	Deletes parallel edges of G_reduced.
void	update_edgelength (List< edge > &S, EdgeArray< double > &new_edgelength, EdgeArray< EdgeAttributes > &E_reduced)
	Sets for each edge e of G_reduced in S its edgelength to new_edgelength[e].
double	get_post_rep_force_strength (int n)
	Returns the value for the strength of the repulsive forces.
void	make_positions_integer (Graph &G, NodeArray< NodeAttributes > &A)
	Makes the node positions integers.
void	create_postscript_drawing (GraphAttributes &AG, char *ps_file)
	Creates a simple drawing of AG in postscript format and saves it in file 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)
	Constructs the list of connected components of G.
void	pack_subGraph_drawings (NodeArray< NodeAttributes > &A, Graph G_sub[], NodeArray< NodeAttributes > A_sub[])
	The drawings of the subgraphs are packed.
void	calculate_bounding_rectangles_of_components (List< Rectangle > &R, Graph G_sub[], NodeArray< NodeAttributes > A_sub[])
	The bounding rectangles of all connected componenents of G are calculated and stored in R.
Rectangle	calculate_bounding_rectangle (Graph &G, NodeArray< NodeAttributes > &A, int componenet_index)
	The bounding rectangle of the componenet_index-th. component of G is returned.
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[])
	Frees dynamically allocated memory for the connected component subgraphs.
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)
	The forces are calculated here.
void	init_boxlength_and_cornercoordinate (Graph &G, NodeArray< NodeAttributes > &A)
	The length of the computational box in the first iteration is set (down left corner is at (0,0).
void	create_initial_placement (Graph &G, NodeArray< NodeAttributes > &A)
	The initial placements of the nodes are created by using initialPlacementForces().
void	init_F (Graph &G, NodeArray< DPoint > &F)
	Sets all entries of F to (0,0).
void	make_initialisations_for_rep_calc_classes (Graph &G)
	Make initializations for the data structures that are used in the choosen class for rep. force calculation.
void	calculate_repulsive_forces (Graph &G, NodeArray< NodeAttributes > &A, NodeArray< DPoint > &F_rep)
	Calculates repulsive forces for each node.
void	deallocate_memory_for_rep_calc_classes ()
	Deallocates dynamically allocated memory of the choosen rep. calculation class.
void	calculate_attractive_forces (Graph &G, NodeArray< NodeAttributes > &A, EdgeArray< EdgeAttributes > &E, NodeArray< DPoint > &F_attr)
	Calculates attractive forces for each node.
double	f_attr_scalar (double d, double ind_ideal_edge_length)
	Returns the attractive force scalar.
void	add_attr_rep_forces (Graph &G, NodeArray< DPoint > &F_attr, NodeArray< DPoint > &F_rep, NodeArray< DPoint > &F, int iter, int fine_tuning_step)
	Add attractive and repulsive forces for each node.
void	move_nodes (Graph &G, NodeArray< NodeAttributes > &A, NodeArray< DPoint > &F)
	Move the nodes.
void	update_boxlength_and_cornercoordinate (Graph &G, NodeArray< NodeAttributes > &A)
	Computes a new tight computational square-box.
double	max_radius (int iter)
	Describes the max. radius of a move in one time step, depending on the number of iterations.
void	set_average_ideal_edgelength (Graph &G, EdgeArray< EdgeAttributes > &E)
	The average_ideal_edgelength for all edges is computed.
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)
	Calculates the angle between PQ and PS in [0,2pi).
void	init_last_node_movement (Graph &G, NodeArray< DPoint > &F, NodeArray< DPoint > &last_node_movement)
	last_node_movement is initialized to F (used after first iteration).
void	adapt_drawing_to_ideal_average_edgelength (Graph &G, NodeArray< NodeAttributes > &A, EdgeArray< EdgeAttributes > &E)
void	restrict_force_to_comp_box (DPoint &force)
void	init_time ()
	Sets time_total to zero.
Private Attributes
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.
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.
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.
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
int	m_maxIterFactor
	The factor used for decreasing MaxIterations.
InitialPlacementMult	m_initialPlacementMult
	The option for creating initial placement.
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.
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.
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.
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< double >	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.

Detailed Description

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 repusive 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.

Option	Type	Default	Description
useHighLevelOptions	bool	false	Wether high-level options are used or not.
pageFormat	PageFormatType	pfSquare	The desired apsect ratio of the layout.
unitEdgeLength	double	100.0	The unit edge length.
newInitialPlacement	bool	false	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
randSeed	int	100	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.
maxIntPosExponent	int	40	Defines the exponent used if allowedPositions == apExponent.
Divide et impera step
pageRatio	double	1.0	The desired page ratio.
stepsForRotatingComponents	int	10	The number of rotations per connected component.
tipOverCCs	TipOver	toNoGrowingRow	Specifies when it is allowed to tip over drawings.
minDistCC	double	100	The minimal distance between connected components.
presortCCs	PreSort	psDecreasingHeight	Defines if the connected components are sorted before the packing algorithm is applied.
Multilevel step
minGraphSize	int	50	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.
randomTries	int	20	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.
maxIterFactor	int	10	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.
springStrength	double	1.0	The strength of the springs.
repForcesStrength	double	1.0	The strength of the repulsive forces.
repulsiveForcesCalculation	RepulsiveForcesMethod	rfcNMM	Defines how to calculate repulsive forces.
stopCriterion	StopCriterion	scFixedIterationsOrThreshold	The stop criterion.
threshold	double	0.01	The threshold for the stop criterion.
fixedIterations	int	30	The fixed number of iterations for the stop criterion.
forceScalingFactor	double	0.05	The scaling factor for the forces.
coolTemperature	bool	false	Use coolValue for scaling forces.
coolValue	double	0.99	The value by which forces are decreased.
initialPlacementForces	InitialPlacementForces	ipfRandomRandIterNr	Defines how the initial placement is done.
Force calculation step
resizeDrawing	bool	true	Specifies if the resulting drawing is resized.
resizingScalar	double	1	Defines a parameter to scale the drawing if resizeDrawing is true.
fineTuningIterations	int	20	The number of iterations for fine tuning.
fineTuneScalar	double	0.2	Defines a parameter for scaling the forces in the fine-tuning iterations.
adjustPostRepStrengthDynamically	bool	true	If set to true, the strength of the repulsive force field is calculated.
postSpringStrength	double	2.0	The strength of the springs in the postprocessing step.
postStrengthOfRepForces	double	0.01	The strength of the repulsive forces in the postprocessing step.
Repulsive force approximation methods
frGridQuotient	int	2	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.
nmParticlesInLeaves	int	25	The maximal number of particles that are contained in a leaf of the reduced bucket quadtree.
nmPrecision	int	4	The precision p for the p-term multipole expansions.

Running time

The running time of the algorithm is O(n log n + m) for graphs with n nodes and m edges. The required space is linear in the input size.

Definition at line 257 of file FMMMLayout.h.

Member Enumeration Documentation

enum ogdf::FMMMLayout::AllowedPositions

Specifies which positions for a node are allowed.

Enumerator:

apAll
apInteger
apExponent

Definition at line 281 of file FMMMLayout.h.

enum ogdf::FMMMLayout::EdgeLengthMeasurement

Specifies how the length of an edge is measured.

Enumerator:

elmMidpoint	Measure from center point of edge end points.
elmBoundingCircle	Measure from border of circle s surrounding edge end points.

Definition at line 275 of file FMMMLayout.h.

enum ogdf::FMMMLayout::ForceModel

Specifies the force model.

Enumerator:

fmFruchtermanReingold	The force-model by Fruchterman, Reingold.
fmEades	The force-model by Eades.
fmNew	The new force-model.

Definition at line 322 of file FMMMLayout.h.

enum ogdf::FMMMLayout::GalaxyChoice

Specifies how sun nodes of galaxies are selected.

Enumerator:

gcUniformProb
gcNonUniformProbLowerMass
gcNonUniformProbHigherMass

Definition at line 302 of file FMMMLayout.h.

enum ogdf::FMMMLayout::InitialPlacementForces

Specifies how the initial placement is done.

Enumerator:

ipfUniformGrid	Uniform placement on a grid.
ipfRandomTime	Random placement (based on current time).
ipfRandomRandIterNr	Random placement (based on randIterNr()).
ipfKeepPositions	No change in placement.

Definition at line 343 of file FMMMLayout.h.

enum ogdf::FMMMLayout::InitialPlacementMult

Specifies how the initial placement is generated.

Enumerator:

ipmSimple
ipmAdvanced

Definition at line 316 of file FMMMLayout.h.

enum ogdf::FMMMLayout::MaxIterChange

Specifies how MaxIterations is changed in subsequent multilevels.

Enumerator:

micConstant
micLinearlyDecreasing
micRapidlyDecreasing

Definition at line 309 of file FMMMLayout.h.

enum ogdf::FMMMLayout::PageFormatType

Possible page formats.

Enumerator:

pfPortrait	A4 portrait page.
pfLandscape	A4 landscape page.
pfSquare	Square format.

Definition at line 261 of file FMMMLayout.h.

enum ogdf::FMMMLayout::PreSort

Specifies how connected components are sorted before the packing algorithm is applied.

Enumerator:

psNone	Do not presort.
psDecreasingHeight	Presort by decreasing height of components.
psDecreasingWidth	Presort by decreasing width of components.

Definition at line 295 of file FMMMLayout.h.

enum ogdf::FMMMLayout::QualityVsSpeed

Trade-off between run-time and quality.

Enumerator:

qvsGorgeousAndEfficient	Best quality.
qvsBeautifulAndFast	Medium quality and speed.
qvsNiceAndIncredibleSpeed	Best speed.

Definition at line 268 of file FMMMLayout.h.

enum ogdf::FMMMLayout::ReducedTreeConstruction

Specifies how the reduced bucket quadtree is constructed.

Enumerator:

rtcPathByPath	Path-by-path construction.
rtcSubtreeBySubtree	Subtree-by-subtree construction.

Definition at line 351 of file FMMMLayout.h.

enum ogdf::FMMMLayout::RepulsiveForcesMethod

Specifies how to calculate repulsive forces.

Enumerator:

rfcExact	Exact calculation.
rfcGridApproximation	Grid approximation.
rfcNMM	Calculation as for new multipole method.

Definition at line 329 of file FMMMLayout.h.

enum ogdf::FMMMLayout::SmallestCellFinding

Specifies how to calculate the smallest quadratic cell surrounding particles of a node in the reduced bucket quadtree.

Enumerator:

scfIteratively	Iteratively (in constant time).
scfAluru	According to formula by Aluru et al. (in constant time).

Definition at line 357 of file FMMMLayout.h.

enum ogdf::FMMMLayout::StopCriterion

Specifies the stop criterion.

Enumerator:

scFixedIterations	Stop if fixedIterations() is reached.
scThreshold	Stop if threshold() is reached.
scFixedIterationsOrThreshold	Stop if fixedIterations() or threshold() is reached.

Definition at line 336 of file FMMMLayout.h.

enum ogdf::FMMMLayout::TipOver

Specifies in which case it is allowed to tip over drawings of connected components.

Enumerator:

toNone
toNoGrowingRow
toAlways

Definition at line 288 of file FMMMLayout.h.

Constructor & Destructor Documentation

ogdf::FMMMLayout::FMMMLayout ( )

Creates an instance of the layout algorithm.

virtual ogdf::FMMMLayout::~FMMMLayout ( ) [inline, virtual]

Definition at line 367 of file FMMMLayout.h.

Member Function Documentation

void ogdf::FMMMLayout::adapt_drawing_to_ideal_average_edgelength	(	Graph &	G,
		NodeArray< NodeAttributes > &	A,
		EdgeArray< EdgeAttributes > &	E
	)			`[private]`

If resizeDrawing is true, the drawing is adapted to the ideal average edge length by shrinking respectively expanding the drawing area.

void ogdf::FMMMLayout::add_attr_rep_forces	(	Graph &	G,
		NodeArray< DPoint > &	F_attr,
		NodeArray< DPoint > &	F_rep,
		NodeArray< DPoint > &	F,
		int	iter,
		int	fine_tuning_step
	)			`[private]`

Add attractive and repulsive forces for each node.

bool ogdf::FMMMLayout::adjustPostRepStrengthDynamically ( ) const [inline]

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.

Definition at line 846 of file FMMMLayout.h.

void ogdf::FMMMLayout::adjustPostRepStrengthDynamically ( bool b ) [inline]

Sets the option adjustPostRepStrengthDynamically to b.

Definition at line 851 of file FMMMLayout.h.

AllowedPositions ogdf::FMMMLayout::allowedPositions ( ) const [inline]

Returns the current setting of option allowedPositions.

This option defines which positions for a node are allowed. Possibly values:

apAll: every position is allowed
apInteger: only integer positions in the range depending on the number of nodes
apExponent: only integer positions in the range of -2^MaxIntPosExponent to 2^MaxIntPosExponent

Definition at line 516 of file FMMMLayout.h.

void ogdf::FMMMLayout::allowedPositions ( AllowedPositions ap ) [inline]

Sets the option allowedPositions to ap.

Definition at line 519 of file FMMMLayout.h.

double ogdf::FMMMLayout::angle	(	DPoint &	P,
		DPoint &	Q,
		DPoint &	R
	)			`[private]`

Calculates the angle between PQ and PS in [0,2pi).

double ogdf::FMMMLayout::calculate_area	(	double	width,
		double	height,
		int	comp_nr
	)			`[private]`

Returns the area (aspect ratio area) of a rectangle with width w and height h if comp_nr > 1 ( comp_nr == 1).

void ogdf::FMMMLayout::calculate_attractive_forces	(	Graph &	G,
		NodeArray< NodeAttributes > &	A,
		EdgeArray< EdgeAttributes > &	E,
		NodeArray< DPoint > &	F_attr
	)			`[private]`

Calculates attractive forces for each node.

Rectangle ogdf::FMMMLayout::calculate_bounding_rectangle	(	Graph &	G,
		NodeArray< NodeAttributes > &	A,
		int	componenet_index
	)			`[private]`

The bounding rectangle of the componenet_index-th. component of G is returned.

void ogdf::FMMMLayout::calculate_bounding_rectangles_of_components	(	List< Rectangle > &	R,
		Graph	G_sub[],
		NodeArray< NodeAttributes >	A_sub[]
	)			`[private]`

The bounding rectangles of all connected componenents of G are calculated and stored in R.

void ogdf::FMMMLayout::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
	)			`[private]`

The forces are calculated here.

void ogdf::FMMMLayout::calculate_repulsive_forces	(	Graph &	G,
		NodeArray< NodeAttributes > &	A,
		NodeArray< DPoint > &	F_rep
	)			`[private]`

Calculates repulsive forces for each node.

void ogdf::FMMMLayout::call	(	GraphAttributes &	AG,
		char *	ps_file
	)

Extended algorithm call: Calls the algorithm for graph AG.

Returns layout information in AG and a simple drawing is saved in file ps_file in postscript format (Nodes are drawn as uniformly sized circles).

void ogdf::FMMMLayout::call ( GraphAttributes & GA ) [virtual]

Calls the algorithm for graph GA and returns the layout information in AG.

Implements ogdf::LayoutModule.

void ogdf::FMMMLayout::call	(	GraphAttributes &	AG,
		const EdgeArray< double > &	edgeLength,
		char *	ps_file
	)

Extend algorithm call: Allows to pass desired lengths of the edges.

The EdgeArray 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 ogdf::FMMMLayout::call ( ClusterGraphAttributes & GA )

Calls the algorithm for clustered graph GA and returns the layout information in AG. Models cluster by simple edge length adaption based on least common ancestor cluster of end vertices.

void ogdf::FMMMLayout::call	(	GraphAttributes &	GA,
		const EdgeArray< double > &	edgeLength
	)

Extended algorithm call: Allows to pass desired lengths of the edges.

Parameters:

edgeLength

is an edge array of the graph associated with GA of positive edge length.

void ogdf::FMMMLayout::call_DIVIDE_ET_IMPERA_step	(	Graph &	G,
		NodeArray< NodeAttributes > &	A,
		EdgeArray< EdgeAttributes > &	E
	)			`[private]`

Calls the divide (decomposition into connected components) and impera (drawing and packing of the componenets) step.

void ogdf::FMMMLayout::call_FORCE_CALCULATION_step	(	Graph &	G,
		NodeArray< NodeAttributes > &	A,
		EdgeArray< EdgeAttributes > &	E,
		int	act_level,
		int	max_level
	)			`[private]`

Calls the force calculation step for G, 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 ogdf::FMMMLayout::call_MULTILEVEL_step_for_subGraph	(	Graph &	G,
		NodeArray< NodeAttributes > &	A,
		EdgeArray< EdgeAttributes > &	E,
		int	comp_index
	)			`[private]`

Calls the multilevel step for subGraph G.

void ogdf::FMMMLayout::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
	)			`[private]`

Calls the postprocessing step.

void ogdf::FMMMLayout::coolTemperature ( bool b ) [inline]

Sets the option coolTemperature to b.

Definition at line 767 of file FMMMLayout.h.

bool ogdf::FMMMLayout::coolTemperature ( ) const [inline]

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().

Definition at line 764 of file FMMMLayout.h.

double ogdf::FMMMLayout::coolValue ( ) const [inline]

Returns the current setting of option coolValue.

This option defines the value by which forces are decreased if coolTemperature is true.

Definition at line 774 of file FMMMLayout.h.

void ogdf::FMMMLayout::coolValue ( double x ) [inline]

Sets the option coolValue to x.

Definition at line 777 of file FMMMLayout.h.

void ogdf::FMMMLayout::create_initial_placement	(	Graph &	G,
		NodeArray< NodeAttributes > &	A
	)			`[private]`

The initial placements of the nodes are created by using initialPlacementForces().

void ogdf::FMMMLayout::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
	)			`[private]`

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 G for each node in a subgraph).

void ogdf::FMMMLayout::create_postscript_drawing	(	GraphAttributes &	AG,
		char *	ps_file
	)			`[private]`

Creates a simple drawing of AG in postscript format and saves it in file ps_file.

void ogdf::FMMMLayout::deallocate_memory_for_rep_calc_classes ( ) [private]

Deallocates dynamically allocated memory of the choosen rep. calculation class.

void ogdf::FMMMLayout::delete_all_subGraphs	(	Graph	G_sub[],
		NodeArray< NodeAttributes >	A_sub[],
		EdgeArray< EdgeAttributes >	E_sub[]
	)			`[private]`

Frees dynamically allocated memory for the connected component subgraphs.

void ogdf::FMMMLayout::delete_parallel_edges	(	const Graph &	G,
		EdgeArray< EdgeAttributes > &	E,
		Graph &	G_reduced,
		List< edge > &	S,
		EdgeArray< double > &	new_edgelength
	)			`[private]`

Deletes parallel edges of G_reduced.

Saves for each set of parallel edges one representative edge in S and saves in new_edgelength the new edge length of this edge in G_reduced.

EdgeLengthMeasurement ogdf::FMMMLayout::edgeLengthMeasurement ( ) const [inline]

Returns the current setting of option edgeLengthMeasurement.

This option indicates how the length of an edge is measured. Possible values:

elmMidpoint: from center to center
elmBoundingCircle: the distance between the two tight circles bounding the graphics of two adjacent nodes

Definition at line 498 of file FMMMLayout.h.

void ogdf::FMMMLayout::edgeLengthMeasurement ( EdgeLengthMeasurement elm ) [inline]

Sets the option edgeLengthMeasurement to elm.

Definition at line 503 of file FMMMLayout.h.

void ogdf::FMMMLayout::export_node_positions	(	NodeArray< NodeAttributes > &	A,
		List< Rectangle > &	R,
		Graph	G_sub[],
		NodeArray< NodeAttributes >	A_sub[]
	)			`[private]`

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 ogdf::FMMMLayout::export_NodeAttributes	(	Graph &	G_reduced,
		NodeArray< NodeAttributes > &	A_reduced,
		GraphAttributes &	GA
	)			`[private]`

Exports for each node v in G_reduced the position of the original_node in G.

double ogdf::FMMMLayout::f_attr_scalar	(	double	d,
		double	ind_ideal_edge_length
	)			`[private]`

Returns the attractive force scalar.

double ogdf::FMMMLayout::fineTuneScalar ( ) const [inline]

Returns the curent setting of option fineTuneScalar.

This option defines a parameter for scaling the forces in the fine-tuning iterations.

Definition at line 835 of file FMMMLayout.h.

void ogdf::FMMMLayout::fineTuneScalar ( double s ) [inline]

Sets the option fineTuneScalar to s.

Definition at line 838 of file FMMMLayout.h.

int ogdf::FMMMLayout::fineTuningIterations ( ) const [inline]

Returns the number of iterations for fine tuning.

Definition at line 825 of file FMMMLayout.h.

void ogdf::FMMMLayout::fineTuningIterations ( int n ) [inline]

Sets the number of iterations for fine tuning to n.

Definition at line 828 of file FMMMLayout.h.

int ogdf::FMMMLayout::fixedIterations ( ) const [inline]

Returns the fixed number of iterations for the stop criterion.

Definition at line 748 of file FMMMLayout.h.

void ogdf::FMMMLayout::fixedIterations ( int n ) [inline]

Sets the fixed number of iterations for the stop criterion to n.

Definition at line 751 of file FMMMLayout.h.

ForceModel ogdf::FMMMLayout::forceModel ( ) const [inline]

Returns the used force model.

Possibly values:

fmFruchtermanReingold: model of Fruchterman and Reingold
fmEades: model of Eades
fmNew: new model

Definition at line 690 of file FMMMLayout.h.

void ogdf::FMMMLayout::forceModel ( ForceModel fm ) [inline]

Sets the used force model to fm.

Definition at line 693 of file FMMMLayout.h.

void ogdf::FMMMLayout::forceScalingFactor ( double f ) [inline]

Sets the scaling factor for the forces to \ f.

Definition at line 757 of file FMMMLayout.h.

double ogdf::FMMMLayout::forceScalingFactor ( ) const [inline]

Returns the scaling factor for the forces.

Definition at line 754 of file FMMMLayout.h.

int ogdf::FMMMLayout::frGridQuotient ( ) const [inline]

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

Definition at line 880 of file FMMMLayout.h.

void ogdf::FMMMLayout::frGridQuotient ( int p ) [inline]

Sets the option frGridQuotient to p.

Definition at line 883 of file FMMMLayout.h.

GalaxyChoice ogdf::FMMMLayout::galaxyChoice ( ) const [inline]

Returns the current setting of option galaxyChoice.

This option defines how sun nodes of galaxies are selected. Possible values:

gcUniformProb: selecting by uniform random probability
gcNonUniformProbLowerMass: selecting by non-uniform probability depending on the star masses (prefering nodes with lower star mass)
gcNonUniformProbHigherMass: as above but prefering nodes with higher star mass

Definition at line 618 of file FMMMLayout.h.

void ogdf::FMMMLayout::galaxyChoice ( GalaxyChoice gc ) [inline]

Sets the option galaxyChoice to gc.

Definition at line 621 of file FMMMLayout.h.

double ogdf::FMMMLayout::get_average_forcevector_length	(	Graph &	G,
		NodeArray< DPoint > &	F
	)			`[private]`

Calculates the average force on each node in the actual iteration, which is needed if StopCriterion is scThreshold() or scFixedIterationsOrThreshold().

int ogdf::FMMMLayout::get_max_mult_iter	(	int	act_level,
		int	max_level,
		int	node_nr
	)			`[private]`

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.

double ogdf::FMMMLayout::get_post_rep_force_strength ( int n ) [private]

Returns the value for the strength of the repulsive forces.

Used in the postprocessing step; depending on = G.numberOfNodes().

double ogdf::FMMMLayout::getCpuTime ( )

Returns the runtime (=CPU-time) of the layout algorithm in seconds.

void ogdf::FMMMLayout::import_EdgeAttributes	(	const Graph &	G,
		const EdgeArray< double > &	edgeLength,
		EdgeArray< EdgeAttributes > &	E
	)			`[private]`

Imports for each edge e of G its desired length given via edgeLength.

void ogdf::FMMMLayout::import_NodeAttributes	(	const Graph &	G,
		GraphAttributes &	GA,
		NodeArray< NodeAttributes > &	A
	)			`[private]`

Imports for each node v of G its width, height and position(given from GA) in A.

void ogdf::FMMMLayout::init_boxlength_and_cornercoordinate	(	Graph &	G,
		NodeArray< NodeAttributes > &	A
	)			`[private]`

The length of the computational box in the first iteration is set (down left corner is at (0,0).

void ogdf::FMMMLayout::init_F	(	Graph &	G,
		NodeArray< DPoint > &	F
	)			`[private]`

Sets all entries of F to (0,0).

void ogdf::FMMMLayout::init_ind_ideal_edgelength	(	const Graph &	G,
		NodeArray< NodeAttributes > &	A,
		EdgeArray< EdgeAttributes > &	E
	)			`[private]`

Sets the individual ideal edge length for each edge e.

void ogdf::FMMMLayout::init_last_node_movement	(	Graph &	G,
		NodeArray< DPoint > &	F,
		NodeArray< DPoint > &	last_node_movement
	)			`[private]`

last_node_movement is initialized to F (used after first iteration).

void ogdf::FMMMLayout::init_time ( ) [inline, private]

Sets time_total to zero.

Definition at line 1322 of file FMMMLayout.h.

void ogdf::FMMMLayout::initialize_all_options ( ) [private]

All parameter options are set to the default values.

InitialPlacementForces ogdf::FMMMLayout::initialPlacementForces ( ) const [inline]

Returns the current setting of option initialPlacementForces.

This option defines how the initial placement is done. Possible values:

ipfUniformGrid: uniform on a grid
ipfRandomTime: random based on actual time
ipfRandomRandIterNr: random based on randIterNr()
ipfKeepPositions: no change in placement

Definition at line 789 of file FMMMLayout.h.

void ogdf::FMMMLayout::initialPlacementForces ( InitialPlacementForces ipf ) [inline]

Sets the option initialPlacementForces to ipf.

Definition at line 794 of file FMMMLayout.h.

InitialPlacementMult ogdf::FMMMLayout::initialPlacementMult ( ) const [inline]

Returns the current setting of option initialPlacementMult.

This option defines how the initial placement is generated. Possible values:

ipmSimple: only using information about placement of nodes on higher levels
ipmAdvanced: using additional information about the placement of all inter
solar system nodes

Definition at line 668 of file FMMMLayout.h.

void ogdf::FMMMLayout::initialPlacementMult ( InitialPlacementMult ipm ) [inline]

Sets the option initialPlacementMult to ipm.

Definition at line 673 of file FMMMLayout.h.

void ogdf::FMMMLayout::make_initialisations_for_rep_calc_classes ( Graph & G ) [private]

Make initializations for the data structures that are used in the choosen class for rep. force calculation.

void ogdf::FMMMLayout::make_positions_integer	(	Graph &	G,
		NodeArray< NodeAttributes > &	A
	)			`[private]`

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 ogdf::FMMMLayout::make_simple_loopfree	(	const Graph &	G,
		NodeArray< NodeAttributes > &	A,
		EdgeArray< EdgeAttributes >	E,
		Graph &	G_reduced,
		NodeArray< NodeAttributes > &	A_reduced,
		EdgeArray< EdgeAttributes > &	E_reduced
	)			`[private]`

Creates a simple and loopfree copy of G and stores the corresponding node / edge attributes.

The corresponding node / edge attributes are stored in A_reduced and E_reduced; the links to the copy_node and original node are stored in A, A_reduced, too.

double ogdf::FMMMLayout::max_radius ( int iter ) [private]

Describes the max. radius of a move in one time step, depending on the number of iterations.

void ogdf::FMMMLayout::maxIntPosExponent ( int e ) [inline]

Sets the option maxIntPosExponent to e.

Definition at line 528 of file FMMMLayout.h.

int ogdf::FMMMLayout::maxIntPosExponent ( ) const [inline]

Returns the current setting of option maxIntPosExponent.

This option defines the exponent used if allowedPositions() == apExponent.

Definition at line 525 of file FMMMLayout.h.

MaxIterChange ogdf::FMMMLayout::maxIterChange ( ) const [inline]

Returns the current setting of option maxIterChange.

This option defines how MaxIterations is changed in subsequent multilevels. Possible values:

micConstant: kept constant at the force calculation step at every level
micLinearlyDecreasing: linearly decreasing from MaxIterFactor*FixedIterations to FixedIterations
micRapidlyDecreasing: rapdily decreasing from MaxIterFactor*FixedIterations to FixedIterations

Definition at line 644 of file FMMMLayout.h.

void ogdf::FMMMLayout::maxIterChange ( MaxIterChange mic ) [inline]

Sets the option maxIterChange to mic.

Definition at line 647 of file FMMMLayout.h.

int ogdf::FMMMLayout::maxIterFactor ( ) const [inline]

Returns the current setting of option maxIterFactor.

This option defines the factor used for decrasing MaxIterations (in case of maxIterChange() == micLinearlyDecreasing or maxIterChange() == micRapidlyDecreasing).

Definition at line 655 of file FMMMLayout.h.

void ogdf::FMMMLayout::maxIterFactor ( int f ) [inline]

Sets the option maxIterFactor to f.

Definition at line 658 of file FMMMLayout.h.

void ogdf::FMMMLayout::minDistCC ( double x ) [inline]

Sets the minimal distance between connected components to x.

Definition at line 576 of file FMMMLayout.h.

double ogdf::FMMMLayout::minDistCC ( ) const [inline]

Returns the minimal distance between connected components.

Definition at line 573 of file FMMMLayout.h.

void ogdf::FMMMLayout::minGraphSize ( int n ) [inline]

Sets the option minGraphSize to n.

Definition at line 607 of file FMMMLayout.h.

int ogdf::FMMMLayout::minGraphSize ( ) const [inline]

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

Definition at line 604 of file FMMMLayout.h.

void ogdf::FMMMLayout::move_nodes	(	Graph &	G,
		NodeArray< NodeAttributes > &	A,
		NodeArray< DPoint > &	F
	)			`[private]`

Move the nodes.

void ogdf::FMMMLayout::newInitialPlacement ( bool nip ) [inline]

Sets the option newInitialPlacement to nip.

Definition at line 462 of file FMMMLayout.h.

bool ogdf::FMMMLayout::newInitialPlacement ( ) const [inline]

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.

Definition at line 459 of file FMMMLayout.h.

int ogdf::FMMMLayout::nmParticlesInLeaves ( ) const [inline]

Returns the current setting of option nmParticlesInLeaves.

Defines the maximal number of particles that are contained in a leaf of the reduced bucket quadtree.

Definition at line 915 of file FMMMLayout.h.

void ogdf::FMMMLayout::nmParticlesInLeaves ( int n ) [inline]

Sets the option nmParticlesInLeaves to n.

Definition at line 918 of file FMMMLayout.h.

int ogdf::FMMMLayout::nmPrecision ( ) const [inline]

Returns the precision p for the p-term multipole expansions.

Definition at line 921 of file FMMMLayout.h.

void ogdf::FMMMLayout::nmPrecision ( int p ) [inline]

Sets the precision for the multipole expansions to \ p.

Definition at line 924 of file FMMMLayout.h.

void ogdf::FMMMLayout::nmSmallCell ( SmallestCellFinding scf ) [inline]

Sets the option nmSmallCell to scf.

Definition at line 908 of file FMMMLayout.h.

SmallestCellFinding ogdf::FMMMLayout::nmSmallCell ( ) const [inline]

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:

scfIteratively: iteratively (in constant time)
scfAluru: by the formula by Aluru et al. (in constant time)

Definition at line 905 of file FMMMLayout.h.

ReducedTreeConstruction ogdf::FMMMLayout::nmTreeConstruction ( ) const [inline]

Returns the current setting of option nmTreeConstruction.

This option defines how the reduced bucket quadtree is constructed. Possible values:

rtcPathByPath: path by path construction
rtcSubtreeBySubtree: subtree by subtree construction

Definition at line 892 of file FMMMLayout.h.

void ogdf::FMMMLayout::nmTreeConstruction ( ReducedTreeConstruction rtc ) [inline]

Sets the option nmTreeConstruction to rtc.

Definition at line 895 of file FMMMLayout.h.

void ogdf::FMMMLayout::pack_subGraph_drawings	(	NodeArray< NodeAttributes > &	A,
		Graph	G_sub[],
		NodeArray< NodeAttributes >	A_sub[]
	)			`[private]`

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.

PageFormatType ogdf::FMMMLayout::pageFormat ( ) const [inline]

Returns the current setting of option pageFormat.

This option defines the desired aspect ratio of the drawing area.

pfPortrait: A4 page in portrait orientation
pfLandscape: A4 page in landscape orientation
pfSquare: square page format

Definition at line 442 of file FMMMLayout.h.

void ogdf::FMMMLayout::pageFormat ( PageFormatType t ) [inline]

Sets the option pageRatio to t.

Definition at line 445 of file FMMMLayout.h.

double ogdf::FMMMLayout::pageRatio ( ) const [inline]

Returns the current setting of option pageRatio.

This option defines the desired aspect ratio of the rectangular drawing area.

Definition at line 542 of file FMMMLayout.h.

void ogdf::FMMMLayout::pageRatio ( double r ) [inline]

Sets the option pageRatio to r.

Definition at line 545 of file FMMMLayout.h.

double ogdf::FMMMLayout::postSpringStrength ( ) const [inline]

Returns the strength of the springs in the postprocessing step.

Definition at line 856 of file FMMMLayout.h.

void ogdf::FMMMLayout::postSpringStrength ( double x ) [inline]

Sets the strength of the springs in the postprocessing step to x.

Definition at line 859 of file FMMMLayout.h.

void ogdf::FMMMLayout::postStrengthOfRepForces ( double x ) [inline]

Sets the strength of the repulsive forces in the postprocessing step to x.

Definition at line 865 of file FMMMLayout.h.

double ogdf::FMMMLayout::postStrengthOfRepForces ( ) const [inline]

Returns the strength of the repulsive forces in the postprocessing step.

Definition at line 862 of file FMMMLayout.h.

PreSort ogdf::FMMMLayout::presortCCs ( ) const [inline]

Returns the current setting of option presortCCs.

This option defines if the connected components are sorted before the packing algorithm is applied. Possible values:

psNone: no sorting
psDecreasingHeight: sorted by decreasing height
psDecreasingWidth: sorted by decreasing width

Definition at line 587 of file FMMMLayout.h.

void ogdf::FMMMLayout::presortCCs ( PreSort ps ) [inline]

Sets the option presortCCs to ps.

Definition at line 590 of file FMMMLayout.h.

void ogdf::FMMMLayout::prevent_oscilations	(	Graph &	G,
		NodeArray< DPoint > &	F,
		NodeArray< DPoint > &	last_node_movement,
		int	iter
	)			`[private]`

Depending on the direction of last_node_movement[v], the length of the next displacement of node v is restricted.

QualityVsSpeed ogdf::FMMMLayout::qualityVersusSpeed ( ) const [inline]

Returns the current setting of option qualityVersusSpeed.

Indicates if the algorithm is tuned either for best quality or best speed.

qvsGorgeousAndEfficient: gorgeous quality and efficient speed
qvsBeautifulAndFast: beautiful quality and fast speed
qvsNiceAndIncredibleSpeed: nice quality and incredible speed

Definition at line 471 of file FMMMLayout.h.

void ogdf::FMMMLayout::qualityVersusSpeed ( QualityVsSpeed qvs ) [inline]

Sets the option qualityVersusSpeed to qvs.

Definition at line 474 of file FMMMLayout.h.

void ogdf::FMMMLayout::randomTries ( int n ) [inline]

Sets the option randomTries to n.

Definition at line 632 of file FMMMLayout.h.

int ogdf::FMMMLayout::randomTries ( ) const [inline]

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

Definition at line 629 of file FMMMLayout.h.

int ogdf::FMMMLayout::randSeed ( ) const [inline]

Returns the seed of the random number generator.

Definition at line 488 of file FMMMLayout.h.

void ogdf::FMMMLayout::randSeed ( int p ) [inline]

Sets the seed of the random number generator.

Definition at line 485 of file FMMMLayout.h.

double ogdf::FMMMLayout::repForcesStrength ( ) const [inline]

Returns the strength of the repulsive forces.

Definition at line 702 of file FMMMLayout.h.

void ogdf::FMMMLayout::repForcesStrength ( double x ) [inline]

Sets the strength of the repulsive forces to x.

Definition at line 705 of file FMMMLayout.h.

RepulsiveForcesMethod ogdf::FMMMLayout::repulsiveForcesCalculation ( ) const [inline]

Returns the current setting of option repulsiveForcesCalculation.

This option defines how to calculate repulsive forces. Possible values:

rfcExact: exact calculation (slow)
rfcGridApproximation: grid approxiamtion (inaccurate)
rfcNMM: like in NMM (= New Multipole Method; fast and accurate)

Definition at line 715 of file FMMMLayout.h.

void ogdf::FMMMLayout::repulsiveForcesCalculation ( RepulsiveForcesMethod rfc ) [inline]

Sets the option repulsiveForcesCalculation to rfc.

Definition at line 720 of file FMMMLayout.h.

void ogdf::FMMMLayout::resizeDrawing ( bool b ) [inline]

Sets the option resizeDrawing to b.

Definition at line 812 of file FMMMLayout.h.

bool ogdf::FMMMLayout::resizeDrawing ( ) const [inline]

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().

Definition at line 809 of file FMMMLayout.h.

void ogdf::FMMMLayout::resizingScalar ( double s ) [inline]

Sets the option resizingScalar to s.

Definition at line 822 of file FMMMLayout.h.

double ogdf::FMMMLayout::resizingScalar ( ) const [inline]

Returns the current setting of option resizingScalar.

This option defines a parameter to scale the drawing if resizeDrawing() is true.

Definition at line 819 of file FMMMLayout.h.

void ogdf::FMMMLayout::restrict_force_to_comp_box ( DPoint & force ) [private]

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 ogdf::FMMMLayout::rotate_components_and_calculate_bounding_rectangles	(	List< Rectangle > &	R,
		Graph	G_sub[],
		NodeArray< NodeAttributes >	A_sub[]
	)			`[private]`

If number_of_components > 1, the subgraphs G_sub are rotated and skipped to find bounding rectangles with minimum area. The information is saved in R and the node positions in A_sub are updated. If number_of_components == 1 a rotation with minimal aspect ratio is found instead.

void ogdf::FMMMLayout::set_average_ideal_edgelength	(	Graph &	G,
		EdgeArray< EdgeAttributes > &	E
	)			`[private]`

The average_ideal_edgelength for all edges is computed.

void ogdf::FMMMLayout::set_radii	(	const Graph &	G,
		NodeArray< NodeAttributes > &	A
	)			`[private]`

The radii of the surrounding circles of the bounding boxes are computed.

void ogdf::FMMMLayout::springStrength ( double x ) [inline]

Sets the strength of the springs to x.

Definition at line 699 of file FMMMLayout.h.

double ogdf::FMMMLayout::springStrength ( ) const [inline]

Returns the strength of the springs.

Definition at line 696 of file FMMMLayout.h.

int ogdf::FMMMLayout::stepsForRotatingComponents ( ) const [inline]

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.

Definition at line 552 of file FMMMLayout.h.

void ogdf::FMMMLayout::stepsForRotatingComponents ( int n ) [inline]

Sets the option stepsForRotatingComponents to n.

Definition at line 555 of file FMMMLayout.h.

StopCriterion ogdf::FMMMLayout::stopCriterion ( ) const [inline]

Returns the stop criterion.

Possible values:

rscFixedIterations: stop if fixedIterations() is reached
rscThreshold: stop if threshold() is reached
rscFixedIterationsOrThreshold: stop if fixedIterations() or threshold() is reached

Definition at line 732 of file FMMMLayout.h.

void ogdf::FMMMLayout::stopCriterion ( StopCriterion rsc ) [inline]

Sets the stop criterion to rsc.

Definition at line 735 of file FMMMLayout.h.

void ogdf::FMMMLayout::threshold ( double x ) [inline]

Sets the threshold for the stop criterion to x.

Definition at line 745 of file FMMMLayout.h.

double ogdf::FMMMLayout::threshold ( ) const [inline]

Returns the threshold for the stop criterion.

(If the average absolute value of all forces in an iteration is less then threshold() then stop.)

Definition at line 742 of file FMMMLayout.h.

void ogdf::FMMMLayout::tipOverCCs ( TipOver to ) [inline]

Sets the option tipOverCCs to to.

Definition at line 570 of file FMMMLayout.h.

TipOver ogdf::FMMMLayout::tipOverCCs ( ) const [inline]

Returns the current setting of option tipOverCCs.

Defines in which case it is allowed to tip over drawings of connected components. Possible values:

toNone: not allowed at all
toNoGrowingRow: only if the height of the packing row does not grow
toAlways: always allowed

Definition at line 567 of file FMMMLayout.h.

void ogdf::FMMMLayout::unitEdgeLength ( double x ) [inline]

Sets the option unitEdgeLength to x.

Definition at line 451 of file FMMMLayout.h.

double ogdf::FMMMLayout::unitEdgeLength ( ) const [inline]

Returns the current setting of option unitEdgeLength.

Definition at line 448 of file FMMMLayout.h.

void ogdf::FMMMLayout::update_boxlength_and_cornercoordinate	(	Graph &	G,
		NodeArray< NodeAttributes > &	A
	)			`[private]`

Computes a new tight computational square-box.

(Guaranteeing, that all midpoints are inside the square.)

void ogdf::FMMMLayout::update_edgelength	(	List< edge > &	S,
		EdgeArray< double > &	new_edgelength,
		EdgeArray< EdgeAttributes > &	E_reduced
	)			`[private]`

Sets for each edge e of G_reduced in S its edgelength to new_edgelength[e].

Also stores this information in E_reduced.

void ogdf::FMMMLayout::update_low_level_options_due_to_high_level_options_settings ( ) [private]

Updates several low level parameter options due to the settings of the high level parameter options.

bool ogdf::FMMMLayout::useHighLevelOptions ( ) const [inline]

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.

Definition at line 430 of file FMMMLayout.h.

void ogdf::FMMMLayout::useHighLevelOptions ( bool uho ) [inline]

Sets the option useHighLevelOptions to uho.

Definition at line 433 of file FMMMLayout.h.

Member Data Documentation

double ogdf::FMMMLayout::average_ideal_edgelength [private]

Measured from center to center.

Definition at line 994 of file FMMMLayout.h.

double ogdf::FMMMLayout::boxlength [private]

Holds the length of the quadratic comput. box.

Definition at line 995 of file FMMMLayout.h.

double ogdf::FMMMLayout::cool_factor [private]

Needed for scaling the forces if coolTemperature is true.

Definition at line 993 of file FMMMLayout.h.

DPoint ogdf::FMMMLayout::down_left_corner [private]

Holds down left corner of the comput. box.

Definition at line 997 of file FMMMLayout.h.

FruchtermanReingold ogdf::FMMMLayout::FR [private]

Class for repulsive force calculation (Fruchterman, Reingold).

Definition at line 1001 of file FMMMLayout.h.

bool ogdf::FMMMLayout::m_adjustPostRepStrengthDynamically [private]

The option adjustPostRepStrengthDynamically.

Definition at line 980 of file FMMMLayout.h.

AllowedPositions ogdf::FMMMLayout::m_allowedPositions [private]

The option for allowed positions.

Definition at line 941 of file FMMMLayout.h.

bool ogdf::FMMMLayout::m_coolTemperature [private]

The option for how to scale forces.

Definition at line 971 of file FMMMLayout.h.

double ogdf::FMMMLayout::m_coolValue [private]

The value by which forces are decreased.

Definition at line 972 of file FMMMLayout.h.

EdgeLengthMeasurement ogdf::FMMMLayout::m_edgeLengthMeasurement [private]

The option for edge length measurement.

Definition at line 940 of file FMMMLayout.h.

double ogdf::FMMMLayout::m_fineTuneScalar [private]

Parameter for scaling forces during fine tuning.

Definition at line 979 of file FMMMLayout.h.

int ogdf::FMMMLayout::m_fineTuningIterations [private]

The number of iterations for fine tuning.

Definition at line 978 of file FMMMLayout.h.

int ogdf::FMMMLayout::m_fixedIterations [private]

The fixed number of iterations for the stop criterion.

Definition at line 969 of file FMMMLayout.h.

ForceModel ogdf::FMMMLayout::m_forceModel [private]

The used force model.

Definition at line 963 of file FMMMLayout.h.

double ogdf::FMMMLayout::m_forceScalingFactor [private]

The scaling factor for the forces.

Definition at line 970 of file FMMMLayout.h.

int ogdf::FMMMLayout::m_frGridQuotient [private]

The grid quotient.

Definition at line 985 of file FMMMLayout.h.

GalaxyChoice ogdf::FMMMLayout::m_galaxyChoice [private]

The selection of galaxy nodes.

Definition at line 953 of file FMMMLayout.h.

InitialPlacementForces ogdf::FMMMLayout::m_initialPlacementForces [private]

The option for how the initial placement is done.

Definition at line 973 of file FMMMLayout.h.

InitialPlacementMult ogdf::FMMMLayout::m_initialPlacementMult [private]

The option for creating initial placement.

Definition at line 960 of file FMMMLayout.h.

int ogdf::FMMMLayout::m_maxIntPosExponent [private]

The option for the used exponent.

Definition at line 942 of file FMMMLayout.h.

MaxIterChange ogdf::FMMMLayout::m_maxIterChange [private]

The option for how to change MaxIterations. If maxIterChange != micConstant, the iterations are decreased depending on the level, starting from ((maxIterFactor()-1) * fixedIterations())

Definition at line 955 of file FMMMLayout.h.

int ogdf::FMMMLayout::m_maxIterFactor [private]

The factor used for decreasing MaxIterations.

Definition at line 959 of file FMMMLayout.h.

double ogdf::FMMMLayout::m_minDistCC [private]

The separation between connected components.

Definition at line 948 of file FMMMLayout.h.

int ogdf::FMMMLayout::m_minGraphSize [private]

The option for minimal graph size.

Definition at line 952 of file FMMMLayout.h.

bool ogdf::FMMMLayout::m_newInitialPlacement [private]

The option for new initial placement.