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 drawing phase of the hierarchic layout algorithm (that is the assignment of nodes' coordinates) as described in "Visualisierungstechniken für den Compilerbau" (Georg Sander) mixed with techniques described in "A technique for drawing directed graphs" (Gansner et al).

• E. R. Gansner, E. Koutsofios, S. C. North and K.-P. Vo, A Technique for Drawing Directed Graphs, IEEE Transactions on Software Engineering, Vol. 19, pp. 214-230, 1993.
• G. Sander, Visualisierungstechniken für den Compilerbau, Ausgezeichnete Informatikdissertationen, GI-Dissertationspreis, pp. 114-127, 1998.

Field Summary

protected NodeMap	left A NodeMap that holds for each node an Object representing its left-hand side node in a layer or null if it is the leftmost node.
protected NodeMap	right A NodeMap that holds for each node an Object representing its right-hand side node in a layer or null if it is the rightmost node.

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()
Creates a new instance of PendularDrawer with default settings.

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., the maximum number of adjacent nodes (real ones and dummy nodes) with in-degree and out-degree 1.
protected double	getEdgeWeight(Edge edge) Returns a non-negative value representing the weight of a given edge.
protected double	getMaximumExtent(Node node, boolean toLeft) Calculates the maximum or minimum x-coordinate to which a given node can be assigned without violating the constraints.
protected double	getMinimalLayerDistance(Node node, boolean toLeft) Returns the minimum distance between two nodes of the same layer according to AbstractDrawer.getMinimalNodeDistance(),AbstractDrawer.getMinimalEdgeDistance() and AbstractDrawer.getMinimalMultiEdgeDistance().
protected double	getPendulumForce(Node node, EdgeCursor edges) Calculates the force applied to a given node by nodes provided by an EdgeCursor instance.
protected double	getPendulumForce(YCursor nodes, int direction) Calculates the force acting on all nodes given by the cursor.
protected double	getZ() Calculates the value of the function that this algorithm should minimize.
protected void	initializePositions(NodeList[] layerLists) Helper method which initializes the positions of the nodes of all layers.
protected void	initStructures() Initializes internal structures.
protected boolean	isSegmentNode(Node node) Determines whether or not a node is a so-called segment node.
protected void	minNode() Performs the minNode phase, i.e., a local optimization on one node at a time.
protected boolean	minPath(YList segments) Performs the minPath phase.
protected void	move(Node node, double distance) Moves a given node by a given distance.
protected void	move(YCursor cursor, double distance) Moves the nodes provided by the cursor by the given distance.
protected YList	partitionLayer(NodeList layer, int direction) Partitions a layer given by a NodeList by calculating the forces according to the given direction.
protected void	setLayoutGraph(LayoutGraph graph) Specifies the given graph.
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) Assigns the same x-coordinate to all the nodes given the first and the last cell in NodeList.
protected boolean	touches(Node node1, Node node2) Checks whether or not two adjacent nodes of a layer touch each other, i.e., their distance is smaller than the minimum layer distance.
protected double	verifyMovement(Node node, double distance) Assures that if a specific distance is applied to the x-coordinate of a given node, no given constraint will be violated.

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

A NodeMap that holds for each node an Object representing its right-hand side node in a layer or null if it is the rightmost node.

left

protected NodeMap left

A NodeMap that holds for each node an Object representing its left-hand side node in a layer or null if it is the leftmost node.

Constructor Detail

PendularDrawer

public PendularDrawer()

Creates a new instance of PendularDrawer with default settings.

Method Detail

initStructures

protected void initStructures()

Initializes internal structures.

This method is called first in assignCoordinates(NodeList[], DataProvider) and calculates the width of the grid for the bends (based on the maximum of the minimum multi-edge distance and the minimum edge distance) and the width of the grid for the nodes (based on the minimum node distance and the width of the grid for bends). It also initializes the NodeMaps that hold the right(left)-hand side nodes in a layer.

It may be overridden for custom calculation of the width of the grid for bends or for nodes.

The NodeMaps do not yet contain any values unless method initializePositions(NodeList[]) is called.

assignCoordinates

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

This is the main loop of this layout algorithm. It performs 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 phase i.e., a local optimization on one node at a time.
• MinPath phase, i.e., calling findChains() and minPath(YList).

