y.layout.hierarchic
Class BFSLayerer

java.lang.Object
  y.layout.hierarchic.BFSLayerer

All Implemented Interfaces:

Layerer

public class BFSLayerer
extends Object
implements Layerer, Layerer

Layerer that uses a breadth first search to assign layers to the nodes. The nodes of the first layer can be freely chosen (see CORE_NODES). The nodes belonging to a subsequent layer are determined as follows: Add all yet unassigned nodes to the new layer that are connected to nodes already assigned.

As a consequence all connected nodes will be at most one layer apart. Also, edges between nodes that belong to the same layer are possible.

Field Summary

static Object

CORE_NODES The data provider key used to look up the core nodes of the bfs layering.

Constructor Summary

BFSLayerer()

Method Summary

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	assignNodeLayer(LayoutGraph graph, NodeMap layer, EdgeList reversedEdges) This method assigns the nodes in the graph to layers.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

CORE_NODES

public static final Object CORE_NODES

The data provider key used to look up the core nodes of the bfs layering. The BFSLayerer will try to retrieve a data provider from the graph to be layered with this key. The looked up data provider should provide boolean values for the nodes of that graph. The boolean value signals whether a node is to be placed in the first layer or not.

If the are no nodes marked as core nodes then nodes with indegree 0 are considered to be core nodes.

Constructor Detail

BFSLayerer

public BFSLayerer()

Method Detail

assignNodeLayer

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

This method assigns the nodes in the graph to layers.

Parameters:

graph - 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)

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)