org.graphstream.ui.layout.springbox

Class BarnesHutLayout

java.lang.Object

org.graphstream.stream.SourceBase

org.graphstream.ui.layout.springbox.BarnesHutLayout

All Implemented Interfaces:

AttributeSink, ElementSink, Pipe, Sink, Source, Layout

Direct Known Subclasses:

LinLog, SpringBox

public abstract class BarnesHutLayout
extends SourceBase
implements Layout

Base implementation of a Barnes-Hut space decomposition and particle interaction algorithm to be used for force-based layout algorithms.

This base class creates the space decomposition method and manages the main loop of the simulation. The simulation is made of NodeParticle and EdgeSpring elements that are created and linked for you in response to graph events received via the Sink interface. However you have to provide an implementation of the abstract NodeParticle class (by overriding the abstract method newNodeParticle(String)).

As almost all the repulsion/attraction forces computation is done in the NodeParticle class, this is the most important one.

This algorithm can be configured using several attributes put on the graph :

• layout.force : a floating point number (default 0.5f), that allows to define the importance of movement of each node at each computation step. The larger the value the quicker nodes move to their position of lowest energy. However too high values can generate non stable layouts and oscillations.
• layout.quality : an integer between 0 and 4. With value 0 the layout is faster but it also can be farther from equilibrium. With value 4 the algorithm tries to be as close as possible from equilibrium (the n-tree and Barnes-Hut algorithms are disabled), but the computation can take a lot of time (the algorithm becomes O(n^2)). TODO change this into layout.barneshut or something similar.

You can also put the following attributes on nodes :

• layout.weight : The force of repulsion of a node. The larger the value, the more the node repulses its neighbors.

And on edges :

• layout.weight : the multiplier for the desired edge length. By default the algorithm tries to make each edge of length one. This is the position of lowest energy for a spring. This coefficient allows to modify this target spring length. Value larger than one will make the edge longer. Values between 0 and 1 will make the edge smaller.
• layout.stabilization-limit : the stabilization of a layout is a number between 0 and 1. 1 means fully stable, but this value is rare. Therefore one can consider the layout stable at a lower value. The default is 0.9. You can fix it with this attribute.

Nested Class Summary

Nested classes/interfaces inherited from class org.graphstream.stream.SourceBase

SourceBase.ElementType

Constructor Summary

Constructors

Constructor and Description
BarnesHutLayout() New 2D Barnes-Hut simulation.
BarnesHutLayout(boolean is3D) New Barnes-Hut simulation.
BarnesHutLayout(boolean is3D, java.util.Random randomNumberGenerator) New Barnes-Hut simulation.

Method Summary

