Package org.jgrapht.alg.drawing

Class IndexedFRLayoutAlgorithm2D<V,E>

java.lang.Object

org.jgrapht.alg.drawing.FRLayoutAlgorithm2D<V,E>

org.jgrapht.alg.drawing.IndexedFRLayoutAlgorithm2D<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

LayoutAlgorithm2D<V,E>

public class IndexedFRLayoutAlgorithm2D<V,E>
extends FRLayoutAlgorithm2D<V,E>

Fruchterman and Reingold Force-Directed Placement Algorithm using the Barnes-Hut indexing technique with a QuadTree. The Barnes-Hut indexing technique is described in the following paper:

• J. Barnes and P. Hut. A hierarchical O(N log N) force-calculation algorithm. Nature. 324(4):446--449, 1986.

Author:

Dimitrios Michail

Nested Class Summary

Nested classes/interfaces inherited from class org.jgrapht.alg.drawing.FRLayoutAlgorithm2D

FRLayoutAlgorithm2D.InverseLinearTemperatureModel, FRLayoutAlgorithm2D.TemperatureModel

Field Summary

Fields

Modifier and Type	Field	Description
protected ToleranceDoubleComparator	comparator
static double	DEFAULT_THETA_FACTOR	Default $\theta$ value for approximation using the Barnes-Hut technique
protected Function<V,Point2D>	initializer	A model initializer
protected long	savedComparisons
protected double	theta

Fields inherited from class org.jgrapht.alg.drawing.FRLayoutAlgorithm2D

DEFAULT_ITERATIONS, DEFAULT_NORMALIZATION_FACTOR, iterations, normalizationFactor, optimalDistance, rng, temperatureModelSupplier

Constructor Summary

Constructors

Constructor	Description
IndexedFRLayoutAlgorithm2D()	Create a new layout algorithm
IndexedFRLayoutAlgorithm2D(int iterations, double theta)	Create a new layout algorithm
IndexedFRLayoutAlgorithm2D(int iterations, double theta, double normalizationFactor)	Create a new layout algorithm
IndexedFRLayoutAlgorithm2D(int iterations, double theta, double normalizationFactor, Random rng)	Create a new layout algorithm
IndexedFRLayoutAlgorithm2D(int iterations, double theta, double normalizationFactor, Random rng, double tolerance)	Create a new layout algorithm

Method Summary

Modifier and Type	Method	Description
protected Map<V,Point2D>	calculateRepulsiveForces(Graph<V,E> graph, LayoutModel2D<V> model)	Calculate the repulsive forces between vertices
Function<V,Point2D>	getInitializer()	Get the initializer
long	getSavedComparisons()	Get the total number of saved comparisons due to the Barnes-Hut technique.
protected void	init(Graph<V,E> graph, LayoutModel2D<V> model)	Initialize a model using the initializer.
void	layout(Graph<V,E> graph, LayoutModel2D<V> model)	Layout a graph.
void	setInitializer(Function<V,Point2D> initializer)	Set the initializer

Methods inherited from class org.jgrapht.alg.drawing.FRLayoutAlgorithm2D

attractiveForce, calculateAttractiveForces, repulsiveForce

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFAULT_THETA_FACTOR

public static final double DEFAULT_THETA_FACTOR

Default $\theta$ value for approximation using the Barnes-Hut technique

See Also:

Constant Field Values

theta

protected double theta

savedComparisons

protected long savedComparisons

comparator

protected ToleranceDoubleComparator comparator

initializer

protected Function<V,Point2D> initializer

A model initializer

Constructor Detail

IndexedFRLayoutAlgorithm2D

public IndexedFRLayoutAlgorithm2D()

Create a new layout algorithm

IndexedFRLayoutAlgorithm2D

public IndexedFRLayoutAlgorithm2D(int iterations,
                                  double theta)

Create a new layout algorithm

Parameters:

iterations - number of iterations

theta - parameter for approximation using the Barnes-Hut technique

IndexedFRLayoutAlgorithm2D

public IndexedFRLayoutAlgorithm2D(int iterations,
                                  double theta,
                                  double normalizationFactor)

Create a new layout algorithm

Parameters:

iterations - number of iterations

theta - parameter for approximation using the Barnes-Hut technique

normalizationFactor - normalization factor for the optimal distance

IndexedFRLayoutAlgorithm2D

public IndexedFRLayoutAlgorithm2D(int iterations,
                                  double theta,
                                  double normalizationFactor,
                                  Random rng)

Create a new layout algorithm

Parameters:

iterations - number of iterations

theta - theta parameter for the Barnes-Hut approximation

normalizationFactor - normalization factor for the optimal distance

rng - the random number generator

IndexedFRLayoutAlgorithm2D

public IndexedFRLayoutAlgorithm2D(int iterations,
                                  double theta,
                                  double normalizationFactor,
                                  Random rng,
                                  double tolerance)

Create a new layout algorithm

Parameters:

iterations - number of iterations

theta - theta parameter for the Barnes-Hut approximation

normalizationFactor - normalization factor for the optimal distance

rng - the random number generator

tolerance - tolerance used when comparing floating point values

Method Detail

layout

public void layout(Graph<V,E> graph,
                   LayoutModel2D<V> model)

Description copied from interface: LayoutAlgorithm2D

Layout a graph.

Specified by:

layout in interface LayoutAlgorithm2D<V,E>

Overrides:

layout in class FRLayoutAlgorithm2D<V,E>

Parameters:

graph - the graph

model - the layout model to use

calculateRepulsiveForces

protected Map<V,Point2D> calculateRepulsiveForces(Graph<V,E> graph,
                                                        LayoutModel2D<V> model)

Description copied from class: FRLayoutAlgorithm2D

Calculate the repulsive forces between vertices

Overrides:

calculateRepulsiveForces in class FRLayoutAlgorithm2D<V,E>

Parameters:

graph - the graph

model - the model

Returns:

the displacement per vertex due to the repulsive forces

getSavedComparisons

public long getSavedComparisons()

Get the total number of saved comparisons due to the Barnes-Hut technique.

Returns:

the total number of saved comparisons

getInitializer

public Function<V,Point2D> getInitializer()

Get the initializer

Returns:

the initializer

setInitializer

public void setInitializer(Function<V,Point2D> initializer)

Set the initializer

Parameters:

initializer - the initializer

init

protected void init(Graph<V,E> graph,
                    LayoutModel2D<V> model)

Initialize a model using the initializer.

Parameters:

graph - the graph

model - the model