y.layout.hierarchic
Class WeightedLayerer

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