Modifier and Type	Method and Description
void	clear() Clears the whole nodes and edges structures
void	compute() Method to call repeatedly to compute the layout.
void	edgeAdded(java.lang.String graphId, long time, java.lang.String edgeId, java.lang.String fromNodeId, java.lang.String toNodeId, boolean directed) An edge was inserted in graph.
void	edgeAttributeAdded(java.lang.String graphId, long time, java.lang.String edgeId, java.lang.String attribute, java.lang.Object value) A edge attribute was added.
void	edgeAttributeChanged(java.lang.String graphId, long time, java.lang.String edgeId, java.lang.String attribute, java.lang.Object oldValue, java.lang.Object newValue) A edge attribute was changed.
void	edgeAttributeRemoved(java.lang.String graphId, long time, java.lang.String edgeId, java.lang.String attribute) A edge attribute was removed.
void	edgeRemoved(java.lang.String graphId, long time, java.lang.String edgeId) An edge of graph was removed.The nodes the edge connects may already have been removed from the graph.
void	freezeNode(java.lang.String id, boolean on) Freeze or un-freeze a node.
double	getBarnesHutTheta() The Barnes-Hut theta value used to know if we use a pole or not.
Point3	getCenterPoint()
Energies	getEnergies()
double	getForce() The current layout force.
double	getGravityFactor() A gravity factor that attracts all nodes to the center of the layout to avoid flying components.
Point3	getHiPoint() Largest point in space of the layout bounding box.
long	getLastStepTime() Time in nanoseconds used by the last call to step().
abstract java.lang.String	getLayoutAlgorithmName() Name of the layout algorithm.
Point3	getLowPoint() Smallest point in space of the layout bounding box.
int	getNodeMovedCount() How many nodes moved during the last step?.
double	getQuality() The current layout algorithm quality.
java.util.Random	getRandom()
ParticleBox	getSpatialIndex() The spatial index as a n-tree.
double	getStabilization() Estimate of how close to stabilization the layout algorithm is.
double	getStabilizationLimit() Above which value a correct stabilization is achieved?
int	getSteps() Number of calls made to step() so far.
double	getViewZone()
void	graphAttributeAdded(java.lang.String graphId, long time, java.lang.String attribute, java.lang.Object value) A graph attribute was added.
void	graphAttributeChanged(java.lang.String graphId, long time, java.lang.String attribute, java.lang.Object oldValue, java.lang.Object newValue) A graph attribute was changed.
void	graphAttributeRemoved(java.lang.String graphId, long time, java.lang.String attribute) A graph attribute was removed.
void	graphCleared(java.lang.String graphId, long time) The whole graph was cleared.
boolean	is3D()
void	moveNode(java.lang.String id, double x, double y, double z) Move a node by force to a new location.
abstract NodeParticle	newNodeParticle(java.lang.String id) Factory method to create node particles.
void	nodeAdded(java.lang.String graphId, long time, java.lang.String nodeId) A node was inserted in the given graph.
void	nodeAttributeAdded(java.lang.String graphId, long time, java.lang.String nodeId, java.lang.String attribute, java.lang.Object value) A node attribute was added.
void	nodeAttributeChanged(java.lang.String graphId, long time, java.lang.String nodeId, java.lang.String attribute, java.lang.Object oldValue, java.lang.Object newValue) A node attribute was changed.
void	nodeAttributeRemoved(java.lang.String graphId, long time, java.lang.String nodeId, java.lang.String attribute) A node attribute was removed.
void	nodeRemoved(java.lang.String graphId, long time, java.lang.String nodeId) A node was removed from the graph.
void	particleAdded(java.lang.Object id, double x, double y, double z)
void	particleAdded(java.lang.Object id, double x, double y, double z, java.lang.Object mark)
void	particleAttributeChanged(java.lang.Object id, java.lang.String attribute, java.lang.Object newValue, boolean removed)
void	particleMarked(java.lang.Object id, java.lang.Object mark)
void	particleMoved(java.lang.Object id, double x, double y, double z)
void	particleRemoved(java.lang.Object id)
double	randomXInsideBounds()
double	randomYInsideBounds()
double	randomZInsideBounds()
void	setBarnesHutTheta(double theta) Change the barnes-hut theta parameter allowing to know if we use a pole or not.
void	setForce(double value) The general "speed" of the algorithm.
void	setGravityFactor(double value) Set the gravity factor that attracts all nodes to the center of the layout to avoid flying components.
void	setQuality(double qualityLevel) Set the overall quality level, a number between 0 and 1 with 1 the highest quality available, but often with a slower computation.
void	setSendNodeInfos(boolean on) If true, node informations messages are sent for every node.
void	setStabilizationLimit(double value) Change the stabilization limit for this layout algorithm.
void	shake() Add a random vector whose length is 10% of the size of the graph to all node positions.
void	stepBegins(java.lang.String graphId, long time, double step) Since dynamic graphs are based on discrete event modifications, the notion of step is defined to simulate elapsed time between events.
void	stepFinished(int time)

Methods inherited from class org.graphstream.stream.SourceBase

