y.layout.hierarchic
Class MedianLinearSegmentDrawer

java.lang.Object
  |
  +--y.layout.hierarchic.AbstractDrawer
        |
        +--y.layout.hierarchic.MedianLinearSegmentDrawer

All Implemented Interfaces:

Drawer

public class MedianLinearSegmentDrawer

extends AbstractDrawer

This class implements the third phase of the hierarchic layout algorithm. Edges are represented as polylines with at most two bends. The algorithm has linear running time and is based on the article [BK01]:

U. Brandes and B. Koepf, Fast and Simple Horizontal Coordinate Assignment, Proceedings of 9th Symposium of Graph Drawing, LNCS, 2001.

Field Summary

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

MedianLinearSegmentDrawer()

Method Summary

protected void	assignCoordinates(NodeList[] layerLists, DataProvider _layerID) Performs coordinate assignment.
protected void	calcShift(LayoutGraph g, Node v, double[] x) Calculate the shift values between the different classes of blocks.
protected void	dispose() Frees held resources.
protected void	horizontalCompaction(LayoutGraph g, double[] x, NodeList[] layerLists) Calculate coordinates.
protected void	init(Graph g, NodeList[] layerLists) Initializes data structures for all runs.
static void	markConflicts(NodeList[] layerLists, EdgeMap conflictMark, NodeMap dummyMap, int[] pos) Mark type 1 conflicts.
protected void	placeBlock(LayoutGraph g, Node v, double[] x) This method implements the function place_block(v) in Algorithm 3 in [BK01].
protected void	propagateCoordinates(LayoutGraph g) Writes the calculated x values in the layout graph.
protected void	reinit(Graph g, double[] x) Initializes data structures for one basic step.
void	verticalAlignment(LayoutGraph g, NodeList[] layerLists) Calculates vertical alignment.

Methods inherited from class y.layout.hierarchic.AbstractDrawer

assignCoordinates, assignYCoords, assignYCoords, 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

Constructor Detail

MedianLinearSegmentDrawer

public MedianLinearSegmentDrawer()

Method Detail

assignCoordinates

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

Performs coordinate assignment.

Specified by:

assignCoordinates in class AbstractDrawer

init

protected void init(Graph g,
                    NodeList[] layerLists)

Initializes data structures for all runs.

reinit

protected void reinit(Graph g,
                      double[] x)

Initializes data structures for one basic step.

Parameters:

x - the array where the coordinates will be stored.

markConflicts

public static void markConflicts(NodeList[] layerLists,
                                 EdgeMap conflictMark,
                                 NodeMap dummyMap,
                                 int[] pos)

Mark type 1 conflicts. This method corresponds to Algorithm 1 in [BK01].

Parameters:

layerLists - the list of layers.

conflictMark - used to mark the conflicting edges.

dummyMap - map which returns true for bends, false otherwise.

pos - is indexed by the index method of node and returns the rank of a node inside the layer which contains the node.

verticalAlignment

public void verticalAlignment(LayoutGraph g,
                              NodeList[] layerLists)

Calculates vertical alignment. This method corresponds to Algorithm 2 in [BK01].

Parameters:

g - the graph for which the layout is calculated.

layerLists - the list of layers.

horizontalCompaction

protected void horizontalCompaction(LayoutGraph g,
                                    double[] x,
                                    NodeList[] layerLists)

Calculate coordinates. This method corresponds to Algorithm 3 in [BK01].

Parameters:

g - the graph for which the layout is calculated.

x - the array where the result is stored.

placeBlock

protected void placeBlock(LayoutGraph g,
                          Node v,
                          double[] x)

This method implements the function place_block(v) in Algorithm 3 in [BK01]. It differs from the paper version, since it does not calculate the shift values, they are calculated by calcShift().

calcShift

protected void calcShift(LayoutGraph g,
                         Node v,
                         double[] x)

Calculate the shift values between the different classes of blocks. Added to BK[01] because this is not handled correctly.

propagateCoordinates

protected void propagateCoordinates(LayoutGraph g)

Writes the calculated x values in the layout graph.

dispose

protected void dispose()

Frees held resources.

Overrides:

dispose in class AbstractDrawer