y.layout.hierarchic.incremental
Class DefaultLayerSequencer

java.lang.Object
  y.layout.hierarchic.incremental.DefaultLayerSequencer

All Implemented Interfaces:

Sequencer

public class DefaultLayerSequencer
extends java.lang.Object
implements Sequencer

This class is a Sequencer implementation that performs the second phase of the Sugiyama algorithm.

It minimizes the crossings in the diagram by using either the barycentric or median heuristic.

Field Summary

static byte	BARYCENTER_HEURISTIC A weight assignment specifier based on a barycenter heuristic.
static byte	MEDIAN_HEURISTIC A weight assignment specifier based on a median heuristic.

Constructor Summary

DefaultLayerSequencer()
Creates a new instance of DefaultLayerSequencer.

Method Summary

protected double	getCrossingCost(Edge edge1, Edge edge2, LayoutDataProvider layoutDataProvider) Returns the cost of an edge crossing between the two given edges.
long	getMaximalDuration() Returns the time limit (in milliseconds) set for this sequencer per execution.
int	getRandomizationRounds() Returns the number of randomized rounds that this algorithm performs, if there was no optimal solution.
byte	getWeightHeuristic() Returns the weight heuristic that should be used.
boolean	isGroupTranspositionEnabled() Returns whether or not an additional crossing minimization heuristic should be used in the presence of grouped graphs.
boolean	isTranspositionEnabled() Returns whether or not to apply an additional crossing minimization heuristic.
void	sequenceNodeLayers(LayoutGraph graph, Layers glayers, LayoutDataProvider ldp, ItemFactory itemFactory) Calculates the sequence of the nodes within each layer.
void	setGroupTranspositionEnabled(boolean b) Specifies whether or not an additional crossing minimization heuristic should be used in the presence of grouped graphs.
void	setMaximalDuration(long msec) Specifies the time limit (in milliseconds) set for this sequencer per execution.
void	setRandomizationRounds(int randomizationRounds) Specifies the number of randomized rounds that this algorithm performs, if there was no optimal solution.
void	setTranspositionEnabled(boolean b) Specifies whether or not to apply an additional crossing minimization heuristic.
void	setWeightHeuristic(byte h) Specifying the weight heuristic that should be used.

Methods inherited from class java.lang.Object

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

Field Detail

BARYCENTER_HEURISTIC

public static final byte BARYCENTER_HEURISTIC

A weight assignment specifier based on a barycenter heuristic.

The position of a node within a layer will be determined by the barycenter of its successor (downward pass) and predecessor (upward pass) nodes.

See Also:

setWeightHeuristic(byte), Constant Field Values

Sample Graph:

MEDIAN_HEURISTIC

public static final byte MEDIAN_HEURISTIC

A weight assignment specifier based on a median heuristic.

The position of a node within a layer will be determined by the median position of its successor (downward pass) and predecessor (upward pass) nodes.

See Also:

setWeightHeuristic(byte), Constant Field Values

Sample Graph:

Constructor Detail

DefaultLayerSequencer

public DefaultLayerSequencer()

Creates a new instance of DefaultLayerSequencer.

Method Detail

setTranspositionEnabled

public void setTranspositionEnabled(boolean b)

Specifies whether or not to apply an additional crossing minimization heuristic.

Activating this heuristic can reduce the overall number of edge crossings. On the other hand, it may increase the running time.

Default Value:

The default value is true. The transposition rule is active.

Parameters:

b - true if the crossing minimization heuristic should be applied, false otherwise

Sample Graphs:

Transposition disabled - five crossings

Transposition enabled - four crossings

isTranspositionEnabled

public boolean isTranspositionEnabled()

Returns whether or not to apply an additional crossing minimization heuristic.

Activating this heuristic can reduce the overall number of edge crossings. On the other hand, it may increase the running time.

Returns:

true if the crossing minimization heuristic is applied, false otherwise

See Also:

setTranspositionEnabled(boolean)

setGroupTranspositionEnabled

public void setGroupTranspositionEnabled(boolean b)

Specifies whether or not an additional crossing minimization heuristic should be used in the presence of grouped graphs.

Activating this heuristic can reduce the overall number of edge crossings in grouped graphs. On the other hand, it may increase running time.

Default Value:

