edu.uci.ics.jung.visualization.contrib
Class DAGLayout

java.lang.Object
  extended by edu.uci.ics.jung.visualization.AbstractLayout
      extended by edu.uci.ics.jung.visualization.SpringLayout
          extended by edu.uci.ics.jung.visualization.contrib.DAGLayout
All Implemented Interfaces:
ChangeEventSupport, Layout, LayoutMutable, VertexLocationFunction

public class DAGLayout
extends SpringLayout

Author:
John Yesberg DAGLayout is a layout algorithm which is suitable for tree-like directed acyclic graphs. Parts of it will probably not terminate if the graph is cyclic! The layout will result in directed edges pointing generally upwards. Any vertices with no successors are considered to be level 0, and tend towards the top of the layout. Any vertex has a level one greater than the maximum level of all its successors. Note: had to make minor access changes to SpringLayout to make this work. FORCE_CONSTANT, LengthFunction, SpringVertexData, and SpringEdgeData were all made "protected".

Nested Class Summary
 
Nested classes/interfaces inherited from class edu.uci.ics.jung.visualization.SpringLayout
SpringLayout.LengthFunction, SpringLayout.SpringDimensionChecker, SpringLayout.SpringEdgeData, SpringLayout.SpringVertexData, SpringLayout.UnitLengthFunction
 
Field Summary
protected static String MINIMUMLEVELKEY
           
 
Fields inherited from class edu.uci.ics.jung.visualization.SpringLayout
force_multiplier, lengthFunction, repulsion_range, stretch, UNITLENGTHFUNCTION
 
Fields inherited from class edu.uci.ics.jung.visualization.AbstractLayout
changeSupport, vertex_locations
 
Constructor Summary
DAGLayout(Graph g)
           
 
Method Summary
 void forceMove(Vertex picked, int x, int y)
          Override forceMove so that if someone moves a node, we can re-layout everything.
 boolean incrementsAreDone()
          Override incrementsAreDone so that we can eventually stop.
protected  void initialize_local()
          Had to override this one as well, to ensure that setRoot() is called.
protected  void initializeLocation(Vertex v, Coordinates coord, Dimension d)
          Sets random locations for a vertex within the dimensions of the space.
protected  void moveNodes()
          Override the moveNodes() method from SpringLayout.
static void propagateMinimumLevel(Vertex v)
          A recursive method for allocating the level for each vertex.
protected  void relaxEdges()
          Overridden relaxEdges.
static void setRoot(Graph g)
          setRoot calculates the level of each vertex in the graph.
static void setRoot(Vertex v)
          Set vertex v to be level 0.
 
Methods inherited from class edu.uci.ics.jung.visualization.SpringLayout
advancePositions, calcEdgeLength, calculateRepulsion, getAVertex, getForceMultiplier, getLength, getRepulsionRange, getSpringData, getSpringData, getSpringKey, getStatus, getStretch, initialize_local_vertex, isIncremental, setForceMultiplier, setRepulsionRange, setStretch, update
 
Methods inherited from class edu.uci.ics.jung.visualization.AbstractLayout
addChangeListener, applyFilter, dontMove, fireStateChanged, forceMove, getBaseKey, getChangeListeners, getCoordinates, getCurrentSize, getEdge, getEdge, getGraph, getLocation, getVertex, getVertex, getVertexIterator, getVisibleEdges, getVisibleGraph, getVisibleVertices, getX, getY, initialize, initialize, initializeLocations, isLocked, lockVertex, offsetVertex, postInitialize, removeChangeListener, resize, restart, unlockVertex
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface edu.uci.ics.jung.visualization.Layout
applyFilter, forceMove, getCurrentSize, getGraph, getLocation, getVertex, getVertex, getVisibleEdges, getVisibleVertices, getX, getY, initialize, isLocked, lockVertex, resize, restart, unlockVertex
 
Methods inherited from interface edu.uci.ics.jung.visualization.VertexLocationFunction
getVertexIterator
 

Field Detail

MINIMUMLEVELKEY

protected static final String MINIMUMLEVELKEY
See Also:
Constant Field Values
Constructor Detail

DAGLayout

public DAGLayout(Graph g)
Method Detail

setRoot

public static void setRoot(Graph g)
setRoot calculates the level of each vertex in the graph. Level 0 is allocated to any vertex with no successors. Level n+1 is allocated to any vertex whose successors' maximum level is n.


setRoot

public static void setRoot(Vertex v)
Set vertex v to be level 0.


propagateMinimumLevel

public static void propagateMinimumLevel(Vertex v)
A recursive method for allocating the level for each vertex. Ensures that all predecessors of v have a level which is at least one greater than the level of v.

Parameters:
v -

initializeLocation

protected void initializeLocation(Vertex v,
                                  Coordinates coord,
                                  Dimension d)
Sets random locations for a vertex within the dimensions of the space. This overrides the method in AbstractLayout

Overrides:
initializeLocation in class AbstractLayout
Parameters:
coord -
d -

initialize_local

protected void initialize_local()
Had to override this one as well, to ensure that setRoot() is called.

Overrides:
initialize_local in class SpringLayout

moveNodes

protected void moveNodes()
Override the moveNodes() method from SpringLayout. The only change we need to make is to make sure that nodes don't float higher than the minY coordinate, as calculated by their minimumLevel.

Overrides:
moveNodes in class SpringLayout

incrementsAreDone

public boolean incrementsAreDone()
Override incrementsAreDone so that we can eventually stop.

Specified by:
incrementsAreDone in interface Layout
Overrides:
incrementsAreDone in class SpringLayout

forceMove

public void forceMove(Vertex picked,
                      int x,
                      int y)
Override forceMove so that if someone moves a node, we can re-layout everything.


relaxEdges

protected void relaxEdges()
Overridden relaxEdges. This one reduces the effect of edges between greatly different levels.

Overrides:
relaxEdges in class SpringLayout