fcmodeler.layout
Class GEMLayout

java.lang.Object
  |
  +--fcmodeler.layout.AbstractLayout
        |
        +--fcmodeler.layout.GEMLayout
All Implemented Interfaces:
diva.graph.layout.GlobalLayout

public class GEMLayout
extends AbstractLayout

GEM (Graph EMbedder) is a spring embedder style layout algorithm by A. Frick. See www.frick-consulting.de/publications.html

Since:
JDK1.3
Version:
$Revision: 1.3 $
Author:
Adam Tomjack

Inner Class Summary
protected  class GEMLayout.NodeInfo
           
 
Field Summary
protected  java.awt.Point _center
          The barycenter of the graph multiplied by the number of nodes.
protected  int _elen
          I think this is some sort of scaling constant related to the fact that the algorithm is integer based.
protected  int _iteration
           
protected  int _layoutType
           
protected  int _MAXATTRACT
           
protected  int _maxTemp
           
protected  GEMLayout.NodeInfo[] _nodeData
          Node state information.
protected  int[] _nodesPermutation
           
protected  java.util.Map _nodesToIndices
           
protected  int _numEdges
           
protected  int _numNodes
           
protected  double _oscillation
           
protected  java.util.Random _rand
           
protected  double _rotation
           
protected  boolean _statusReport
           
protected  int _temperature
           
protected  boolean _verbose
           
protected  double a_finalTemp
           
protected  double a_gravity
           
protected  double a_maxIter
           
protected  double a_maxTemp
           
protected  double a_oscillation
           
protected  double a_rotation
           
protected  double a_shake
           
protected  double a_startTemp
           
protected  double i_finalTemp
           
protected  double i_gravity
           
protected  double i_maxIter
           
protected  double i_maxTemp
           
protected  double i_oscillation
           
protected  double i_rotation
           
protected  double i_shake
           
protected  double i_startTemp
           
protected  double o_finalTemp
           
protected  double o_gravity
           
protected  double o_maxIter
           
protected  double o_maxTemp
           
protected  double o_oscillation
           
protected  double o_rotation
           
protected  double o_shake
           
protected  double o_startTemp
           
 
Fields inherited from class fcmodeler.layout.AbstractLayout
_edgesToEdgeFigures, _fcmodeler, _nodes
 
Constructor Summary
GEMLayout(FCModeler fcmodeler, int layoutType)
           
 
Method Summary
 java.awt.Point a_impulse(int nodeIndex, boolean[] activeNodes, double shake, double gravity)
          Given a list of nodes to consider, compute the sum of the forces on a node.
 void a_round(int impulseFunction)
          Loop through all nodes and displace() each once.
 void arrange(int impulseFunction)
          Move the nodes.
 int breadthFirstSearch(int root)
          This isn't a breadth first search.
 java.awt.Point centerOfMass(java.util.List nodes)
          Find the center of mass of a List of nodes.
 void circleInsert()
          Insert the nodes along the perimeter of a circle.
 void computeLayout()
          This is the main function which drives the layout.
 void displace(int nodeIndex, java.awt.Point impulse)
          Given the previously computed impulse, move the node, update the necessary variables, check for oscillation and rotation, and update the temperatures.
 java.util.List getAdjacentNodes(int node, boolean[] activeNodes)
          Build a list of nodes adjacent to the indicated node.
 boolean[] getAllActive()
          Some functions require a list of nodes that should be considered during calculations.
 boolean[] getNoneActive()
          like getAllActive() except all nodes are off by default.
 int graphCenter()
          Find the index of the node that is at the center of the graph.
 java.awt.Point impulse(int nodeIndex, boolean[] activeNodes, double shake, double gravity)
          Given a list of nodes to consider, compute the sum of the forces on a node.
 void init()
          Set up some global variables.
 void initVertexData(double startTemp)
          Set the initial temperature of each node, find the total temperature of the graph, and compute the center point.
 void insert()
          Insert the nodes.
 void moveNodes()
          Translate the nodes so that they are all in the correct quadrant and there is no extra padding.
 void o_round()
           
 void optimize()
           
 void permuteNodes()
          Permute the nodes using the Fischer Yates shuffle.
 void randomInsert()
          Insert the nodes randomly.
 
Methods inherited from class fcmodeler.layout.AbstractLayout
getBoundingBox, getFCModeler, getGraph, getLayoutTarget, layout, layout, placeNode, setFCModeler
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

_verbose

protected boolean _verbose

_statusReport

protected boolean _statusReport

i_maxTemp

protected double i_maxTemp

i_startTemp

protected double i_startTemp

i_finalTemp

protected double i_finalTemp

i_maxIter

protected double i_maxIter

i_gravity

protected double i_gravity

i_oscillation

protected double i_oscillation

i_rotation

protected double i_rotation

i_shake

protected double i_shake

a_maxTemp

protected double a_maxTemp

a_startTemp

protected double a_startTemp

a_finalTemp

protected double a_finalTemp

a_maxIter

protected double a_maxIter

a_gravity

protected double a_gravity

a_oscillation

protected double a_oscillation

a_rotation

protected double a_rotation

a_shake

protected double a_shake

o_maxTemp

protected double o_maxTemp

o_startTemp

protected double o_startTemp

o_finalTemp

protected double o_finalTemp

