y.layout.hierarchic
Class WeightedLayerer

java.lang.Object
  y.layout.hierarchic.WeightedLayerer

All Implemented Interfaces:

Layerer

public class WeightedLayerer
extends Object
implements Layerer, Layerer

This class implements the first phase of the hierarchic layouter. It first makes the directed graph acyclic. Then it assigns the layers such that edge weights are respected A weight defines a minimal distance between the two end points of an edge.

Field Summary

protected Object	key The key to access the weights.
protected DataProvider	weight Provides the edge weights.

Constructor Summary

WeightedLayerer()
Creates a new weighted layerer.

WeightedLayerer(Object k)
Creates a new weighted layerer.

Method Summary

int	assignLayers(Graph g, NodeMap layer) Assigns the layers to the nodes.
void	assignLayers(LayoutGraph graph, Layers layers, LayoutDataProvider ldp) This method assigns all nodes in the graph to layers and registers them in the Layers instance.
int	assignLayersFast(Graph g, NodeMap layer) Assign the layers to the nodes.
int	assignNodeLayer(Graph g, NodeMap layer, EdgeList reversedEdges, DataProvider w) 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 g, NodeMap layer, EdgeList reversedEdges) This method assigns the nodes in the graph to layers.
int	assignNodeLayer(LayoutGraph g, NodeMap layer, EdgeList reversedEdges, DataProvider w) This method assigns the nodes in the graph to layers.
protected void	downShiftNodes(Graph g, NodeMap LAYER_KEY, int maxLayer) Pushes the nodes down, drawings seems then to be nicer.
long	getMaximalDuration() Returns the time limit (in milliseconds) set for the algorithm.
protected double	getWeight(Edge edge) Returns the edge weight of the specified edge for use with the weight based cycle removal heuristic.
boolean	isWeightedCycleRemovalEnabled() Returns true if the edges that need to be reversed are determined using an edge weight based heuristic and false if a Depth First Search based approach should be used.
void	makeDFSAcyclic(Graph g, EdgeList reversedEdges) Uses dfs to remove cycles from the graph.
void	makeDFSAcyclic(LayoutGraph g, EdgeList reversedEdges) Uses dfs to remove cycles from the graph.
void	setMaximalDuration(long maximalDuration) Sets a preferred time limit (in milliseconds) for the algorithm.
void	setWeightedCycleRemovalEnabled(boolean enabled) Specifies if 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

Provides the edge weights.

key

protected Object key

The key to access the weights.

Constructor Detail

WeightedLayerer

public WeightedLayerer()

Creates a new weighted layerer.

WeightedLayerer

public WeightedLayerer(Object k)

Creates a new weighted layerer.

Parameters:

k - the key to access the weights.

Method Detail

isWeightedCycleRemovalEnabled

public boolean isWeightedCycleRemovalEnabled()

Returns true if the edges that need to be reversed are determined using an edge weight based heuristic and false if a Depth First Search based approach should be used. 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.

Defaults to false.

Returns:

true if the edges that need to be reversed are determined using an edge weight based heuristic and false if a Depth First Search based approach should be used.

See Also:

setWeightedCycleRemovalEnabled(boolean)

setWeightedCycleRemovalEnabled

public void setWeightedCycleRemovalEnabled(boolean enabled)

Specifies if 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.

By default, the DFS based approach is used.

Parameters:

enabled - if true an edge weight based heuristic is used; else a Depth First Search based approach is used.

See Also:

isWeightedCycleRemovalEnabled()

getMaximalDuration

public long getMaximalDuration()

Returns the time limit (in milliseconds) set for the algorithm.

Returns:

the time limit.

See Also:

setMaximalDuration(long)

setMaximalDuration

public void setMaximalDuration(long maximalDuration)

Sets a preferred time limit (in milliseconds) for the algorithm. Note that restricting the maximal duration may result in a worse layout quality. Furthermore, the real runtime may exceed the maximal duration since the algorithm still have to find a valid solution.

Parameters:

maximalDuration - the time limit.

See Also:

getMaximalDuration()

assignNodeLayer

public int assignNodeLayer(LayoutGraph g,
                           NodeMap layer,
                           EdgeList reversedEdges)

This method assigns the nodes in the graph to layers.

Parameters:

g - the graph for which the layers are determined.

layer - here the layers are stored

reversedEdges - here the edges are stored which had been reversed.

Returns:

the number of layers

Postcondition:

Forall (v,w) in E: layer(v) < layer(w)

assignNodeLayer

public int assignNodeLayer(LayoutGraph g,
                           NodeMap layer,
                           EdgeList reversedEdges,
                           DataProvider w)

This method assigns the nodes in the graph to layers.

Parameters:

g - the graph for which the layers are determined.

layer - here the layers are stored

reversedEdges - here the edges are stored which had been reversed.

Returns:

the number of layers

Postcondition:

Forall (v,w) in E: layer(v) < layer(w)

getWeight

protected double getWeight(Edge edge)

Returns the edge weight of the specified edge for use with the weight based cycle removal heuristic.

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

Parameters:

edge - the edge whose weight is returned.

Returns:

the edge weight of the specified edge.

See Also:

isWeightedCycleRemovalEnabled(), setWeightedCycleRemovalEnabled(boolean)

assignNodeLayer

public int assignNodeLayer(Graph g,
                           NodeMap layer,
                           EdgeList reversedEdges,
                           DataProvider w)

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.

This method assigns the nodes in the graph to layers.

Parameters:

g - the graph for which the layers are determined.

layer - here the layers are stored

reversedEdges - here the edges are stored which had been reversed.

Returns:

the number of layers

Postcondition:

Forall (v,w) in E: layer(v) < layer(w)

makeDFSAcyclic

public void makeDFSAcyclic(LayoutGraph g,
                           EdgeList reversedEdges)

Uses dfs to remove cycles from the graph.

makeDFSAcyclic

public void makeDFSAcyclic(Graph g,
                           EdgeList reversedEdges)

Uses dfs to remove cycles from the graph.

assignLayers

public int assignLayers(Graph g,
                        NodeMap layer)

Assigns the layers to the nodes.

assignLayersFast

public int assignLayersFast(Graph g,
                            NodeMap layer)

Assign the layers to the nodes.

downShiftNodes

protected void downShiftNodes(Graph g,
                              NodeMap LAYER_KEY,
                              int maxLayer)

Pushes the nodes down, drawings seems then to be nicer.

assignLayers

public void assignLayers(LayoutGraph graph,
                         Layers layers,
                         LayoutDataProvider ldp)

Description copied from interface: Layerer

This method assigns all nodes in the graph to layers and registers them in the Layers instance. In order to create new layers, the factory method Layers.insert(byte, int) must be used.

Specified by:

assignLayers in interface Layerer

Parameters:

graph - the graph that contains the nodes that should be distributed into the layers

layers - the object that will be filled with the results of the calculation

ldp - LayoutDataProvider that can be used to query information about the nodes - note that positional information (see NodeData.getPosition() and NodeData.getLayer()) cannot be available at any time.

See Also:

Layers.insert(byte, int), Layer.add(y.base.Node)