Subclasses that wish to override this function to implement different behavior should implement a call to initStructures() and initializePositions(NodeList[]) before using the provided methods.

After the work is done, they should call disposeStructures().

Specified by:

assignCoordinates in class AbstractDrawer

Parameters:

layerLists - the array of NodeLists each of which contains nodes that belong to the same layer

layerID - the DataProvider that returns the zero-based index of the layer to which each node belongs

disposeStructures

protected void disposeStructures()

Cleans up previously allocated structures that were constructed by a call to initStructures().

It should be called after method assignCoordinates(NodeList[], DataProvider) has assigned the node coordinates.

See Also:

initStructures()

minPath

protected boolean minPath(YList segments)

Performs the minPath phase.

This method is called by assignCoordinates(NodeList[], DataProvider) as a final step and 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, without violating the constraints and without changing the coordinates of the nodes in the neighborhood of each segment. It may be overridden to support custom straightening of node chains.

Parameters:

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

Returns:

true if a change in any coordinate of the graph has occurred, false otherwise

See Also:

findChains()

findChains

protected YList findChains()

Finds chains of nodes, i.e., the maximum number of adjacent nodes (real ones and dummy nodes) with in-degree and out-degree 1.

This method is called in assignCoordinates(NodeList[], DataProvider) during the minPath(YList) MinPath} phase. It may be overridden for custom chain finding.

Returns:

a list of NodeLists containing each more than one nodes

See Also:

minPath(YList)

straightenPath

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

Assigns the same x-coordinate to all the nodes given the first and the last cell in NodeList.

The x-coordinates must lie within a range determined by range. If the first value of range is -Double.MAX_VALUE, the minimum distance between the nodes is used for the left border. Similarly, if the second value of range is Double.MAX_VALUE, the maximum distance between the nodes is used for the right border.

This method is called by minPath(YList) and performs the straightening of node chains. It may be overridden for custom implementations.

This method does not double-check whether the given range is valid for all nodes.

Parameters:

firstCell - the first node in a NodeList that should be assigned a new x-coordinate

lastCell - the last node in a NodeList (which must refer to same list as the one for firstCell) that should be assigned a new x-coordinate

range - an interval providing information of the legal range of x-coordinates that could be set

Returns:

true if this method has done any change to the coordinates, false otherwise

See Also:

minPath(YList)

isSegmentNode

protected boolean isSegmentNode(Node node)

Determines whether or not a node is a so-called segment node.

A node is called segment node if (in-degree == 1 && out-degree < 2) or (in-degree < 2 && out-degree == 1).

This method is called by findChains() method in order to distinguish the segment nodes. It may be overridden for custom segment node definitions.

Parameters:

node - the given node

Returns:

true if the given node is a segment node, false otherwise

minNode

protected void minNode()

Performs the minNode phase, i.e., a local optimization on one node at a time.

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 x-coordinate of a node has changed, all its neighbors are re-queued, if not already in the queue.

This method is called in assignCoordinates(NodeList[], DataProvider) after calling method partitionLayer(NodeList, int) and before minPath(YList). It may be overridden for custom implementations.

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 the following methods:

• getPendulumForce(YCursor, int)
• verifyMovement(Node, double)
• move(YCursor, double)

This method is called by assignCoordinates(NodeList[], DataProvider) after a layer has been partitioned and may be overridden for custom implementations.

Parameters:

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

direction - -1 if nodes in higher layers should be used for calculating 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 a NodeList by calculating the forces according to the given direction.

It is intended to be used with shakePartition(YList, int) method.

This method is called in assignCoordinates(NodeList[], DataProvider) during:

• Top-down phase calling partitionLayer(layerList[i] , -1) for each layer in top-down order.
• Bottom-up phase calling partitionLayer(layerList[i] , -1) for each layer in bottom-up order.
• Criss-cross phase calling partitionLayer(layerList[i] , 0) for each layer in top-down order.

It may be overridden for custom implementations.

Parameters:

layer - the NodeList containing the nodes of a single layer

direction - -1 if nodes in higher layers should be used for calculating 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 of a given layer, which can be treated as a single unit when moving

See Also:

getPendulumForce(YCursor, int), touches(Node, Node), shakePartition(YList, int)

setLayoutGraph

protected void setLayoutGraph(LayoutGraph graph)

Specifies the given graph.

Parameters:

graph - the graph

getPendulumForce

