y.layout.hierarchic
Class ClassicLayerSequencer

java.lang.Object
  y.layout.hierarchic.ClassicLayerSequencer

All Implemented Interfaces:

LayerSequencer

public class ClassicLayerSequencer
extends java.lang.Object
implements LayerSequencer

This class implements the sequencing phase of the HierarchicLayouter (i.e., the order of the nodes within each layer is determined).

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

Field Summary

static byte	BARYCENTER_HEURISTIC A weight assignment based on a barycenter heuristic.
static java.lang.Object	GROUP_KEY A DataProvider key for mapping nodes with groups.
static byte	MEDIAN_HEURISTIC A weight assignment based on a median heuristic.

Constructor Summary

ClassicLayerSequencer()
Creates a ClassicLayerSequencer instance with default settings.

Method Summary

void	adoptValues(LayerSequencer otherSequencer) Tries to adopt/copy the settings of the given LayerSequencer to this sequencer.
NodeList[]	getLayers(LayoutGraph graph, NodeMap layerID, int maxLayer) Calculates the sequence of nodes within each layer.
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.
int	getRecentCrossingNumber() Returns the number of edge crossings that were produced by this sequencer the last time it was applied to a graph.
boolean	getRemoveFalseCrossings() Returns whether or not to remove so-called false crossings in an additional phase.
boolean	getUseTransposition() Returns whether or not to apply an additional crossing minimization heuristic.
byte	getWeightHeuristic() Returns the weight heuristic that is used.
boolean	isUsingGroups() Returns whether or not this ClassicLayerSequencer will preserve the groupings of nodes between each layer.
void	setMaximalDuration(long maximalDuration) 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	setRemoveFalseCrossings(boolean b) Specifies whether or not to remove so-called false crossings in an additional phase.
void	setUseTransposition(boolean b) Specifies whether or not to apply an additional crossing minimization heuristic.
void	setUsingGroups(boolean usingGroups) Specifies whether or not this ClassicLayerSequencer will preserve the groupings of nodes between each layer.
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

GROUP_KEY

public static final java.lang.Object GROUP_KEY

A DataProvider key for mapping nodes with groups.

BARYCENTER_HEURISTIC

public static final byte BARYCENTER_HEURISTIC

A weight assignment 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

MEDIAN_HEURISTIC

public static final byte MEDIAN_HEURISTIC

A weight assignment 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

Constructor Detail

ClassicLayerSequencer

public ClassicLayerSequencer()

Creates a ClassicLayerSequencer instance with default settings.

Method Detail

setUseTransposition

public void setUseTransposition(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 - four crossings

Transposition enabled - two crossings

getUseTransposition

public boolean getUseTransposition()

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:

setUseTransposition(boolean)

setWeightHeuristic

public void setWeightHeuristic(byte h)

Specifying the weight heuristic that should be used.

Default Value:

The default value is BARYCENTER_HEURISTIC

Parameters:

h - one of the predefined weight heuristics

Throws:

java.lang.IllegalArgumentException - if the specified constant is unknown

getWeightHeuristic

public byte getWeightHeuristic()

Returns the weight heuristic that is used.

Returns:

one of the predefined weight heuristics

See Also:

setWeightHeuristic(byte)

setRemoveFalseCrossings

public void setRemoveFalseCrossings(boolean b)

Specifies whether or not to remove so-called false crossings in an additional phase.

A false crossing is a crossing between two edges that share a common terminal node.

Enabling this option may increase the running time of the algorithm.

Default Value:

The default value is true. False crossings will be removed.

Parameters:

b - true if false crossings should be removed, false otherwise

Sample Graphs:

false

true

getRemoveFalseCrossings

public boolean getRemoveFalseCrossings()

Returns whether or not to remove so-called false crossings in an additional phase.

A false crossing is a crossing between two edges that share a common terminal node.

Enabling this option may increase the running time of the algorithm.

Default Value:

The default value is true. False crossings will be removed.

Returns:

true if false crossings should be removed, false otherwise

See Also:

setRemoveFalseCrossings(boolean)

setMaximalDuration

public void setMaximalDuration(long maximalDuration)

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 1000.

Parameters:

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

Throws:

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

getRecentCrossingNumber

public int getRecentCrossingNumber()

Returns the number of edge crossings that were produced by this sequencer the last time it was applied to a graph.

This method can be called after CanonicMultiStageLayouter.doLayout(LayoutGraph) has finished to return the current number of edge crossings in the layout.

Precondition:

Method getLayers(LayoutGraph, NodeMap, int) must have been called before.

Returns:

the number of edge crossings that were produced by this sequencer

adoptValues

public void adoptValues(LayerSequencer otherSequencer)

Tries to adopt/copy the settings of the given LayerSequencer to this sequencer.

This method has an effect only if the given LayerSequencer is an instance of ClassicLayerSequencer.

Parameters:

otherSequencer - the given LayerSequencer instance

getLayers

public NodeList[] getLayers(LayoutGraph graph,
                            NodeMap layerID,
                            int maxLayer)

Calculates the sequence of nodes within each layer.

The result is returned as an array of NodeLists containing nodes that belong to the same layer. The order of the nodes within such list represents the sequence of the nodes within their layer.

Specified by:

getLayers in interface LayerSequencer

Parameters:

graph - the input graph

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

maxLayer - the number of layers

Returns:

an array of NodeLists containing nodes that belong to the same layer; the order of the nodes within each such list represents the sequence of the nodes within their layer

isUsingGroups

public boolean isUsingGroups()

Returns whether or not this ClassicLayerSequencer will preserve the groupings of nodes between each layer.

Preserving groupings means nodes inside the same group will be placed directly next to each other within each layer.

Returns:

true if groupings is preserved, false otherwise

setUsingGroups

public void setUsingGroups(boolean usingGroups)

Specifies whether or not this ClassicLayerSequencer will preserve the groupings of nodes between each layer.

Preserving groupings means nodes inside the same group will be placed directly next to each other within each layer.

Default Value:

The default value is false. Preserving groupings is disabled.

Parameters:

usingGroups - true if groupings should be preserved, false otherwise

Sample Graphs:

false - Groups are ignored. Nodes 5 and 7 belong to Group 2, while nodes 6 and 8 to Group 3.

true - Groups are considered. Nodes 5 and 7 belong to Group 2, while nodes 6 and 8 to Group 3.

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 40. The number of randomized rounds is 40, if the maximum duration hasn't been reduced below its default value.

Parameters:

randomizationRounds - the given number of additional rounds

Throws:

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