
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.layout.hierarchic.AbstractDrawer y.layout.hierarchic.PendularDrawer
public class PendularDrawer
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).
Field Summary  

protected NodeMap 
left
A NodeMap that holds for each node an Object representing its lefthand 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 righthand 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 indegree and outdegree 1 . 
protected double 
getEdgeWeight(Edge edge)
Returns a nonnegative value representing the weight of a given edge. 
protected double 
getMaximumExtent(Node node,
boolean toLeft)
Calculates the maximum or minimum xcoordinate 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 socalled 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 xcoordinate 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 xcoordinate of a given node, no given constraint will be violated. 
Methods inherited from class java.lang.Object 

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

protected NodeMap right
NodeMap
that holds for each node an Object
representing its righthand side node in a layer
or null
if it is the rightmost node.
protected NodeMap left
NodeMap
that holds for each node an Object
representing its lefthand side node in a layer
or null
if it is the leftmost node.
Constructor Detail 

public PendularDrawer()
PendularDrawer
with default settings.
Method Detail 

protected void initStructures()
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 multiedge 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 NodeMap
s 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.
NodeMap
s do not yet contain any values unless method
initializePositions(NodeList[])
is called.protected void assignCoordinates(NodeList[] layerLists, DataProvider layerID)
partitionLayer(layerList[i] , 1)
and shakePartition(partition,1)
for each layer in topdown order.
partitionLayer(layerList[i] , 1)
and shakePartition(partition,1)
for each layer in bottomup order.
partitionLayer(layerList[i] , 0)
and shakePartition(partition,0)
for each layer in topdown order.
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()
.
assignCoordinates
in class AbstractDrawer
layerLists
 the array of NodeList
s each of which contains nodes that belong to the same layerlayerID
 the DataProvider
that returns the zerobased index of the layer to which each node belongsprotected void disposeStructures()
initStructures()
.
It should be called after method assignCoordinates(NodeList[], DataProvider)
has assigned the node
coordinates.
initStructures()
protected boolean minPath(YList segments)
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 NodeList
s, by sequentially assigning
the same xcoordinate 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.
segments
 a list
of NodeList
s each containing a chain of nodes
true
if a change in any coordinate of the graph has occurred, false
otherwisefindChains()
protected YList findChains()
1
.
This method is called in assignCoordinates(NodeList[], DataProvider)
during the
minPath(YList)
MinPath} phase. It may be overridden for custom chain finding.
list
of NodeList
s containing each more than one nodesminPath(YList)
protected boolean straightenPath(ListCell firstCell, ListCell lastCell, double[] range)
NodeList
.
The xcoordinates 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.
firstCell
 the first node in a NodeList
that should be assigned a new xcoordinatelastCell
 the last node in a NodeList
(which must refer to same list as the one for firstCell
)
that should be assigned a new xcoordinaterange
 an interval providing information of the legal range of xcoordinates that could be set
true
if this method has done any change to the coordinates, false
otherwiseminPath(YList)
protected boolean isSegmentNode(Node node)
A node is called segment node if (indegree == 1 && outdegree < 2)
or
(indegree < 2 && outdegree == 1)
.
This method is called by findChains()
method in order to distinguish the segment nodes. It may be
overridden for custom segment node definitions.
node
 the given node
true
if the given node is a segment node, false
otherwiseprotected void minNode()
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 xcoordinate of a node has changed, all its neighbors are requeued, 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.
protected void shakePartition(YList partition, int direction)
It uses the functionality of the following methods:
This method is called by assignCoordinates(NodeList[], DataProvider)
after
a layer has been partitioned
and may be overridden for custom
implementations.
partition
 a YList
of NodeList
s each containing at least one node
belonging to a single layerdirection
 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 usedpartitionLayer(NodeList,int)
,
getPendulumForce(YCursor, int)
protected YList partitionLayer(NodeList layer, int direction)
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:
partitionLayer(layerList[i] , 1)
for each layer in topdown order.partitionLayer(layerList[i] , 1)
for each layer in bottomup order.partitionLayer(layerList[i] , 0)
for each layer in topdown order.It may be overridden for custom implementations.
layer
 the NodeList
containing the nodes of a single layerdirection
 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
NodeList
s each containing adjacent nodes of a given layer,
which can be treated as a single unit when movinggetPendulumForce(YCursor, int)
,
touches(Node, Node)
,
shakePartition(YList, int)
protected void setLayoutGraph(LayoutGraph graph)
graph
 the graphprotected double getPendulumForce(Node node, EdgeCursor edges)
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 xcoordinates. It may be overridden for custom calculations of the
force on every node.
node
 the given node for which the force will be calculatededges
 the EdgeCursor
instance which determines which edges should be considered for the calculation
v
) would minimize, if applied,
the force on v
getEdgeWeight(Edge)
protected boolean touches(Node node1, Node node2)
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.
node1
 the first nodenode2
 the second node
true
if the distance is smaller than the minimum layer distance
,
false
otherwisegetMinimalLayerDistance(Node,boolean)
protected double verifyMovement(Node node, double distance)
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.
node
 the given node to be moveddistance
 the distance which should be verified
getMinimalLayerDistance(Node,boolean)
protected double getPendulumForce(YCursor nodes, int direction)
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.
nodes
 the nodes for which the force will be calculateddirection
 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
cursor
,
would minimize the force acting on themprotected void move(Node node, double 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.
node
 the given nodedistance
 the distance by which the xcoordinate should be modifiedprotected void move(YCursor cursor, double distance)
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
.
cursor
 the nodes to be moveddistance
 the distance by which the xcoordinate should be modifiedmove(Node,double)
protected double getZ()
protected double getEdgeWeight(Edge edge)
In this implementation:
1
.segmentEndFactor * 1
.segmentFactor * 1
.
One could implement edge weights by supplying an EdgeMap
that maps a nonnegative double value for
each edge.
edge
 the given edge
protected double getMaximumExtent(Node node, boolean toLeft)
node
 the given nodetoLeft
 true
if the minimum xcoordinate should be calculated;
false
if the maximum xcoordinate should be calculated
protected double getMinimalLayerDistance(Node node, boolean toLeft)
AbstractDrawer.getMinimalNodeDistance()
,AbstractDrawer.getMinimalEdgeDistance()
and AbstractDrawer.getMinimalMultiEdgeDistance()
.
node
 the given nodetoLeft
 true
if the minimum xcoordinate should be calculated;
false
if the maximum xcoordinate should be calculated
AbstractDrawer.getMinimalMultiEdgeDistance()
,
AbstractDrawer.getMinimalNodeDistance()
,
AbstractDrawer.getMinimalEdgeDistance()
protected void initializePositions(NodeList[] layerLists)
This method respects getMinimalLayerDistance(Node,boolean)
and compacts the graph to the
leftmost position (0)
.
layerLists
 an array of NodeList
s each containing nodes that belong to the same layer

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 