diva.graph.layout
Class LevelLayout

java.lang.Object
  diva.graph.layout.AbstractGlobalLayout
      diva.graph.layout.LevelLayout

All Implemented Interfaces:

GlobalLayout

Direct Known Subclasses:

BasicGraphFrame.PtolemyLayout

public class LevelLayout
extends AbstractGlobalLayout

A level-based layout algorithm originally implemented by Ulfar Erlingsson at Cornell/RPI and modified to fit into this system.

The algorithm is structured in the following way:

• Copy the original graph. The copy will be augmented with dummy nodes, edges, etc. The method which performs the copy can be overridden in a subclass so that the the layout can be customized. For example, one might wish to create dummy edges from a composite node, which represent edges from subnodes of the composite node to subnodes in other composite nodes in the graph (e.g. if you are laying out a circuit schematic, with composite nodes representing components and subnodes representing pins on the components).
• Perform the levelizing layout on the graph copy. This process consists of several steps:
  • Calculate the levels of the nodes in the graph.
  • Add dummy nodes on edges which span multiple levels in the graph.
  • Perform a sorting on each level in the graph based on some cost function (not yet implemented).
  • Assign a position based on the level and sorting order of the node.
• Copy the layout results from the graph copy back into the original graph, ignoring dummy nodes. This should also be overridden if the copy process was overridden (described above).

TODO:

• Break cycles in the graph.
• Implement barycentric layout (currently commented out).

Version:

$Id: LevelLayout.java 40814 2006-02-11 17:24:01Z cxh $

Author:

Michael Shilman

Accepted Rating:

Red

Nested Class Summary

class	LevelLayout.LevelData
static class	LevelLayout.LevelInfo The semantic object of each node in the graph copy that is being laid out.

Field Summary

private BasicGraphModel	_local The graph implementation of the graph copy, for adding dummy nodes/edges to the graph copy.
protected int	_orientation Keep track of the orientation; vertical by default.
private boolean	_randomizedPlacement A flag to determine whether or not we want to randomize the placement of the nodes.
static int	HORIZONTAL Layout the graph in levels from left to right.
static int	VERTICAL Layout the graph in levels from top to bottom.

Fields inherited from class diva.graph.layout.AbstractGlobalLayout

_layoutTarget

Constructor Summary

LevelLayout(LayoutTarget target)
Construct a new levelizing layout with a vertical orientation.

Method Summary

private void	addDummies(LevelLayout.LevelData levelData) Add dummy nodes between nodes along edges that span multiple levels.
private void	addSubGraphReverseDFS(LevelLayout.LevelData levelData, java.lang.Object node) Add this node and all of its parent nodes to the levels array in a reverse DFS.
void	applyLayout(LevelLayout.LevelData levelData, java.lang.Object g) Place the nodes in the target environment according to their levels and sorting order which are specified in levelData.
void	applyLayout(LevelLayout.LevelData levelData, java.lang.Object g, boolean useDummies) Place the nodes in the target environment according to their levels and sorting order which are specified in levelData.
private void	ASSERT(boolean b, java.lang.String err) Assert the given condition and throw a runtime exception with the given string if the assertion fails.
private void	breakCycles(java.lang.Object composite, GraphModel model) Inefficient algorithm to break cycles in the graph.
LevelLayout.LevelData	calculateLayout(java.lang.Object composite) This method performs levelizing layout on the given composite.
private boolean	checkAndBreak(java.lang.Object edge, java.lang.Object node) Return true if a cycle was broken.
private void	computeLevels(LevelLayout.LevelData levelData) Topological sort of graph and then set level numbers for the nodes.
protected java.lang.Object	copyComposite(java.lang.Object origComposite) Copy the given graph and make the nodes/edges in the copied graph point to the nodes/edges in the original.
protected void	copyLayout(java.lang.Object origComposite, java.lang.Object copyComposite) Take the layout generated by the core layout algorithm and copy it back into the view of the original composite passed in by the user.
private int	getLevel(java.lang.Object node) Get the level of n in the graph.
private LevelLayout.LevelInfo	getLevelInfo(java.lang.Object node)
BasicGraphModel	getLocalGraphModel() Return the local graph model.
int	getOrientation() Return the orientation in which the graph is to be laid out, either VERTICAL or HORIZONTAL.
boolean	getRandomizedPlacement() Return whether or not placement will be randomized.
private int	getUsage(java.lang.Object node) Get the level of n in the graph.
private void	initialOrderNodes(LevelLayout.LevelData levelData, java.lang.Object maxNode) Assign an initial ordering to the nodes.
private boolean	isDummy(java.lang.Object node) Return whether or not the given node is a dummy.
boolean	isVisited(java.lang.Object node)
void	layout(java.lang.Object composite) Perform the levelizing layout on the given composite in the given target environment.
private void	makeLevels(LevelLayout.LevelData levelData) Get the level of n in the graph.
private void	makeMeta(LevelLayout.LevelData levelData) Create a meta-node and add it to the graph, connecting it to each existing node in the graph.
private void	placeNode(java.lang.Object node, double x, double y)
private void	placeNodes(LevelLayout.LevelData levelData, java.awt.geom.Rectangle2D vp, boolean useDummies) Place the nodes in the graph, based on the previous level calculations and the order of the nodes in the _levels array.
private void	removeMeta(LevelLayout.LevelData levelData) Remove the meta-node from the graph.
void	setAllVisited(java.lang.Object composite, boolean val)
private void	setLevel(java.lang.Object node, int l) Set the level of n in the graph.
void	setOrientation(int o) Set the orientation in which the graph is to be laid out, either VERTICAL or HORIZONTAL.
void	setRandomizedPlacement(boolean flag) Set whether or not placement will be randomized.
private void	setUsage(java.lang.Object node, int val) Set the level of n in the graph.
void	setVisited(java.lang.Object node, boolean val)
private void	topoSort(java.lang.Object node, java.util.ArrayList topo) Topologically sort from the given node and place the results in the given array list.

