SpringGraphLayout (CharGer4 Documentation)

Object
- charger.layout.GraphLayout
- - charger.layout.SpringGraphLayout

```
public class SpringGraphLayout
extends GraphLayout
```
Implements a simple force-directed (spring) layout for Charger. The algorithm treats Charger nodes as nodes in this algorithm, while Charger lines are treated as springs. Calculations and changes are made on the basis of the internally held nodePositions list. The actual graph and nodes aren't supposed to be touched until the end of performLayout.
The main principle behind its operation is that graph nodes are subject to two forces: a spring force and a coulomb (electric charge) force. The edges are considered to be springs subject to Hooke's law where the force is attraction when the string is stretched (i.e., length greater than the equilibrium length desired) or repulsion when the spring is compressed to less than the equilibrium length. The nodes are considered to be electric point charges (all with the same positive charge) that repel each other according to Coulomb's reciprocal-of-the-distance law. There is a mass function which generally returns the same for all nodes, but can be adjusted (e.g., for immovable notes) depending on the kind of node. See the mass() method to override.
In order to handle contexts, the algorithm works in a depth-first recursive way. That is, nested contexts are laid out before their enclosing graph. The context is treated as a point-node, whose mass is equal to the sum of the masses of its constituents. If there is an edge that crosses into the context, a fake "edge" is temporarily created to directly connect the context itself for the purposes of determining the layout. This fake edge is only considered when laying out the outer graph; the context's layout is unaware of any edges that link to the outer context(s).
The displacement is merely the force interpreted as a position translation operation.
For unconnected components (in the graph theory sense), the algorithm will ordinarily cause them to push apart (since there's no spring force to balance), leaving lots of wide open space. Therefore there's a step that identifies unconnected components, and connects each one's center-most node with at least one other center-most node. This ensures that they will have at least one attractive force to help them stay together.
Fine tuning of the layout parameters is crucial to the effective use of the algorithm. See comments on each of the layout parameters to better understand how they work.

Future tweaks:
Tell the force calculators to "favor" x-forces so that layouts will tend toward landscape orientation.
Tell the force calculators to "favor" rectilinear placement.

Author:

Harry S. Delugach (delugach@uah.edu)

Field Summary

Fields
Modifier and Type	Field and Description
`private boolean`	`applyUpLeftPressure`
`private int`	`ATTRACTION_FORCE_SIGN` The arithmetic sign of an attractive force.
`private double`	`borderMargin` How much extra space to provide on the top and left of the final laid out graph.
`private float`	`contextInnerPadding` How much padding to provide between the bounding rectangle of the graph/context and its enclosed contents.
`private double`	`COULOMB_CONSTANT` Coulomb constant (numerator) for the distance-squared calculations.
`private double`	`COULOMB_EXPONENT` Used to further "dampen" the coulomb force.
`private static double`	`DAMPER_FOR_COULOMB` Multiplier for the coulomb (repulsion) force
`private static double`	`DAMPER_FOR_SPRING` Multiplier for the spring force
`private static double`	`DAMPING_FOR_DISPLACEMENTS` Further damping for displacements; currently set to 1.0
`private ArrayList<GEdge>`	`edges`
`private double`	`ENERGY_THRESHHOLD` The minimum energy level that tells the algorithm it can stop.
`private double`	`ENERGY_THRESHHOLD_PER_NODE` To fine-tune the threshhold
`private static double`	`EPSILON` Double-precision values are considered equal if they are within this value of each other
`private double`	`equilibriumEdgeLength` The "best" edge length.
`private double`	`MAX_DISTANCE` The maximum distance between nodes; if they are farther apart than this, bring them in to this distance.
`private Rectangle2D.Double`	`maxBoundsAvailable` How much space this graph is allowed to occupy
`static int`	`maxIterations` When to call it quits on iterating through the algorithm.
`private double`	`MIN_DISTANCE` The minimum distance between nodes; if they are actually closer than this, then assume they are at this distance.
`private static DecimalFormat`	`nformat`
`private HashMap<GNode,Point2D.Double>`	`nodeDisplacements` Displacement is represented as a "point" where the x value is dx and the y value is dy.
`private HashMap<GNode,Point2D.Double>`	`nodeForces`
`private HashMap<GNode,Point2D.Double>`	`nodePositions` Keeps track of each node's displacement (movement) at each iteration.
`private ArrayList<GNode>`	`nodes`
`private double`	`pressureScale`
`private int`	`REPULSION_FORCE_SIGN` Set to -1 * the attraction force.
`private static double`	`SPRING_CONSTANT` Used in determining the spring force using Hooke's law.
`private static Point2D.Double`	`zeroPoint`

Fields inherited from class charger.layout.GraphLayout
graph, verbose

Constructor Summary

Constructors
Constructor and Description

SpringGraphLayout(Graph g)

Constructors
Constructor and Description
`SpringGraphLayout(Graph g)`

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`addEdgesFromUnconnectedComponents()` Add custom edges between unconnected graph components.
`void`	`addForceToNodeForces(Point2D.Double force, GraphObject node)` For the given node, add the force to the current forces on it.
`void`	`addNewCoulombForces()` For each node in the graph, calculate the new coulomb force vectors (as "points") and add them to the nodeForces list.
`void`	`addNewSpringForces()`
`void`	`copyToGraph()` Update the actual graph to reflect the positions calculated by the layout.
`Point2D.Double`	`coulomb_force(GNode thisnode, GNode other)` Given two nodes, calculates the coulomb force that repels them.
`double`	`getBorderMargin()`
`protected Rectangle2D.Double`	`getBounds(boolean displayRects)` Find the bounds of all the node positions (not the original graph).
`double`	`getClippedLength(GNode node1, GNode node2)` Considers the shape (from the original graph) returns the distance between the clipping points of a center-to-center line between the objects.
`protected Rectangle2D.Double`	`getDisplayRectBounds()` Find the bounds of all the node display rectangles (using the original graph).
`double`	`getEquilibriumEdgeLength()` The preferred length of an edge to be sought by the algorithm.
`Rectangle2D.Double`	`getMaxBoundsAvailable()` Find out the maximum size of the area in which nodes can be placed.
`protected Rectangle2D.Double`	`getPositionBounds()` Find the bounds of all the node positions (not the original graph).
`static Point2D.Double`	`getXYForce(double force, Point2D.Double source, Point2D.Double dest)` Calculates both the x and y components of a force between two points.
`private Rectangle2D.Double`	`inferCurrentDisplayRect(GNode node)` Uses the height and width of the node's display rectangle, but infers (from its new proposed center point) the rectangle it would form in its nodePositions location.
`void`	`loadEdges()` Initializes the edges list.
`void`	`loadNodePositions()` Using the nodes list, get the actual positions from the original objects and load up nodePositions list.
`double`	`makeNewPositions(boolean upLeftPressure)` From the existing forces vectors, calculate a displacement for each node, assume a unit time interval and calculate a new position for each node.
`double`	`mass(GNode gn)` Allows the algorithm to adjust for varying "sizes" of nodes.
`void`	`moveToUpperLeft(boolean force)` Makes sure there are no negative-coordinate positions.
`protected boolean`	`nodesInLine()` Using the original graph nodes, determines whether, within EPSILON, the nodes are in line, either along an x-value or a y-value.
`boolean`	`performLayout()` Perform the layout operation on the graph.
`boolean`	`performLayoutOnContext(Graph g)` Invokes the spring algorithm recursively on any nested graph.
`double`	`performOneRelaxation()` One iteration of the algorithm, starting with zero forces all around.
`protected void`	`randomizePositions()` Not really random; moves each node one pixel right and down from the previous node.
`static Point2D.Double`	`reverseForce(Point2D.Double force)`
`protected void`	`scanAndLoadGraph()` Initialize the node and edges lists.
`void`	`setBorderMargin(double borderMargin)`
`void`	`setEquilibriumEdgeLength(double equilibriumEdgeLength)`
`void`	`setMaxBoundsAvailable(Rectangle rect)` Set the available rectangle to be the current extent of the graph; i.e., it will not take up any more room in display.
`void`	`setMaxBoundsAvailable(Rectangle2D.Double maxBoundsAvailable)` Set the maximum space allowed in laying out the graph.
`private void`	`showAllForces(String s)`
`private void`	`showDisplacements(String s)`
`static String`	`showForce(Point2D.Double p)`
`private String`	`showPoint(Point2D.Double point)`
`private void`	`showPositions(String s)`
`Point2D.Double`	`spring_force(GEdge edge, boolean fromTo)` Models the Hooke's law spring force along edges.
`private void`	`zeroOutVectors(HashMap<GNode,Point2D.Double> points)` convenience method for re-setting the hashmaps after each relaxation.

Methods inherited from class charger.layout.GraphLayout
isVerbose, setVerbose

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - equilibriumEdgeLength
```
private double equilibriumEdgeLength
```
    The "best" edge length. For the spring forces, this is the distance at which the force is zero.
  - borderMargin
```
private double borderMargin
```
    How much extra space to provide on the top and left of the final laid out graph.
  - contextInnerPadding
```
private float contextInnerPadding
```
    How much padding to provide between the bounding rectangle of the graph/context and its enclosed contents.
  - maxBoundsAvailable
```
private Rectangle2D.Double maxBoundsAvailable
```
    How much space this graph is allowed to occupy
  - maxIterations
```
public static int maxIterations
```
    When to call it quits on iterating through the algorithm. Currently set to a user-settable value.
    
    See Also:
    
    Global.springLayoutMaxIterations
  - MIN_DISTANCE
```
private double MIN_DISTANCE
```
    The minimum distance between nodes; if they are actually closer than this, then assume they are at this distance. This is to prevent short distances from overwhelming the repulsion forces for nodes
  - MAX_DISTANCE
```
private double MAX_DISTANCE
```
    The maximum distance between nodes; if they are farther apart than this, bring them in to this distance.
  - DAMPER_FOR_SPRING
```
private static final double DAMPER_FOR_SPRING
```
    Multiplier for the spring force
    
    See Also:
    
    Constant Field Values
  - DAMPER_FOR_COULOMB
```
private static final double DAMPER_FOR_COULOMB
```
    Multiplier for the coulomb (repulsion) force
    
    See Also:
    
    Constant Field Values
  - COULOMB_EXPONENT
```
private double COULOMB_EXPONENT
```
    Used to further "dampen" the coulomb force. The physical constant would set this to 2.0 (1/distance-squared) but it's set to 2.2 so that node repulsion will drop off faster.
  - ENERGY_THRESHHOLD
```
private double ENERGY_THRESHHOLD
```
    The minimum energy level that tells the algorithm it can stop. This value is actually set in performLayout so that it can be tuned for the number of nodes and edges.
  - ENERGY_THRESHHOLD_PER_NODE
```
private double ENERGY_THRESHHOLD_PER_NODE
```
    To fine-tune the threshhold
  - EPSILON
```
private static double EPSILON
```
    Double-precision values are considered equal if they are within this value of each other
  - DAMPING_FOR_DISPLACEMENTS
```
private static double DAMPING_FOR_DISPLACEMENTS
```
    Further damping for displacements; currently set to 1.0
  - SPRING_CONSTANT
```
private static double SPRING_CONSTANT
```
    Used in determining the spring force using Hooke's law. Currently set to 1.0.
    
    See Also:
    
    DAMPER_FOR_SPRING
  - COULOMB_CONSTANT
```
private double COULOMB_CONSTANT
```
    Coulomb constant (numerator) for the distance-squared calculations. Currently set to Math.pow( equilibriumEdgeLength, COULOMB_EXPONENT )
    
    See Also:
    
    COULOMB_EXPONENT
  - zeroPoint
```
private static final Point2D.Double zeroPoint
```
  - ATTRACTION_FORCE_SIGN
```
private int ATTRACTION_FORCE_SIGN
```
    The arithmetic sign of an attractive force. Forces with this sign are considered attractive forces. Forces with the opposite sign are considered negative forces.
  - REPULSION_FORCE_SIGN
```
private int REPULSION_FORCE_SIGN
```
    Set to -1 * the attraction force.
  - nformat
```
private static DecimalFormat nformat
```
  - applyUpLeftPressure
```
private boolean applyUpLeftPressure
```
  - pressureScale
```
private double pressureScale
```
  - nodeDisplacements
```
private HashMap<GNode,Point2D.Double> nodeDisplacements
```
    Displacement is represented as a "point" where the x value is dx and the y value is dy.
  - nodePositions
```
private HashMap<GNode,Point2D.Double> nodePositions
```
    Keeps track of each node's displacement (movement) at each iteration.
  - nodeForces
```
private HashMap<GNode,Point2D.Double> nodeForces
```
  - nodes
```
private ArrayList<GNode> nodes
```
  - edges
```
private ArrayList<GEdge> edges
```
- Constructor Detail
  - SpringGraphLayout
```
public SpringGraphLayout(Graph g)
```
- Method Detail
  - scanAndLoadGraph
```
protected void scanAndLoadGraph()
```
    Initialize the node and edges lists. Treats the outer graph only after it has recursively called itself on the inner graphs.
  - nodesInLine
```
protected boolean nodesInLine()
```
    Using the original graph nodes, determines whether, within EPSILON, the nodes are in line, either along an x-value or a y-value. Both of these constitute pathological cases, and the solution is to slightly alter some of their positions.
    
    Returns:
    
    true if the centers are within EPSILON of the same value (either x or y); false otherwise.
  - randomizePositions
```
protected void randomizePositions()
```
    Not really random; moves each node one pixel right and down from the previous node. Warning: modifies the original graph!
  - zeroOutVectors
```
private void zeroOutVectors(HashMap<GNode,Point2D.Double> points)
```
    convenience method for re-setting the hashmaps after each relaxation.
    
    Parameters:
    
    points -
  - performLayout
```
public boolean performLayout()
```
    Perform the layout operation on the graph. Does not update the original graph, just in case there's an error; simply updates the nodes and edges collections.
    
    Specified by:
    
    performLayout in class GraphLayout
    
    Returns:
    
    true if all went well; false if something went wrong.
    
    See Also:
    
    copyToGraph()
  - performOneRelaxation
```
public double performOneRelaxation()
```
    One iteration of the algorithm, starting with zero forces all around. If verbose is set, then will announce some of its progress along the way. calculated.
    
    Returns:
    
    total energy for the collection of nodes for this iteration
  - performLayoutOnContext
```
public boolean performLayoutOnContext(Graph g)
```
    Invokes the spring algorithm recursively on any nested graph. Takes its parameters from the caller, except of course for the bounds of the context. Updates the original nodes inside the context, and adjusts its size, but leaves the position to be determined by its enclosing graph's layout. Does not yet handle undisplayed contexts, which are probably going to fail here.
    
    Parameters:
    
    g - the context to be laid out
  - makeNewPositions
```
public double makeNewPositions(boolean upLeftPressure)
```
    From the existing forces vectors, calculate a displacement for each node, assume a unit time interval and calculate a new position for each node. Does NOT actually change the positions of the graph nodes.
    
    Parameters:
    
    upLeftPressure - if true, then an additional "pressure" is applied to force nodes upward and to the left. This should help layouts from getting too spread out.
    
    Returns:
    
    total energy of the displacements times the masses added up.
  - addNewCoulombForces
```
public void addNewCoulombForces()
```
    For each node in the graph, calculate the new coulomb force vectors (as "points") and add them to the nodeForces list.
  - addNewSpringForces
```
public void addNewSpringForces()
```
  - coulomb_force
```
public Point2D.Double coulomb_force(GNode thisnode,
                                    GNode other)
```
    Given two nodes, calculates the coulomb force that repels them. The sign of this force is always -1 * ATTRACTIVE_FORCE_SIGN. Distances of less than MIN_DISTANCE are calculated as though they were at MIN_DISTANCE apart.
    
    Parameters:
    
    thisnode - The node from which the other is being repelled
    
    other -
    
    Returns:
    
    the repulsive force between the nodes
  - spring_force
```
public Point2D.Double spring_force(GEdge edge,
                                   boolean fromTo)
```
    Models the Hooke's law spring force along edges. Unlike the coulomb force, which is always repulsive, this force can be attractive or repulsive, depending on whether the spring is compressed (repulsive) or extended (attractive). Considered as the force between the from object and the to object
    
    Parameters:
    
    edge - The edge whose forces are to be determined
    
    fromTo - Whether to calculate force from the from object to the to object or vice versa
    
    Returns:
    
    an x,y pair that represent the force relative to that node
  - mass
```
public double mass(GNode gn)
```
    Allows the algorithm to adjust for varying "sizes" of nodes. For example, the note shouldn't move much, so it gets a very low mass.
    
    Parameters:
    
    gn -
    
    Returns:
    
    the computed "mass" for an object - 1.0 for regular nodes, 0.1 for a note, so that it doesn't move much.
  - addForceToNodeForces
```
public void addForceToNodeForces(Point2D.Double force,
                                 GraphObject node)
```
    For the given node, add the force to the current forces on it.
    
    Parameters:
    
    force - x and y values to be added to the force, multiplied by the "mass" of the node.
    
    node - The node whose force is to be altered
  - moveToUpperLeft
```
public void moveToUpperLeft(boolean force)
```
    Makes sure there are no negative-coordinate positions. Adjusts the positions as found in the nodePositions list. Does not alter the original graph. Allows for an equilibrium edge length margin on the top and left. If this is a nested graph (i.e., ownergraph != null) then take into account the context label during the y-calculation.
    
    Parameters:
    
    force - Whether to force the graph into the upper left corner whether it already fits or not.
  - getXYForce
```
public static Point2D.Double getXYForce(double force,
                                        Point2D.Double source,
                                        Point2D.Double dest)
```
    Calculates both the x and y components of a force between two points. The direction of the force is considered to be from the source to the pushed one ... that is, if the force is positive in that direction, the sign of each component will depend on their geometric alignment to the original force. Forces are with respect to the Java coordinate system; i.e., if the y force is positive, it is pushed downward, not upward.
    
    Parameters:
    
    force -
    
    source -
    
    dest -
    
    Returns:
    
    a point containing x,y values representing the force's horizontal and vertical components respectively.
  - loadNodePositions
```
public void loadNodePositions()
```
    Using the nodes list, get the actual positions from the original objects and load up nodePositions list.
  - loadEdges
```
public void loadEdges()
```
    Initializes the edges list. If an edge is connected to an object that is NOT in the node list, that means it must be in a node that is nested in a context, whose internal content is not handled at this level. In order to account for the edge forces, we create an invisible edge that links to the context rather than the internal node. This should not affect copying to the graph, since edges aren't copied, but simply used to determine forces on the nodes.
  - addEdgesFromUnconnectedComponents
```
public void addEdgesFromUnconnectedComponents()
```
    Add custom edges between unconnected graph components.
  - copyToGraph
```
public void copyToGraph()
```
    Update the actual graph to reflect the positions calculated by the layout. Also deletes the custom edges which could cause problems if left behind. algorithm. Repositions the graph to the upper left corner.
    
    Specified by:
    
    copyToGraph in class GraphLayout
  - showAllForces
```
private void showAllForces(String s)
```
  - showDisplacements
```
private void showDisplacements(String s)
```
  - showPositions
```
private void showPositions(String s)
```
  - showPoint
```
private String showPoint(Point2D.Double point)
```
  - showForce
```
public static String showForce(Point2D.Double p)
```
  - reverseForce
```
public static Point2D.Double reverseForce(Point2D.Double force)
```
  - getBounds
```
protected Rectangle2D.Double getBounds(boolean displayRects)
```
    Find the bounds of all the node positions (not the original graph).
    
    Parameters:
    
    displayRects - whether to consider the displayrects (an approximation for the shapes)
    
    Returns:
    
    the bounds all added up
  - getPositionBounds
```
protected Rectangle2D.Double getPositionBounds()
```
    Find the bounds of all the node positions (not the original graph).
    
    Returns:
    
    a rectangle that encloses all the currently-calculated center points of the objects in the graph.
  - getDisplayRectBounds
```
protected Rectangle2D.Double getDisplayRectBounds()
```
    Find the bounds of all the node display rectangles (using the original graph).
    
    Returns:
    
    a rectangle that encloses all the currently-calculated display rectangles of the objects in the graph.
  - inferCurrentDisplayRect
```
private Rectangle2D.Double inferCurrentDisplayRect(GNode node)
```
    Uses the height and width of the node's display rectangle, but infers (from its new proposed center point) the rectangle it would form in its nodePositions location. Don't use the original display rect, because we've moved its center.
    
    Parameters:
    
    node -
    
    Returns:
    
    what the layout thinks will be the displayrect of the node if the layout stops right now.
  - getClippedLength
```
public double getClippedLength(GNode node1,
                               GNode node2)
```
    Considers the shape (from the original graph) returns the distance between the clipping points of a center-to-center line between the objects. Uses the nodePositions list, not the original graph objects' positions. There is a problem with this approach -- what if the two nodes' rectangles overlap? That would mean that the clipped length might be negative.
  - getMaxBoundsAvailable
```
public Rectangle2D.Double getMaxBoundsAvailable()
```
    Find out the maximum size of the area in which nodes can be placed.
    
    Returns:
    
    the rectangle
  - setMaxBoundsAvailable
```
public void setMaxBoundsAvailable(Rectangle rect)
```
    Set the available rectangle to be the current extent of the graph; i.e., it will not take up any more room in display.
    
    Parameters:
    
    rect -
  - setMaxBoundsAvailable
```
public void setMaxBoundsAvailable(Rectangle2D.Double maxBoundsAvailable)
```
    Set the maximum space allowed in laying out the graph. May increase or decrease the space it takes to display the laid out graph.
    
    Parameters:
    
    maxBoundsAvailable -
  - getEquilibriumEdgeLength
```
public double getEquilibriumEdgeLength()
```
    The preferred length of an edge to be sought by the algorithm.
    
    Returns:
    
    the preferred length of an edge to be sought by the algorithm
  - setEquilibriumEdgeLength
```
public void setEquilibriumEdgeLength(double equilibriumEdgeLength)
```
  - getBorderMargin
```
public double getBorderMargin()
```
  - setBorderMargin
```
public void setBorderMargin(double borderMargin)
```

Class SpringGraphLayout

Field Summary

Fields inherited from class charger.layout.GraphLayout

Constructor Summary

Method Summary

Methods inherited from class charger.layout.GraphLayout

Methods inherited from class Object

Field Detail

equilibriumEdgeLength

borderMargin

contextInnerPadding

maxBoundsAvailable

maxIterations

MIN_DISTANCE

MAX_DISTANCE

DAMPER_FOR_SPRING

DAMPER_FOR_COULOMB

COULOMB_EXPONENT

ENERGY_THRESHHOLD

ENERGY_THRESHHOLD_PER_NODE

EPSILON

DAMPING_FOR_DISPLACEMENTS

SPRING_CONSTANT

COULOMB_CONSTANT

zeroPoint

ATTRACTION_FORCE_SIGN

REPULSION_FORCE_SIGN

nformat

applyUpLeftPressure

pressureScale

nodeDisplacements

nodePositions

nodeForces

nodes

edges

Constructor Detail

SpringGraphLayout

Method Detail

scanAndLoadGraph

nodesInLine

randomizePositions

zeroOutVectors

performLayout

performOneRelaxation

performLayoutOnContext

makeNewPositions

addNewCoulombForces

addNewSpringForces

coulomb_force

spring_force

mass

addForceToNodeForces

moveToUpperLeft

getXYForce

loadNodePositions

loadEdges

addEdgesFromUnconnectedComponents

copyToGraph

showAllForces

showDisplacements

showPositions

showPoint

showForce

reverseForce

getBounds

getPositionBounds

getDisplayRectBounds

inferCurrentDisplayRect

getClippedLength

getMaxBoundsAvailable

setMaxBoundsAvailable

setMaxBoundsAvailable

getEquilibriumEdgeLength

setEquilibriumEdgeLength

getBorderMargin

setBorderMargin