Search this API

y.layout.hierarchic
Class WeightedLayerer

java.lang.Object
  extended by y.layout.hierarchic.WeightedLayerer
All Implemented Interfaces:
Layerer

public class WeightedLayerer
extends java.lang.Object
implements Layerer, Layerer

This class implements the layering phase of the IncrementalHierarchicLayouter (i.e., the assignment of the nodes to layers).

It first makes the directed graph acyclic. Then, it assigns the layers such that edge weights are respected. A weight defines a minimum distance between the two end points of an edge.

 
This class can be used with IncrementalHierarchicLayouter as well as HierarchicLayouter and HierarchicGroupLayouter.
 

Field Summary
protected  java.lang.Object key
          The key to access the DataProvider that holds the edge weights.
protected  DataProvider weight
          This is a DataProvider that holds for each Edge an integer value representing its weight.
 
Constructor Summary
WeightedLayerer()
          Creates an instance of WeightedLayerer with default settings.
WeightedLayerer(java.lang.Object key)
          Creates an instance of WeightedLayerer with the given key that provides access to the DataProvider that holds the edge weights and unlimited maximum duration for the WeightedLayerer.
 
Method Summary
 int assignLayers(Graph graph, NodeMap layerID)
          Assigns all nodes of the graph to layers.
 void assignLayers(LayoutGraph graph, Layers layers, LayoutDataProvider ldp)
          Assigns all nodes of the graph to layers and adds them to the Layers instance.
 int assignLayersFast(Graph graph, NodeMap layerID)
          Assigns all nodes of the graph to layers.
 int assignNodeLayer(Graph graph, NodeMap layerID, EdgeList reversedEdges, DataProvider weight)
          Deprecated. Use assignNodeLayer(y.layout.LayoutGraph, y.base.NodeMap, y.base.EdgeList, y.base.DataProvider) instead.

This method does not support graphs that have several disjoint graph components nor the edge weight based cycle removal heuristic.

 int assignNodeLayer(LayoutGraph graph, NodeMap layerID, EdgeList reversedEdges)
          Assigns all nodes of the graph to layers.
 int assignNodeLayer(LayoutGraph graph, NodeMap layerID, EdgeList reversedEdges, DataProvider weight)
          Assigns all nodes of the graph to layers.
protected  void downShiftNodes(Graph graph, NodeMap layerID, int maxLayer)
          Deprecated. This method is not used any more. ??

The drawings seem to be nicer in this way.

 long getMaximalDuration()
          Returns the time limit in milliseconds set for the layout algorithm.
protected  double getWeight(Edge edge)
          Returns the edge weight of the given edge using the weight based cycle removal heuristic.
 boolean isWeightedCycleRemovalEnabled()
          Returns whether or not the edges that need to be reversed are determined using an edge weight based heuristic or using a depth first search based approach.
 void makeDFSAcyclic(Graph graph, EdgeList reversedEdges)
          Removes cycles from the graph using a depth first search.
 void makeDFSAcyclic(LayoutGraph graph, EdgeList reversedEdges)
          Removes cycles from the graph using a depth first search.
 void setMaximalDuration(long maximalDuration)
          Specifies the time limit in milliseconds set for the layout algorithm.
 void setWeightedCycleRemovalEnabled(boolean enabled)
          Specifies whether or not the edges that need to be reversed are determined using an edge weight based heuristic or using a depth first search based approach.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

weight

protected DataProvider weight
This is a DataProvider that holds for each Edge an integer value representing its weight.


key

protected java.lang.Object key
The key to access the DataProvider that holds the edge weights. More precisely, the corresponding DataProvider maps each edge of the input graph to an integer value representing the edge's weight.

Constructor Detail

WeightedLayerer

public WeightedLayerer()
Creates an instance of WeightedLayerer with default settings.

With this constructor, there exists no key to access the DataProvider that holds the edge weights. This means that the edges will be considered to have uniform weights of value 1.0.


WeightedLayerer

public WeightedLayerer(java.lang.Object key)
Creates an instance of WeightedLayerer with the given key that provides access to the DataProvider that holds the edge weights and unlimited maximum duration for the WeightedLayerer.

Parameters:
key - the key to access the DataProvider that holds the edge weights
Method Detail

isWeightedCycleRemovalEnabled

public boolean isWeightedCycleRemovalEnabled()
Returns whether or not the edges that need to be reversed are determined using an edge weight based heuristic or using a depth first search based approach.

The weight based approach may result in fewer reversed edges (especially for cases with many multi-edges) whereas the DFS based approach is likely to be faster.

Returns:
true if an edge weight based heuristic is used; false if a DFS based approach is used
See Also:
setWeightedCycleRemovalEnabled(boolean), isWeightedCycleRemovalEnabled()

setWeightedCycleRemovalEnabled

public void setWeightedCycleRemovalEnabled(boolean enabled)
Specifies whether or not the edges that need to be reversed are determined using an edge weight based heuristic or using a depth first search based approach.

The weight based approach may result in fewer reversed edges (especially for cases with many multi-edges) whereas the DFS based approach is likely to be faster.

Default Value:
The default value is false. The DFS based approach is used.
Parameters:
enabled - true if an edge weight based heuristic is used; false if a DFS based approach is used
See Also:
isWeightedCycleRemovalEnabled()

getMaximalDuration

