y.layout.hierarchic
Class PendularDrawer

java.lang.Object
  y.layout.hierarchic.AbstractDrawer
      y.layout.hierarchic.PendularDrawer

All Implemented Interfaces:

Drawer

public class PendularDrawer
extends AbstractDrawer

This class implements the third phase of the Sugiyama layout algorithm as described in "Visualisierungstechniken für den Compilerbau" (Georg Sander) mixed with techniques as described in "A technique for drawing directed graphs" (Gansner et al).

Field Summary

protected NodeMap	left map that maps the left node for each node in a layer or null if it is the leftmost
protected NodeMap	right map that maps the right node for each node in a layer or null if it is the rightmost

Fields inherited from class y.layout.hierarchic.AbstractDrawer

distanceToNextNode, dummyMap, edgeLengthKey, graph, minimalEdgeDistance, minimalLayerDistance, minimalMultiEdgeDistance, minimalNodeDistance

Fields inherited from interface y.layout.hierarchic.Drawer

NODE_BORDER_BOTTOM, NODE_BORDER_LEFT, NODE_BORDER_RIGHT, NODE_BORDER_TOP, NODE_DISTANCE

Constructor Summary

PendularDrawer()
empty constructor, does nothing

Method Summary

protected void	assignCoordinates(NodeList[] layerLists, DataProvider layerID) This is the main loop of this layout algorithm.
protected void	disposeStructures() Cleans up previously allocated structures, that were constructed by a call to initStructures
protected YList	findChains() Finds chains of nodes, i.e. maximum number of adjacent nodes (real ones and dummy nodes) have indegree and outdegree 1.
protected double	getEdgeWeight(Edge e) Returns a non-negative value for each Edge e.
protected double	getMaximumExtent(Node n, boolean toLeft) Calculates the highest or lowest x-coordinate the Node n can be assigned to, without breaking the constraints.
protected double	getMinimalLayerDistance(Node n, boolean toLeft) Returns the minimum distance between two Nodes on the same layer according to getMinimalNodeDistance(), getMinimalEdgeDistance() and getMinimalMultiEdgeDistance().
protected double	getPendulumForce(Node v, EdgeCursor ec) Helper method which calculates the force that all nodes given by EdgeCursor apply to v.
protected double	getPendulumForce(YCursor cursor, int direction) Helper method which calculates the force acting on all nodes given by the cursor.
protected double	getZ() Calculates the value of the function this algorithm should minimize.
protected void	initializePositions(NodeList[] layerList) Helper method which initializes the positions of the nodes in all layers.
protected void	initStructures() used to initialize internal structures such as NodeMap right and NodeMap left bendGridWidth and nodeGridWidth.
protected boolean	isSegmentNode(Node n) Helper method that determines whether a node is a so-called segment node.
protected void	minNode() Performs the minNode phase.
protected boolean	minPath(YList segments) Performs the minPath phase.
protected void	move(Node n, double distance) Helper method which moves a given node by a given amount if the useGrid is set to true, this method will snap the new node position to the appropriate grid, i.e. it decides whether to use nodeGridWith or bendGridWith
protected void	move(YCursor nodes, double distance) Helper method which moves the nodes provided by the Cursor nodes by the given amount.
protected YList	partitionLayer(NodeList layer, int direction) Partitions a layer given by its NodeList by calculating the forces according to the given direction.
protected void	setLayoutGraph(LayoutGraph g)
protected void	shakePartition(YList partition, int direction) Shakes a given partition of a Layer, i.e. it calculates the forces for each part of the partition and applies them if possible.
protected boolean	straightenPath(ListCell firstCell, ListCell lastCell, double[] range) Helper method for use in minPath.
protected boolean	touches(Node v1, Node v2) Helper method which checks whether two adjacent nodes on a layer touch each other, i.e. their distance is smaller than getMinimalLayerDistance(v1, ...)
protected double	verifyMovement(Node n, double distance) Assures that if distance was applied to the n's x-coordinate no given constraint gets broken.

Methods inherited from class y.layout.hierarchic.AbstractDrawer

assignCoordinates, assignYCoords, assignYCoords, dispose, getBottomBorder, getBottomHalf, getBottomY, getDistanceToNextNode, getFullHeight, getFullWidth, getLeftBorder, getLeftHalf, getLeftX, getMinimalEdgeDistance, getMinimalLayerDistance, getMinimalMultiEdgeDistance, getMinimalNodeDistance, getRightBorder, getRightHalf, getRightX, getTopBorder, getTopHalf, getTopY, initializeDistancesToNextNode, setDummyMap, setEdgeLengthKey, setMinimalEdgeDistance, setMinimalLayerDistance, setMinimalMultiEdgeDistance, setMinimalNodeDistance

Methods inherited from class java.lang.Object

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

