Search this API

y.layout.hierarchic.incremental
Class DefaultLayerSequencer

java.lang.Object
  extended by 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

© Copyright 2000-2021,
yWorks GmbH.
All rights reserved.