public long getMaximalDuration()
Returns the time limit in milliseconds set for the layout algorithm.

Values have to be greater than or equal to 0.

 
Restricting the maximum duration may result in a lower layout quality. Furthermore, the real runtime may exceed the maximum duration since the layout algorithm still has to find a valid solution.
Returns:
a non-negative value that specifies the time limit
See Also:
setMaximalDuration(long)

setMaximalDuration

public void setMaximalDuration(long maximalDuration)
Specifies the time limit in milliseconds set for the layout algorithm.

Values have to be greater than or equal to 0.

 
Restricting the maximum duration may result in a lower layout quality. Furthermore, the real runtime may exceed the maximum duration since the layout algorithm still has to find a valid solution.
Default Value:
The default value is Long.MAX_VALUE. The layout algorithm runs unrestricted.
Parameters:
maximalDuration - a non-negative value that specifies the time limit
Throws:
java.lang.IllegalArgumentException - if the maximum duration is negative

assignNodeLayer

public int assignNodeLayer(LayoutGraph graph,
                           NodeMap layerID,
                           EdgeList reversedEdges)
Assigns all nodes of the graph to layers.

Postcondition:
For all (v,w) in E: layer(v) < layer(w)
Parameters:
graph - the graph for which the layers are determined
layerID - the NodeMap that will be filled by the layout algorithm and returns the zero-based index of the layer to which each node belongs
reversedEdges - an EdgeList containing the edges which had been reversed
Returns:
the number of layers

assignNodeLayer

public int assignNodeLayer(LayoutGraph graph,
                           NodeMap layerID,
                           EdgeList reversedEdges,
                           DataProvider weight)
Assigns all nodes of the graph to layers.

Postcondition:
For all (v,w) in E: layer(v) < layer(w)
Parameters:
graph - the graph for which the layers are determined
layerID - the NodeMap that will be filled by the layout algorithm and returns a zero-based layer index for each node
reversedEdges - an EdgeList containing the edges which had been reversed
weight - the DataProvider that returns an integer value (weight) for each edge
Returns:
the number of layers

getWeight

protected double getWeight(Edge edge)
Returns the edge weight of the given edge using the weight based cycle removal heuristic.

By default, all edges are considered to have weight 1.0.

It may be overridden if non-uniform weights are desired.

Parameters:
edge - given edge
Returns:
the edge weight of the specified edge
See Also:
isWeightedCycleRemovalEnabled(), setWeightedCycleRemovalEnabled(boolean)

assignNodeLayer

public int assignNodeLayer(Graph graph,
                           NodeMap layerID,
                           EdgeList reversedEdges,
                           DataProvider weight)
Deprecated. Use assignNodeLayer(y.layout.LayoutGraph, y.base.NodeMap, y.base.EdgeList, y.base.DataProvider) instead.

This method does not support graphs that have several disjoint graph components nor the edge weight based cycle removal heuristic.

Assigns all nodes of the graph to layers.

Postcondition:
For all (v,w) in E: layer(v) < layer(w)
Parameters:
graph - the graph for which the layers are determined
layerID - the NodeMap that will be filled by the layout algorithm and returns the zero-based index of the layer to which each node belongs
reversedEdges - an EdgeList containing the edges which had been reversed
weight - the DataProvider that returns an integer value (weight) for each edge
Returns:
the number of layers

makeDFSAcyclic

public void makeDFSAcyclic(LayoutGraph graph,
                           EdgeList reversedEdges)
Removes cycles from the graph using a depth first search.

Parameters:
graph - the graph
reversedEdges - an EdgeList containing the edges which will be reversed

makeDFSAcyclic

public void makeDFSAcyclic(Graph graph,
                           EdgeList reversedEdges)
Removes cycles from the graph using a depth first search.

Parameters:
graph - the graph
reversedEdges - an EdgeList containing the edges which will be reversed

assignLayers

public int assignLayers(Graph graph,
                        NodeMap layerID)
Assigns all nodes of the graph to layers.

Postcondition:
For all (v,w) in E: layer(v) < layer(w)
Parameters:
graph - the graph for which the layers are determined
layerID - the NodeMap that will be filled by the layout algorithm and returns the zero-based index of the layer to which each node belongs
Returns:
the number of layers

assignLayersFast

public int assignLayersFast(Graph graph,
                            NodeMap layerID)
Assigns all nodes of the graph to layers.

Postcondition:
For all (v,w) in E: layer(v) < layer(w)
Parameters:
graph - the graph for which the layers are determined
layerID - the NodeMap that will be filled by the layout algorithm and returns a zero-based layer index for each node
Returns:
the number of layers

downShiftNodes

protected void downShiftNodes(Graph graph,
                              NodeMap layerID,
                              int maxLayer)
Deprecated. This method is not used any more. ??

The drawings seem to be nicer in this way.

Shifts downwards the nodes of the given graph.

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

assignLayers

public void assignLayers(LayoutGraph graph,
                         Layers layers,
                         LayoutDataProvider ldp)
Assigns all nodes of the graph to layers and adds them to the Layers instance.

Specified by:
assignLayers in interface Layerer
Parameters:
graph - the input graph
layers - the Layers instance that will be filled with the results of the calculation
ldp - the LayoutDataProvider used for querying information about the nodes and edges
See Also:
Layers.insert(byte, int), Layer.add(y.base.Node)

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