Field Detail

right

protected NodeMap right

map that maps the right node for each node in a layer or null if it is the rightmost

left

protected NodeMap left

map that maps the left node for each node in a layer or null if it is the leftmost

Constructor Detail

PendularDrawer

public PendularDrawer()

empty constructor, does nothing

Method Detail

initStructures

protected void initStructures()

used to initialize internal structures such as NodeMap right and NodeMap left bendGridWidth and nodeGridWidth. Note that the NodeMaps do not yet contain any values unless you call initializePositions()

assignCoordinates

protected void assignCoordinates(NodeList[] layerLists,
                                 DataProvider layerID)

This is the main loop of this layout algorithm. For now it does the following loop:

• for each round do
  • top down phase, i.e. calling partitionLayer(layerList[i] , -1) and shakePartition(partition,-1) for each layer in top down order
  • bottom up phase, i.e. calling partitionLayer(layerList[i] , -1) and shakePartition(partition,-1) for each layer in bottom up order
  • criss cross phase, i.e. calling partitionLayer(layerList[i] , 0) and shakePartition(partition,0) for each layer in top down order
  • performing minNode
• minPath phase, i.e. calling findChains() and minPath(chains)

Subclasses that wish to override this function to implement different behaviour should implement a call to initStructures() and initializePositions(layerLists) before using the provided methods. After the work is done, they should call disposeStructures(g).

Specified by:

assignCoordinates in class AbstractDrawer

Parameters:

layerLists - a list of all the nodes for each layer, to determine their relative positions

disposeStructures

protected void disposeStructures()

Cleans up previously allocated structures, that were constructed by a call to initStructures

See Also:

initStructures()

minPath

protected boolean minPath(YList segments)

Performs the minPath phase. It tries to straighten the chains given by a list of NodeLists, by sequentially assigning the same x- coordinate to as many adjacent nodes of each chain as possible, not violating the constraints and not changing coordinates of nodes in the neighborhood of each segment

Parameters:

segments - a list of NodeList each containing a chain of nodes

Returns:

true iff there was a change in any coordinate of the graph

See Also:

findChains()

findChains

protected YList findChains()

Finds chains of nodes, i.e. maximum number of adjacent nodes (real ones and dummy nodes) have indegree and outdegree 1.

Returns:

a list of NodeLists containing each more than 1 nodes

See Also:

minPath(YList)

straightenPath

protected boolean straightenPath(ListCell firstCell,
                                 ListCell lastCell,
                                 double[] range)

Helper method for use in minPath. It will assign the same x-coordinate to all the nodes given the first and the last cell in NodeList. Note that this method does not double-check whether the given range is valid for all nodes.

Parameters:

firstCell - this determines the first Node in a NodeList which should be assigned a new x-coordinate

lastCell - this determines the last Node in a NodeList (which must be same List as the one for firstCell) which should be assigned a new x-coordinate

range - an interval providing information of the legal range, the Nodes x-coordinates could be set to. The values can can be smaller than (-Double.MAX_VALUE) for the left border and greater than Double.MAX_VALUE for the right one

Returns:

true iff this method has done any change to the graphs coordinates

See Also:

minPath(YList)

isSegmentNode

protected boolean isSegmentNode(Node n)

Helper method that determines whether a node is a so-called segment node.

Parameters:

n - the Node

Returns:

true iff (inDegree == 1 && outDegree < 2) || (outDegree == 1 && inDegree < 2)

minNode

protected void minNode()

Performs the minNode phase. It uses a queue, which is initially filled with all nodes in the layout graph. For each Node n that is popped off the queue it performs a call to

• force = getPendulumForce(n, n.edges)
• force = verifyMovement(n,force)
• move(n, force)

If the node has changed its x-coordinate all its neighbors are requeued, if not already in the queue.

shakePartition

protected void shakePartition(YList partition,
                              int direction)

Shakes a given partition of a Layer, i.e. it calculates the forces for each part of the partition and applies them if possible. It uses the functionality of these methods:

• getPendulumForce(NodeCursor, int direction)
• verifyMovement(Node, double force)
• move(NodeCursor, double force)

Parameters:

partition - a List of NodeLists each containing at least one node belonging to a single layer

direction - -1 if nodes in higher layers should be used to calculate the forces, 1 if nodes in lower layers should be used, 0 if both surrounding layers should be used

See Also:

partitionLayer(NodeList,int), getPendulumForce(YCursor, int)

partitionLayer

protected YList partitionLayer(NodeList layer,
                               int direction)

Partitions a layer given by its NodeList by calculating the forces according to the given direction. This one is intended for use with the shakePartition() method.

Parameters:

layer - the layer which shall be partitioned

direction - -1 if nodes in higher layers should be used to calculate the forces, 1 if nodes in lower layers should be used, 0 if both surrounding layers should be used

