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 fuer 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 layoutalgorithm.
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)
          This method 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()
          This method calculates the function whose value 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 wether a node is a socalled segmentnode.
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 wether 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 wether 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 layoutalgorithm. For now it does the following loop: 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:
PendularDrawer.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 neighbourhood 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:
PendularDrawer.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:
PendularDrawer.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 doublecheck 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:
PendularDrawer.minPath(YList)

isSegmentNode

protected boolean isSegmentNode(Node n)
Helper method that determines wether a node is a socalled segmentnode.

Parameters:
n - the Node
Returns:
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 layoutgraph. For each Node n that is popped off the queue it performs a call to if the node has changed its x-coordinate all its neigbours 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:

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:
PendularDrawer.partitionLayer(NodeList,int), PendularDrawer.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. It uses the functionalities of the methods getPendulumForce(NodeCursor, int direction) and touches(Node,Node).

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:
PendularDrawer.getPendulumForce(YCursor, int), PendularDrawer.touches(Node,Node), PendularDrawer.shakePartition(YList,int direction)

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:
PendularDrawer.getEdgeWeight(Edge)

touches

protected boolean touches(Node v1,
                          Node v2)
Helper method which checks wether 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:
PendularDrawer.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:
PendularDrawer.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 wether 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:
PendularDrawer.move(Node,double)

getZ

protected double getZ()
This method calculates the function whose value this algorithm should minimize.

Returns:
a positive value

getEdgeWeight

protected double getEdgeWeight(Edge e)
This method 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 edgeweights 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

© Copyright 2000-2003,
yWorks GmbH.
All rights reserved.

2003