addAttributeSink, addElementSink, addSink, attributeSinks, clearAttributeSinks, clearElementSinks, clearSinks, elementSinks, removeAttributeSink, removeElementSink, removeSink, sendAttributeChangedEvent, sendAttributeChangedEvent, sendEdgeAdded, sendEdgeAdded, sendEdgeAttributeAdded, sendEdgeAttributeAdded, sendEdgeAttributeChanged, sendEdgeAttributeChanged, sendEdgeAttributeRemoved, sendEdgeAttributeRemoved, sendEdgeRemoved, sendEdgeRemoved, sendGraphAttributeAdded, sendGraphAttributeAdded, sendGraphAttributeChanged, sendGraphAttributeChanged, sendGraphAttributeRemoved, sendGraphAttributeRemoved, sendGraphCleared, sendGraphCleared, sendNodeAdded, sendNodeAdded, sendNodeAttributeAdded, sendNodeAttributeAdded, sendNodeAttributeChanged, sendNodeAttributeChanged, sendNodeAttributeRemoved, sendNodeAttributeRemoved, sendNodeRemoved, sendNodeRemoved, sendStepBegins, sendStepBegins

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.graphstream.stream.Source

addAttributeSink, addElementSink, addSink, clearAttributeSinks, clearElementSinks, clearSinks, removeAttributeSink, removeElementSink, removeSink

Constructor Detail

BarnesHutLayout

public BarnesHutLayout()

New 2D Barnes-Hut simulation.

BarnesHutLayout

public BarnesHutLayout(boolean is3D)

New Barnes-Hut simulation.

Parameters:

is3D - If true the simulation dimensions count is 3 else 2.

BarnesHutLayout

public BarnesHutLayout(boolean is3D,
                       java.util.Random randomNumberGenerator)

New Barnes-Hut simulation.

Parameters:

is3D - If true the simulation dimensions count is 3 else 2.

randomNumberGenerator - The random number generator to use.

Method Detail

getLowPoint

public Point3 getLowPoint()

Description copied from interface: Layout

Smallest point in space of the layout bounding box.

Specified by:

getLowPoint in interface Layout

getHiPoint

public Point3 getHiPoint()

Description copied from interface: Layout

Largest point in space of the layout bounding box.

Specified by:

getHiPoint in interface Layout

randomXInsideBounds

public double randomXInsideBounds()

randomYInsideBounds

public double randomYInsideBounds()

randomZInsideBounds

public double randomZInsideBounds()

getCenterPoint

public Point3 getCenterPoint()

getGravityFactor

public double getGravityFactor()

A gravity factor that attracts all nodes to the center of the layout to avoid flying components. If set to zero, the gravity computation is disabled.

Returns:

The gravity factor, usually between 0 and 1.

setGravityFactor

public void setGravityFactor(double value)

Set the gravity factor that attracts all nodes to the center of the layout to avoid flying components. If set to zero, the gravity computation is disabled.

Parameters:

value - The new gravity factor, usually between 0 and 1.

getSpatialIndex

public ParticleBox getSpatialIndex()

The spatial index as a n-tree.

Returns:

The n-tree.

getLastStepTime

public long getLastStepTime()

Description copied from interface: Layout

Time in nanoseconds used by the last call to step().

Specified by:

getLastStepTime in interface Layout

getLayoutAlgorithmName

public abstract java.lang.String getLayoutAlgorithmName()

Description copied from interface: Layout

Name of the layout algorithm.

Specified by:

getLayoutAlgorithmName in interface Layout

getNodeMovedCount

public int getNodeMovedCount()

Description copied from interface: Layout

How many nodes moved during the last step?. When this method returns zero, the layout stabilized.

Specified by:

getNodeMovedCount in interface Layout

getStabilization

public double getStabilization()

Description copied from interface: Layout

Estimate of how close to stabilization the layout algorithm is.

Specified by:

getStabilization in interface Layout

Returns:

a value between 0 and 1. 1 means fully stabilized.

getStabilizationLimit

public double getStabilizationLimit()

Description copied from interface: Layout

Above which value a correct stabilization is achieved?

Specified by:

getStabilizationLimit in interface Layout

Returns:

The stabilization limit.

getSteps

public int getSteps()

Description copied from interface: Layout

Number of calls made to step() so far.

Specified by:

getSteps in interface Layout

getQuality

public double getQuality()

Description copied from interface: Layout

The current layout algorithm quality. A number between 0 and 1 with 1 the highest (but probably slowest) quality.

Specified by:

getQuality in interface Layout

Returns:

A number between 0 and 1.

is3D

public boolean is3D()

