org.graphstream.ui.layout.springbox
Class BarnesHutLayout

java.lang.Object
  extended by org.graphstream.stream.SourceBase
      extended by org.graphstream.ui.layout.springbox.BarnesHutLayout
All Implemented Interfaces:
AttributeSink, ElementSink, Pipe, Sink, Source, Layout, org.miv.pherd.ParticleBoxListener
Direct Known Subclasses:
LinLog, SpringBox

public abstract class BarnesHutLayout
extends SourceBase
implements Layout, org.miv.pherd.ParticleBoxListener

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 :

You can also put the following attributes on nodes : And on edges :


Nested Class Summary
 
Nested classes/interfaces inherited from class org.graphstream.stream.SourceBase
SourceBase.ElementType
 
Constructor Summary
BarnesHutLayout()
          New 2D Barnes-Hut simulation.
BarnesHutLayout(boolean is3D)
          New Barnes-Hut simulation.
BarnesHutLayout(boolean is3D, Random randomNumberGenerator)
          New Barnes-Hut simulation.
 
Method Summary
 void clear()
          Clears the whole nodes and edges structures
 void compute()
          Method to call repeatedly to compute the layout.
 void edgeAdded(String graphId, long time, String edgeId, String fromNodeId, String toNodeId, boolean directed)
          An edge was inserted in graph.
 void edgeAttributeAdded(String graphId, long time, String edgeId, String attribute, Object value)
          A edge attribute was added.
 void edgeAttributeChanged(String graphId, long time, String edgeId, String attribute, Object oldValue, Object newValue)
          A edge attribute was changed.
 void edgeAttributeRemoved(String graphId, long time, String edgeId, String attribute)
          A edge attribute was removed.
 void edgeRemoved(String graphId, long time, String edgeId)
          An edge of graph was removed.The nodes the edge connects may already have been removed from the graph.
 void freezeNode(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  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.
 Random getRandom()
           
 org.miv.pherd.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(String graphId, long time, String attribute, Object value)
          A graph attribute was added.
 void graphAttributeChanged(String graphId, long time, String attribute, Object oldValue, Object newValue)
          A graph attribute was changed.
 void graphAttributeRemoved(String graphId, long time, String attribute)
          A graph attribute was removed.
 void graphCleared(String graphId, long time)
          The whole graph was cleared.
 boolean is3D()
           
 void moveNode(String id, double x, double y, double z)
          Move a node by force to a new location.
abstract  NodeParticle newNodeParticle(String id)
          Factory method to create node particles.
 void nodeAdded(String graphId, long time, String nodeId)
          A node was inserted in the given graph.
 void nodeAttributeAdded(String graphId, long time, String nodeId, String attribute, Object value)
          A node attribute was added.
 void nodeAttributeChanged(String graphId, long time, String nodeId, String attribute, Object oldValue, Object newValue)
          A node attribute was changed.
 void nodeAttributeRemoved(String graphId, long time, String nodeId, String attribute)
          A node attribute was removed.
 void nodeRemoved(String graphId, long time, String nodeId)
          A node was removed from the graph.
 void particleAdded(Object id, double x, double y, double z)
           
 void particleAdded(Object id, double x, double y, double z, Object mark)
           
 void particleAttributeChanged(Object id, String attribute, Object newValue, boolean removed)
           
 void particleMarked(Object id, Object mark)
           
 void particleMoved(Object id, double x, double y, double z)
           
 void particleRemoved(Object id)
           
 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(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,
                       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

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 org.miv.pherd.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 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 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(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(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(Object id,
                          double x,
                          double y,
                          double z,
                          Object mark)

particleAdded

public void particleAdded(Object id,
                          double x,
                          double y,
                          double z)
Specified by:
particleAdded in interface org.miv.pherd.ParticleBoxListener

particleMarked

public void particleMarked(Object id,
                           Object mark)

particleMoved

public void particleMoved(Object id,
                          double x,
                          double y,
                          double z)
Specified by:
particleMoved in interface org.miv.pherd.ParticleBoxListener

particleRemoved

public void particleRemoved(Object id)
Specified by:
particleRemoved in interface org.miv.pherd.ParticleBoxListener

stepFinished

public void stepFinished(int time)
Specified by:
stepFinished in interface org.miv.pherd.ParticleBoxListener

particleAttributeChanged

public void particleAttributeChanged(Object id,
                                     String attribute,
                                     Object newValue,
                                     boolean removed)
Specified by:
particleAttributeChanged in interface org.miv.pherd.ParticleBoxListener

edgeAdded

public void edgeAdded(String graphId,
                      long time,
                      String edgeId,
                      String fromNodeId,
                      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(String graphId,
                      long time,
                      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(String graphId,
                        long time,
                        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(String graphId,
                        long time,
                        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(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(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(String graphId,
                                long time,
                                String attribute,
                                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(String graphId,
                                  long time,
                                  String attribute,
                                  Object oldValue,
                                  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(String graphId,
                                  long time,
                                  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(String graphId,
                               long time,
                               String nodeId,
                               String attribute,
                               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(String graphId,
                                 long time,
                                 String nodeId,
                                 String attribute,
                                 Object oldValue,
                                 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(String graphId,
                                 long time,
                                 String nodeId,
                                 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(String graphId,
                               long time,
                               String edgeId,
                               String attribute,
                               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(String graphId,
                                 long time,
                                 String edgeId,
                                 String attribute,
                                 Object oldValue,
                                 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(String graphId,
                                 long time,
                                 String edgeId,
                                 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(String id)
Factory method to create node particles.

Parameters:
id - The identifier of the new node/particle.
Returns:
The new node/particle.


Copyright © 2012. All Rights Reserved.