protected double getPendulumForce(Node node,
                                  EdgeCursor edges)

Calculates the force applied to a given node by nodes provided by an EdgeCursor instance.

This method is called by minNode() and getPendulumForce(YCursor, int) to calculate the force as the sum of the weighted differences of the x-coordinates. It may be overridden for custom calculations of the force on every node.

Parameters:

node - the given node for which the force will be calculated

edges - the EdgeCursor instance which determines which edges should be considered for the calculation

Returns:

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

See Also:

getEdgeWeight(Edge)

touches

protected boolean touches(Node node1,
                          Node node2)

Checks whether or not two adjacent nodes of a layer touch each other, i.e., their distance is smaller than the minimum layer distance.

This method is called in partitionLayer(NodeList, int) when the forces are calculated and checks whether or not the distance between two nodes is smaller than the minimum layer distance. It may be overridden if a different calculation of touching nodes is needed.

Parameters:

node1 - the first node

node2 - the second node

Returns:

true if the distance is smaller than the minimum layer distance, false otherwise

See Also:

getMinimalLayerDistance(Node,boolean)

verifyMovement

protected double verifyMovement(Node node,
                                double distance)

Assures that if a specific distance is applied to the x-coordinate of a given node, no given constraint will be violated.

It makes extensive use of getMinimalLayerDistance(Node, boolean)

This method is called in minNode() after the getPendulumForce(YCursor, int) is calculated. It may be overridden for custom verifications of the node movement.

Parameters:

node - the given node to be moved

distance - the distance which should be verified

Returns:

the distance which can be applied to the given without violating any constraint

See Also:

getMinimalLayerDistance(Node,boolean)

getPendulumForce

protected double getPendulumForce(YCursor nodes,
                                  int direction)

Calculates the force acting on all nodes given by the cursor.

This method is called by shakePartition(YList, int) to return the sum of the results of calls to getPendulumForce(Node, EdgeCursor) divided by the number of the nodes.

Parameters:

nodes - the nodes for which the force will be calculated

direction - -1 if nodes in higher layers should be used for calculating 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 given by the cursor, would minimize the force acting on them

move

protected void move(Node node,
                    double distance)

Moves a given node by a given distance.

This method is called in minNode() after the force of each node has been calculated. It is also called by move(YCursor, double) in order to move the nodes provided by the YCursor by the given distance.

For the movement, the distance and the width of the grid size for nodes and bends are taken into consideration. It may be overridden for custom calculation of the nodes' positions.

Parameters:

node - the given node

distance - the distance by which the x-coordinate should be modified

move

protected void move(YCursor cursor,
                    double distance)

Moves the nodes provided by the cursor by the given distance.

This method in turn calls move(Node, double) to delegate its work. It is called by shakePartition(YList, int) after the movement of the nodes based on the calculated forces is verified.

Parameters:

cursor - the nodes to be moved

distance - the distance by which the x-coordinate should be modified

See Also:

move(Node,double)

getZ

protected double getZ()

Calculates the value of the function that this algorithm should minimize.

Returns:

a positive value

getEdgeWeight

protected double getEdgeWeight(Edge edge)

Returns a non-negative value representing the weight of a given edge.

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 that maps a non-negative double value for each edge.

Parameters:

edge - the given edge

Returns:

a non-negative value representing the weight of a given edge

getMaximumExtent

protected double getMaximumExtent(Node node,
                                  boolean toLeft)

Calculates the maximum or minimum x-coordinate to which a given node can be assigned without violating the constraints.

Parameters:

node - the given node

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

Returns:

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

getMinimalLayerDistance

protected double getMinimalLayerDistance(Node node,
                                         boolean toLeft)

Returns the minimum distance between two nodes of the same layer according to AbstractDrawer.getMinimalNodeDistance(),AbstractDrawer.getMinimalEdgeDistance() and AbstractDrawer.getMinimalMultiEdgeDistance().

Parameters:

node - the given node

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

Returns:

the minimum distance between two nodes of the same layer

See Also:

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

initializePositions

protected void initializePositions(NodeList[] layerLists)

Helper method which initializes the positions of the nodes of all layers.

This method respects getMinimalLayerDistance(Node,boolean) and compacts the graph to the leftmost position (0).

Parameters:

layerLists - an array of NodeLists each containing nodes that belong to the same layer