getForce

public double getForce()

Description copied from interface: Layout

The current layout force.

Specified by:

getForce in interface Layout

Returns:

A real number.

getRandom

public java.util.Random getRandom()

getEnergies

public Energies getEnergies()

getBarnesHutTheta

public double getBarnesHutTheta()

The Barnes-Hut theta value used to know if we use a pole or not.

Returns:

The theta value (between 0 and 1).

getViewZone

public double getViewZone()

setSendNodeInfos

public void setSendNodeInfos(boolean on)

Description copied from interface: Layout

If true, node informations messages are sent for every node. This is mainly for debugging and slows down the process a lot. The contents of the node information is specific to the algorithm, and sent via a specific "layout.info" attribute.

Specified by:

setSendNodeInfos in interface Layout

Parameters:

on - If true, send node informations to a "layout.info" attribute.

setBarnesHutTheta

public void setBarnesHutTheta(double theta)

Change the barnes-hut theta parameter allowing to know if we use a pole or not.

Parameters:

theta - The new value for theta (between 0 and 1).

setForce

public void setForce(double value)

Description copied from interface: Layout

The general "speed" of the algorithm. For some algorithm this will have no effect. For most "dynamic" algorithms, this change the way iterations toward stabilization are done.

Specified by:

setForce in interface Layout

Parameters:

value - A number in [0..1].

setStabilizationLimit

public void setStabilizationLimit(double value)

Description copied from interface: Layout

Change the stabilization limit for this layout algorithm.

The stabilization is a number between 0 and 1 that indicates how close to stabilization (no nodes need to move) the layout is. The value 1 means the layout is fully stabilized. Naturally this is often only an indication only, for some algorithms, it is difficult to determine if the layout is correct or acceptable enough. You can get the actual stabilization limit using Layout.getStabilizationLimit(). You can get the actual stabilization using Layout.getStabilization().

Be careful, most layout classes do not use the stabilization limit, this number is mostly used the process that control the layout, like the LayoutRunner for example. The stabilization limit is only an indication with a default set for each layout algorithm. However this default can be changed using this method, or by storing on the graph an attribute "layout.stabilization-limit" (or "layout.stabilisation-limit").

The convention is that the value 0 means that the process controlling the layout will not stop the layout (will therefore not consider the stabilization limit). In other words the layout will compute endlessly.

Specified by:

setStabilizationLimit in interface Layout

Parameters:

value - The new stabilization limit, 0 means no need to stabilize. Else a value larger than zero or equal to 1 is accepted.

setQuality

public void setQuality(double qualityLevel)

Description copied from interface: Layout

Set the overall quality level, a number between 0 and 1 with 1 the highest quality available, but often with a slower computation.

Specified by:

setQuality in interface Layout

Parameters:

qualityLevel - The quality level, a number between 0 and 1.

clear

public void clear()

Description copied from interface: Layout

Clears the whole nodes and edges structures

Specified by:

clear in interface Layout

compute

public void compute()

Description copied from interface: Layout

Method to call repeatedly to compute the layout.

This method implements the layout algorithm proper. It must be called in a loop, until the layout stabilizes. You can know if the layout is stable by using the Layout.getNodeMovedCount() method that returns the number of node that have moved during the last call to step().

The listener is called by this method, therefore each call to step() will also trigger layout events, allowing to reproduce the layout process graphically for example. You can insert the listener only when the layout stabilized, and then call step() anew if you do not want to observe the layout process.

Specified by:

compute in interface Layout

shake

public void shake()

Description copied from interface: Layout

Add a random vector whose length is 10% of the size of the graph to all node positions.

Specified by:

shake in interface Layout

moveNode

public void moveNode(java.lang.String id,
                     double x,
                     double y,
                     double z)

Description copied from interface: Layout

Move a node by force to a new location. It is preferable to first freeze the node before moving it by force, and then un-freeze it.

Specified by:

moveNode in interface Layout

Parameters:

id - The node identifier.

x - The node new X.

y - The node new Y.

z - The node new Z.

freezeNode

public void freezeNode(java.lang.String id,
                       boolean on)

