y.layout.hierarchic
Class BFSLayerer

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

All Implemented Interfaces:

Layerer

public class BFSLayerer
extends Object
implements 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

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.

Specified by:

assignNodeLayer in interface Layerer

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)