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 (i.e., the assignment of nodes' coordinates).

Edges are represented as polyline segments with at most two bends per edge. 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()
Creates an instance of MedianLinearSegmentDrawer with default settings.

Method Summary

protected void	assignCoordinates(NodeList[] layerLists, DataProvider layerID) Assigns the coordinates to the nodes of the given graph.
protected void	dispose() Cleans up previously allocated structures.
protected void	horizontalCompaction(LayoutGraph graph, double[] x, NodeList[] layerLists) Calculates the coordinates of the graph.
protected void	init(Graph graph, NodeList[] layerLists) Initializes the data structures for all runs.
static void	markConflicts(NodeList[] layerLists, EdgeMap conflictMark, NodeMap dummyMap, int[] pos) Marks conflicts occurred when a non-inner segment crosses an inner segment.
protected void	propagateCoordinates(LayoutGraph graph) Propagates the calculated x-coordinates to the nodes of the graph.
protected void	reinit(Graph graph, double[] x) Initializes the data structures for one basic step.
void	verticalAlignment(LayoutGraph graph, NodeList[] layerLists) Calculates a 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()

Creates an instance of MedianLinearSegmentDrawer with default settings.

Method Detail

assignCoordinates

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

Assigns the coordinates to the nodes of the given graph.

The procedure has three steps (see U. Brandes and B. Koepf, 2001):

• Each node is aligned either with its median upper or its median lower neighbor while alignment conflicts are resolved (this is performed four times).
• Aligned nodes obtain the same horizontal coordinate and all nodes are placed as close as possible to the next nodes in the preferred horizontal direction of the alignment (this is performed four times).
• The four assignments are combined to balance their biases.

This method is called by AbstractDrawer.assignCoordinates(LayoutGraph, NodeList[], DataProvider) after the AbstractDrawer.initializeDistancesToNextNode(NodeList[]) has been called and can be overridden for custom calculation of the horizontal node positions.

Specified by:

assignCoordinates in class AbstractDrawer

Parameters:

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

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

init

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

Initializes the data structures for all runs.

Parameters:

graph - the input graph

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

reinit

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

Initializes the data structures for one basic step.

Parameters:

graph - the input graph

x - the array in which the x-coordinates will be stored

markConflicts

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

Marks conflicts occurred when a non-inner segment crosses an inner segment.

An inner segment is a segment between two dummy vertices. This method corresponds to Algorithm 1 in [BK01].

Parameters:

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

conflictMark - the EdgeMap that returns a boolean value for each edge determining whether or not an edge is marked as conflict

dummyMap - the NodeMap that returns a boolean value for each node determining whether or not the node is a dummy node (i.e., a node that corresponds to a bend)

pos - an array indexed by the index of a node and returns the rank of a node inside the layer to which it belongs

verticalAlignment

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

Calculates a vertical alignment.

This method corresponds to Algorithm 2 in [BK01].

Parameters:

graph - the input graph

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

horizontalCompaction

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

Calculates the coordinates of the graph.

This method corresponds to Algorithm 3 in [BK01].

Parameters:

graph - the input graph

x - the array in which the x-coordinates will be stored

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

propagateCoordinates

protected void propagateCoordinates(LayoutGraph graph)

Propagates the calculated x-coordinates to the nodes of the graph.

Parameters:

graph - the graph

dispose

protected void dispose()

Cleans up previously allocated structures.

Overrides:

dispose in class AbstractDrawer