Description copied from interface: Layout

Freeze or un-freeze a node. The freezed node position will not be changed by the algorithm until un-freezed.

Specified by:

freezeNode in interface Layout

Parameters:

id - The node identifier.

on - If true the node is frozen.

particleAdded

public void particleAdded(java.lang.Object id,
                          double x,
                          double y,
                          double z,
                          java.lang.Object mark)

particleAdded

public void particleAdded(java.lang.Object id,
                          double x,
                          double y,
                          double z)

particleMarked

public void particleMarked(java.lang.Object id,
                           java.lang.Object mark)

particleMoved

public void particleMoved(java.lang.Object id,
                          double x,
                          double y,
                          double z)

particleRemoved

public void particleRemoved(java.lang.Object id)

stepFinished

public void stepFinished(int time)

particleAttributeChanged

public void particleAttributeChanged(java.lang.Object id,
                                     java.lang.String attribute,
                                     java.lang.Object newValue,
                                     boolean removed)

edgeAdded

public void edgeAdded(java.lang.String graphId,
                      long time,
                      java.lang.String edgeId,
                      java.lang.String fromNodeId,
                      java.lang.String toNodeId,
                      boolean directed)

Description copied from interface: ElementSink

An edge was inserted in graph.

Specified by:

edgeAdded in interface ElementSink

Parameters:

graphId - Identifier of the graph where the edge was added.

edgeId - Identifier of the added edge.

fromNodeId - Identifier of the first node of the edge.

toNodeId - Identifier of the second node of the edge.

directed - If true, the edge is directed.

nodeAdded

public void nodeAdded(java.lang.String graphId,
                      long time,
                      java.lang.String nodeId)

Description copied from interface: ElementSink

A node was inserted in the given graph.

Specified by:

nodeAdded in interface ElementSink

Parameters:

graphId - Identifier of the graph where the node was added.

nodeId - Identifier of the added node.

edgeRemoved

public void edgeRemoved(java.lang.String graphId,
                        long time,
                        java.lang.String edgeId)

Description copied from interface: ElementSink

An edge of graph was removed.The nodes the edge connects may already have been removed from the graph.

Specified by:

edgeRemoved in interface ElementSink

Parameters:

graphId - The graph where the edge will be removed.

edgeId - The edge that will be removed.

nodeRemoved

public void nodeRemoved(java.lang.String graphId,
                        long time,
                        java.lang.String nodeId)

Description copied from interface: ElementSink

A node was removed from the graph.

Specified by:

nodeRemoved in interface ElementSink

Parameters:

graphId - Identifier of the graph where the node will be removed.

nodeId - Identifier of the removed node.

graphCleared

public void graphCleared(java.lang.String graphId,
                         long time)

Description copied from interface: ElementSink

The whole graph was cleared. All the nodes, edges and attributes of the graph are removed.

Specified by:

graphCleared in interface ElementSink

Parameters:

graphId - The graph cleared.

stepBegins

public void stepBegins(java.lang.String graphId,
                       long time,
                       double step)

Description copied from interface: ElementSink

Since dynamic graphs are based on discrete event modifications, the notion of step is defined to simulate elapsed time between events. So a step is a event that occurs in the graph, it does not modify it but it gives a kind of timestamp that allow the tracking of the progress of the graph over the time.

This kind of event is useful for dynamic algorithms that listen to the dynamic graph and need to measure the time in the graph's evolution.

Specified by:

stepBegins in interface ElementSink

Parameters:

graphId - Identifier of the graph where the step starts.

time - A numerical value that may give a timestamp to track the evolution of the graph over the time.

graphAttributeAdded

public void graphAttributeAdded(java.lang.String graphId,
                                long time,
                                java.lang.String attribute,
                                java.lang.Object value)

Description copied from interface: AttributeSink

A graph attribute was added.

Specified by:

graphAttributeAdded in interface AttributeSink

Parameters:

graphId - Identifier of the graph where the attribute changed.

attribute - The attribute name.

value - The attribute new value.

graphAttributeChanged

public void graphAttributeChanged(java.lang.String graphId,
                                  long time,
                                  java.lang.String attribute,
                                  java.lang.Object oldValue,
                                  java.lang.Object newValue)

