y.layout.hierarchic
Class BFSLayerer

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

All Implemented Interfaces:

Layerer

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

BFSLayerer uses a breadth first search for assigning layers to the nodes.

The nodes of the first layer can be freely selected (see CORE_NODES). The nodes that belong 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.

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

Field Summary

static java.lang.Object

CORE_NODES A DataProvider key for identifying the core nodes of the BFS layering.

Constructor Summary

BFSLayerer()
Creates an instance of BFSLayerer.

Method Summary

void	assignLayers(LayoutGraph graph, Layers layers, LayoutDataProvider ldp) Assigns all nodes of the graph to layers and adds them to the Layers instance.
int	assignNodeLayer(LayoutGraph graph, NodeMap layerID, EdgeList reversedEdges) Assigns the nodes of 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 java.lang.Object CORE_NODES

A DataProvider key for identifying the core nodes of the BFS layering.

The DataProvider registered with this key should provide boolean values for the nodes of the graph. The boolean value determines whether or not a node is to be placed in the first layer. If there are no nodes marked as core nodes, then nodes with in-degree 0 are considered to be the core nodes.

Constructor Detail

BFSLayerer

public BFSLayerer()

Creates an instance of BFSLayerer.

Method Detail

assignNodeLayer

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

Assigns the nodes of the graph to layers.

Postcondition:

For all (v,w) in E: layer(v) < layer(w).

Parameters:

graph - the given graph

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

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 query information about the nodes and edges

See Also:

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