Returns:

a list of NodeLists each containing adjacent nodes in that layer, which can be treated as a single unit when moving

See Also:

getPendulumForce(y.base.YCursor, int), touches(y.base.Node, y.base.Node), shakePartition(y.base.YList, int)

setLayoutGraph

protected void setLayoutGraph(LayoutGraph g)

getPendulumForce

protected double getPendulumForce(Node v,
                                  EdgeCursor ec)

Helper method which calculates the force that all nodes given by EdgeCursor apply to v. The force is calculated by the sum of the weighted differences of the x-coordinates.

Parameters:

v - the node for which the force will be calculated

ec - the EdgeCursor which determines which edges should be considered in the calculation

Returns:

a force, i.e. a signed value, which (if added to the x-coordinate of v) would minimize the force on v if applied.

See Also:

getEdgeWeight(Edge)

touches

protected boolean touches(Node v1,
                          Node v2)

Helper method which checks whether two adjacent nodes on a layer touch each other, i.e. their distance is smaller than getMinimalLayerDistance(v1, ...)

Parameters:

v1 - one node

v2 - another node

Returns:

true iff their distance is smaller than getMinimalLayerDistance+EPSILON

See Also:

getMinimalLayerDistance(Node,boolean)

verifyMovement

protected double verifyMovement(Node n,
                                double distance)

Assures that if distance was applied to the n's x-coordinate no given constraint gets broken. It makes extensive use of getMinimalLayerDistance(v1, ...)

Parameters:

n - the node to be moved

distance - the distance which shall be verified

Returns:

the distance which can be applied to n without breaking any constraint

See Also:

getMinimalLayerDistance(Node,boolean)

getPendulumForce

protected double getPendulumForce(YCursor cursor,
                                  int direction)

Helper method which calculates the force acting on all nodes given by the cursor. The force is calculated by the sum of the results of calls to getPendulumForce(Node, int) divided by the number of the nodes.

Parameters:

cursor - the nodes for which the force will be calculated

direction - -1 if nodes in higher layers should be used to calculate the forces, 1 if nodes in lower layers should be used, 0 if both surrounding layers should be used

Returns:

a force, i.e. a signed value, which, if applied to the nodes in cursor, would minimize the force acting on them.

move

protected void move(Node n,
                    double distance)

Helper method which moves a given node by a given amount if the useGrid is set to true, this method will snap the new node position to the appropriate grid, i.e. it decides whether to use nodeGridWith or bendGridWith

Parameters:

n - the node

distance - the distance that shall be added to the nodes x-coordinate

move

protected void move(YCursor nodes,
                    double distance)

Helper method which moves the nodes provided by the Cursor nodes by the given amount. This one in turn calls move(Node,double) to delegate its work.

Parameters:

nodes - the nodes

distance - the distance that shall be added to the nodes x-coordinate

See Also:

move(Node,double)

getZ

protected double getZ()

Calculates the value of the function this algorithm should minimize.

Returns:

a positive value.

getEdgeWeight

protected double getEdgeWeight(Edge e)

Returns a non-negative value for each Edge e. In this implementation edges between two real nodes result in an edge weight of 1. Edges between one dummy and one real node result in an edge weight of segmentEndFactor * 1. Edges between two dummy nodes get an edge weight of segmentFactor * 1. One could implement edge weights by supplying an EdgeMap mapping a non-negative numeric value for each edge.

Parameters:

e - the edge

Returns:

a non-negative value

getMaximumExtent

protected double getMaximumExtent(Node n,
                                  boolean toLeft)

Calculates the highest or lowest x-coordinate the Node n can be assigned to, without breaking the constraints.

Parameters:

n - the node

toLeft - true if the minimum x-coordinate shall be calculated; false for the maximum x-coordinate

Returns:

the maximum/minimum extent of the node's center x-coordinate

getMinimalLayerDistance

protected double getMinimalLayerDistance(Node n,
                                         boolean toLeft)

Returns the minimum distance between two Nodes on the same layer according to getMinimalNodeDistance(), getMinimalEdgeDistance() and getMinimalMultiEdgeDistance().

Parameters:

n - the node

toLeft - true if the minimum x-coordinate shall be calculated; false for the maximum x-coordinate

Returns:

the maximum/minimum extent of the node's center x-coordinate

See Also:

AbstractDrawer.getMinimalMultiEdgeDistance(), AbstractDrawer.getMinimalNodeDistance(), AbstractDrawer.getMinimalEdgeDistance()

initializePositions

protected void initializePositions(NodeList[] layerList)

Helper method which initializes the positions of the nodes in all layers. This method respects getMinimalLayerDistance(Node,boolean) and compacts the graph to the leftmost position (0)

Parameters:

layerList - an array of NodeLists each corresponding to a single layer