Methods inherited from class diva.graph.layout.AbstractGlobalLayout

getLayoutTarget, setLayoutTarget

Methods inherited from class java.lang.Object

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

Field Detail

VERTICAL

public static final int VERTICAL

Layout the graph in levels from top to bottom.

See Also:

setOrientation(int), Constant Field Values

HORIZONTAL

public static final int HORIZONTAL

Layout the graph in levels from left to right.

See Also:

setOrientation(int), Constant Field Values

_orientation

protected int _orientation

Keep track of the orientation; vertical by default.

_local

private BasicGraphModel _local

The graph implementation of the graph copy, for adding dummy nodes/edges to the graph copy.

_randomizedPlacement

private boolean _randomizedPlacement

A flag to determine whether or not we want to randomize the placement of the nodes.

Constructor Detail

LevelLayout

public LevelLayout(LayoutTarget target)

Construct a new levelizing layout with a vertical orientation.

Method Detail

copyComposite

protected java.lang.Object copyComposite(java.lang.Object origComposite)

Copy the given graph and make the nodes/edges in the copied graph point to the nodes/edges in the original.

copyLayout

protected void copyLayout(java.lang.Object origComposite,
                          java.lang.Object copyComposite)

Take the layout generated by the core layout algorithm and copy it back into the view of the original composite passed in by the user.

getLocalGraphModel

public BasicGraphModel getLocalGraphModel()

Return the local graph model.

getOrientation

public int getOrientation()

Return the orientation in which the graph is to be laid out, either VERTICAL or HORIZONTAL.

getRandomizedPlacement

public boolean getRandomizedPlacement()

Return whether or not placement will be randomized.

layout

public void layout(java.lang.Object composite)

Perform the levelizing layout on the given composite in the given target environment. It operates on a copy of the composite and then copies the layout results back into the original view (the given layout target).

Specified by:

layout in interface GlobalLayout

Specified by:

layout in class AbstractGlobalLayout

calculateLayout

public LevelLayout.LevelData calculateLayout(java.lang.Object composite)

This method performs levelizing layout on the given composite. It figures out the node levels, but doesn't actually layout the composite in the target environment yet. The level information can be accessed through the returned LevelData. This information can be used to size the viewport. The following are the operations performed in this method:

• Make a copy of the original composite. All operations are performed on the copy of the composite.
• Break the cycles in the composite if there are any.
• Add dummies to edges that span multiple levels in the composite.
• Assign level numbers to the nodes in the composite. This creates the _levels data structure which provides access to all the nodes in each level.
To apply this layout to the target environment, call applyLayout with the returned LevelData.

applyLayout

public void applyLayout(LevelLayout.LevelData levelData,
                        java.lang.Object g)