o_maxIter

protected double o_maxIter

o_gravity

protected double o_gravity

o_oscillation

protected double o_oscillation

o_rotation

protected double o_rotation

o_shake

protected double o_shake

_elen

protected int _elen
I think this is some sort of scaling constant related to the fact that the algorithm is integer based.

_MAXATTRACT

protected int _MAXATTRACT

_temperature

protected int _temperature

_maxTemp

protected int _maxTemp

_center

protected java.awt.Point _center
The barycenter of the graph multiplied by the number of nodes. In other words, _center represents the vector sum of the positions of all the nodes To find the center of mass, simply divide by the number of nodes.

_oscillation

protected double _oscillation

_rotation

protected double _rotation

_iteration

protected int _iteration

_numNodes

protected int _numNodes

_numEdges

protected int _numEdges

_nodeData

protected GEMLayout.NodeInfo[] _nodeData
Node state information.

_nodesPermutation

protected int[] _nodesPermutation

_nodesToIndices

protected java.util.Map _nodesToIndices

_layoutType

protected int _layoutType

_rand

protected java.util.Random _rand
Constructor Detail

GEMLayout

public GEMLayout(FCModeler fcmodeler,
                 int layoutType)
Method Detail

a_round

public void a_round(int impulseFunction)
Loop through all nodes and displace() each once.

arrange

public void arrange(int impulseFunction)
Move the nodes. This is the main computation of this layout algorithm.

breadthFirstSearch

public int breadthFirstSearch(int root)
This isn't a breadth first search. It uses one to calculate a number which represents the centralness of the given node. It finds the minimum distance between every node and the specified node, adds those distances, and returns that number.

centerOfMass

public java.awt.Point centerOfMass(java.util.List nodes)
Find the center of mass of a List of nodes. This does not return a node. graphCenter() returns a node which at the center. Given a layout, this computes the center of mass of the layout. This center of mass may or may not be located at a node's position.

computeLayout

public void computeLayout()
This is the main function which drives the layout.
Overrides:
computeLayout in class AbstractLayout

displace

public void displace(int nodeIndex,
                     java.awt.Point impulse)
Given the previously computed impulse, move the node, update the necessary variables, check for oscillation and rotation, and update the temperatures.

getAdjacentNodes

public java.util.List getAdjacentNodes(int node,
                                       boolean[] activeNodes)
Build a list of nodes adjacent to the indicated node.

getAllActive

public boolean[] getAllActive()
Some functions require a list of nodes that should be considered during calculations. This returns a such a list where every node is turned on by default.

getNoneActive

public boolean[] getNoneActive()
like getAllActive() except all nodes are off by default.

graphCenter

public int graphCenter()
Find the index of the node that is at the center of the graph. What constitutes the center is debatable. The GEM algorithm as presented in Frick's implementation finds the node where the maximum distance between that node and any other is less than the max distance with any other node as the reference point. I think a more appropriate center point could be computed in the following manner: Select a reference node. Find the minimum distance between that node and every other node. Sum the distances. The center is the reference node for which this sum is minimized. Consider a complete graph with a long tail attached to it. Since every node in the complete subgraph is separated by a distance of one, the center point would be one edge away from the center of the tail subgraph by Frick's algorithm. Mine would select the node to which the tail is attached. In summary: Frick chooses the center of area where I choose the center of mass. For now however, I'll use the first node as the center. I'll mess with this later.

impulse

public java.awt.Point impulse(int nodeIndex,
                              boolean[] activeNodes,
                              double shake,
                              double gravity)
Given a list of nodes to consider, compute the sum of the forces on a node.

a_impulse

public java.awt.Point a_impulse(int nodeIndex,
                                boolean[] activeNodes,
                                double shake,
                                double gravity)
Given a list of nodes to consider, compute the sum of the forces on a node.

init

public void init()
Set up some global variables. This only needs to be run once, unlike initVertexData which may be run more than once.

initVertexData

public void initVertexData(double startTemp)
Set the initial temperature of each node, find the total temperature of the graph, and compute the center point. This does not affect the positions, so it can be used without affecting previous layout work.

insert

public void insert()
Insert the nodes. This could be random, but instead we do some extra work to get close to the final layout to speed things up. It works like this: Place the first node at (0,0). Loop { Pick a node and place it at the center of mass of the adjacent nodes that have already been placed. Then do the spring embedder displacing thing with all nodes already placed to get it close to its final position. } This doesn't appear to work very well or to provide any speed enhancement over a random insertion. Perhaps I mistranslated it.

optimize

public void optimize()

o_round

public void o_round()

circleInsert

public void circleInsert()
Insert the nodes along the perimeter of a circle.

randomInsert

public void randomInsert()
Insert the nodes randomly.

moveNodes

public void moveNodes()
Translate the nodes so that they are all in the correct quadrant and there is no extra padding. Then place each Diva Node in it's correct position.

permuteNodes

public void permuteNodes()
Permute the nodes using the Fischer Yates shuffle. Frick has a function called select() that returned the index of a node. It did the shuffling a step at a time as you called select(). That seems unnecessary to me, so I chose to do the entire permutation at once. It makes things a little simpler. I just noticed that java.util.Collections.shuffle(List) could work, but this is already done. Using java.util.Arrays.asList() would make using the shuffle() function easier.