Description copied from interface: AttributeSink

A graph attribute was changed.

Specified by:

graphAttributeChanged in interface AttributeSink

Parameters:

graphId - Identifier of the graph where the attribute changed.

attribute - The attribute name.

oldValue - The attribute old value.

newValue - The attribute new value.

graphAttributeRemoved

public void graphAttributeRemoved(java.lang.String graphId,
                                  long time,
                                  java.lang.String attribute)

Description copied from interface: AttributeSink

A graph attribute was removed.

Specified by:

graphAttributeRemoved in interface AttributeSink

Parameters:

graphId - Identifier of the graph where the attribute was removed.

attribute - The removed attribute name.

nodeAttributeAdded

public void nodeAttributeAdded(java.lang.String graphId,
                               long time,
                               java.lang.String nodeId,
                               java.lang.String attribute,
                               java.lang.Object value)

Description copied from interface: AttributeSink

A node attribute was added.

Specified by:

nodeAttributeAdded in interface AttributeSink

Parameters:

graphId - Identifier of the graph where the change occurred.

nodeId - Identifier of the node whose attribute changed.

attribute - The attribute name.

value - The attribute new value.

nodeAttributeChanged

public void nodeAttributeChanged(java.lang.String graphId,
                                 long time,
                                 java.lang.String nodeId,
                                 java.lang.String attribute,
                                 java.lang.Object oldValue,
                                 java.lang.Object newValue)

Description copied from interface: AttributeSink

A node attribute was changed.

Specified by:

nodeAttributeChanged in interface AttributeSink

Parameters:

graphId - Identifier of the graph where the change occurred.

nodeId - Identifier of the node whose attribute changed.

attribute - The attribute name.

oldValue - The attribute old value.

newValue - The attribute new value.

nodeAttributeRemoved

public void nodeAttributeRemoved(java.lang.String graphId,
                                 long time,
                                 java.lang.String nodeId,
                                 java.lang.String attribute)

Description copied from interface: AttributeSink

A node attribute was removed.

Specified by:

nodeAttributeRemoved in interface AttributeSink

Parameters:

graphId - Identifier of the graph where the attribute was removed.

nodeId - Identifier of the node whose attribute was removed.

attribute - The removed attribute name.

edgeAttributeAdded

public void edgeAttributeAdded(java.lang.String graphId,
                               long time,
                               java.lang.String edgeId,
                               java.lang.String attribute,
                               java.lang.Object value)

Description copied from interface: AttributeSink

A edge attribute was added.

Specified by:

edgeAttributeAdded in interface AttributeSink

Parameters:

graphId - Identifier of the graph where the change occurred.

edgeId - Identifier of the edge whose attribute changed.

attribute - The attribute name.

value - The attribute new value.

edgeAttributeChanged

public void edgeAttributeChanged(java.lang.String graphId,
                                 long time,
                                 java.lang.String edgeId,
                                 java.lang.String attribute,
                                 java.lang.Object oldValue,
                                 java.lang.Object newValue)

Description copied from interface: AttributeSink

A edge attribute was changed.

Specified by:

edgeAttributeChanged in interface AttributeSink

Parameters:

graphId - Identifier of the graph where the change occurred.

edgeId - Identifier of the edge whose attribute changed.

attribute - The attribute name.

oldValue - The attribute old value.

newValue - The attribute new value.

edgeAttributeRemoved

public void edgeAttributeRemoved(java.lang.String graphId,
                                 long time,
                                 java.lang.String edgeId,
                                 java.lang.String attribute)

Description copied from interface: AttributeSink

A edge attribute was removed.

Specified by:

edgeAttributeRemoved in interface AttributeSink

Parameters:

graphId - Identifier of the graph where the attribute was removed.

edgeId - Identifier of the edge whose attribute was removed.

attribute - The removed attribute name.

newNodeParticle

public abstract NodeParticle newNodeParticle(java.lang.String id)

Factory method to create node particles.

Parameters:

id - The identifier of the new node/particle.

Returns:

The new node/particle.