The default value is false. The group transposition rule is disabled.

Parameters:

b - true if the crossing minimization heuristic should be applied, false otherwise

Sample Graphs:

Group transposition disabled - one crossing

Group transposition disabled - zero crossings

isGroupTranspositionEnabled

public boolean isGroupTranspositionEnabled()

Returns whether or not an additional crossing minimization heuristic should be used in the presence of grouped graphs.

Activating this heuristic can reduce the overall number of edge crossings in grouped graphs. On the other hand, it may increase running time.

Returns:

true if the crossing minimization heuristic should be applied, false otherwise

See Also:

setGroupTranspositionEnabled(boolean)

setWeightHeuristic

public void setWeightHeuristic(byte h)

Specifying the weight heuristic that should be used.

Default Value:

The default value is BARYCENTER_HEURISTIC. A barycenter heuristic is used.

Parameters:

h - one of the predefined weight heuristics

Throws:

java.lang.IllegalArgumentException - if the constant is unknown

getWeightHeuristic

public byte getWeightHeuristic()

Returns the weight heuristic that should be used.

Returns:

one of the predefined weight heuristics

See Also:

setWeightHeuristic(byte)

getMaximalDuration

public long getMaximalDuration()

Returns the time limit (in milliseconds) set for this sequencer per execution.

Values have to be greater than or equal to 0.

Returns:

a non-negative value that specifies the time limit

getRandomizationRounds

public int getRandomizationRounds()

Returns the number of randomized rounds that this algorithm performs, if there was no optimal solution.

Values have to be greater than or equal to 0.

Returns:

the number of additional rounds

See Also:

setRandomizationRounds(int)

setRandomizationRounds

public void setRandomizationRounds(int randomizationRounds)

Specifies the number of randomized rounds that this algorithm performs, if there was no optimal solution.

Values have to be greater than or equal to 0.

Default Value:

The default value is 50. The number of randomized rounds is 50, if the maximum duration hasn't been reduced below its default value. Otherwise, 14 rounds are performed.

Parameters:

randomizationRounds - the given number of additional rounds

Throws:

java.lang.IllegalArgumentException - if a negative value is given

setMaximalDuration

public void setMaximalDuration(long msec)

Specifies the time limit (in milliseconds) set for this sequencer per execution.

Values have to be greater than or equal to 0.

Default Value:

The default value is 10000.

Parameters:

msec - a non-negative value that specifies the time limit

Throws:

java.lang.IllegalArgumentException - if the maximum duration is negative.

getCrossingCost

protected double getCrossingCost(Edge edge1,
                                 Edge edge2,
                                 LayoutDataProvider layoutDataProvider)

Returns the cost of an edge crossing between the two given edges.

The default implementation defines the crossing cost of two edges as the product of the individual crossing costs which are retrieved from the DataProvider registered with the graph with key IncrementalHierarchicLayouter.EDGE_CROSSING_COST_DPKEY. If no individual crossing costs are defined, all edges have a cost of 1, hence, this method also returns 1.

This method may be overridden to specify costs for a specific pair of edges. The given LayoutDataProvider is helpful to determine the type of the edges by using method LayoutDataProvider.getEdgeData(Edge). Furthermore, using the original edge to decide what a crossing costs might be helpful, see IncrementalHierarchicLayouter.getOriginalEdge(Edge, LayoutDataProvider).

Parameters:

edge1 - the first edge involved in the crossing

edge2 - the second edge involved in the crossing

layoutDataProvider - the LayoutDataProvider containing information about the edges and nodes

Returns:

the crossing cost for the two given edges

sequenceNodeLayers

public void sequenceNodeLayers(LayoutGraph graph,
                               Layers glayers,
                               LayoutDataProvider ldp,
                               ItemFactory itemFactory)

Description copied from interface: Sequencer

Calculates the sequence of the nodes within each layer.

This method is called by HierarchicLayouter during the second phase and finally writes back the calculated sequence using the Layer.setNodeOrder(y.base.YList) method.

Specified by:

sequenceNodeLayers in interface Sequencer

Parameters:

graph - the input graph

glayers - the given Layers instance containing the elements in the layering

ldp - the LayoutDataProvider implementation which provides access to the NodeData and EdgeData instances

itemFactory - the ItemFactory used temporarily for modifying the graph instance