diva.graph.layout

Class LevelLayout

java.lang.Object

diva.graph.layout.AbstractGlobalLayout

diva.graph.layout.LevelLayout

All Implemented Interfaces:

GlobalLayout

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 70398 2014-10-22 23:44:32Z cxh $

Author:

Michael Shilman

Accepted Rating:

Red

Nested Class Summary

Nested Classes

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

Field Summary

Fields

Modifier and Type	Field and Description
protected int	_orientation Keep track of the orientation; vertical by default.
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

Constructors

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

Method Summary

Modifier and Type	Method and Description
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.
LevelLayout.LevelData	calculateLayout(java.lang.Object composite) This method performs levelizing layout on the given composite.
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.
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.
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.
void	setAllVisited(java.lang.Object composite, boolean val)
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.
void	setVisited(java.lang.Object node, boolean val)

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.

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.

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)