Place the nodes in the target environment according to their levels and sorting order which are specified in levelData. By default, the dummy nodes are used while doing the layout. This method should be called after calculateLayout(t, g) which returns the levelData used by this method.

applyLayout

public void applyLayout(LevelLayout.LevelData levelData,
                        java.lang.Object g,
                        boolean useDummies)

Place the nodes in the target environment according to their levels and sorting order which are specified in levelData. If "useDummies" is false, the dummy nodes are not used in the layout which produces a more compact layout: nodes in the same level may overlap and edges may cross over nodes. If "useDummies" is true, the dummy nodes are used in the layout. This method should be called after calculateLayout(t, g) which returns the levelData used by this method.

setOrientation

public void setOrientation(int o)

Set the orientation in which the graph is to be laid out, either VERTICAL or HORIZONTAL.

setRandomizedPlacement

public void setRandomizedPlacement(boolean flag)

Set whether or not placement will be randomized.

ASSERT

private void ASSERT(boolean b,
                    java.lang.String err)
             throws java.lang.RuntimeException

Assert the given condition and throw a runtime exception with the given string if the assertion fails.

Throws:

java.lang.RuntimeException

breakCycles

private void breakCycles(java.lang.Object composite,
                         GraphModel model)

Inefficient algorithm to break cycles in the graph.

checkAndBreak

private boolean checkAndBreak(java.lang.Object edge,
                              java.lang.Object node)

Return true if a cycle was broken.

addDummies

private void addDummies(LevelLayout.LevelData levelData)

Add dummy nodes between nodes along edges that span multiple levels. For example:

   o from            o from          o from
   |            |                  | <------ original edge
   |            |                  o dum1
   |    ==>   |            ==>          |          ==> ...
   |            o dum1          o dum2
   | <- e --> |                  |
  o to            o to          o to

 

makeLevels

private void makeLevels(LevelLayout.LevelData levelData)

Get the level of n in the graph. Requires that all nodes have LevelInfo attributes.

initialOrderNodes

private void initialOrderNodes(LevelLayout.LevelData levelData,
                               java.lang.Object maxNode)

Assign an initial ordering to the nodes. This starts with the "maximum" node (i.e. a node in the maximum level) and traverses its predecessors, adding them all to the level buckets. Then it adds all the other unmarked nodes.

addSubGraphReverseDFS

private void addSubGraphReverseDFS(LevelLayout.LevelData levelData,
                                   java.lang.Object node)

Add this node and all of its parent nodes to the levels array in a reverse DFS.

placeNodes

private void placeNodes(LevelLayout.LevelData levelData,
                        java.awt.geom.Rectangle2D vp,
                        boolean useDummies)

Place the nodes in the graph, based on the previous level calculations and the order of the nodes in the _levels array. Because we can make the placement either horiz. we need to be clever to share code. The algorithm is written as if it were vertical placement, and in the horizontal case, different values are used.

placeNode

private void placeNode(java.lang.Object node,
                       double x,
                       double y)

getLevelInfo

private LevelLayout.LevelInfo getLevelInfo(java.lang.Object node)

getLevel

private int getLevel(java.lang.Object node)

Get the level of n in the graph. Requires that node has LevelInfo attribute.

setLevel

private void setLevel(java.lang.Object node,
                      int l)

Set the level of n in the graph. Requires that node has LevelInfo attribute.

getUsage

private int getUsage(java.lang.Object node)

Get the level of n in the graph. Requires that node has LevelInfo attribute.

isDummy

private boolean isDummy(java.lang.Object node)

Return whether or not the given node is a dummy.

setUsage

private void setUsage(java.lang.Object node,
                      int val)

Set the level of n in the graph. Requires that node has LevelInfo attribute.

topoSort

private void topoSort(java.lang.Object node,
                      java.util.ArrayList topo)

Topologically sort from the given node and place the results in the given array list.

makeMeta

private void makeMeta(LevelLayout.LevelData levelData)

Create a meta-node and add it to the graph, connecting it to each existing node in the graph.

removeMeta

private void removeMeta(LevelLayout.LevelData levelData)

Remove the meta-node from the graph.

setVisited

public void setVisited(java.lang.Object node,
                       boolean val)

setAllVisited

public void setAllVisited(java.lang.Object composite,
                          boolean val)

isVisited

public boolean isVisited(java.lang.Object node)

computeLevels

private void computeLevels(LevelLayout.LevelData levelData)

Topological sort of graph and then set level numbers for the nodes.