y.layout.tree
Class TreeReductionStage

java.lang.Object
  y.layout.AbstractLayoutStage
      y.layout.tree.TreeReductionStage

All Implemented Interfaces:

Layouter, LayoutStage

public class TreeReductionStage
extends AbstractLayoutStage

The TreeReductionStage temporarily reduces general graphs to trees.

Layout Style

This stage prepares a non-tree graph such that it can be processed by a tree layout algorithm.

The non-tree edges are marked

Typical usage:

 TreeLayouter tl = new TreeLayouter();
 TreeReductionStage trs = new TreeReductionStage();

 trs.setNonTreeEdgeRouter(new OrganicEdgeRouter());
 trs.setNonTreeEdgeSelectionKey(OrganicEdgeRouter.ROUTE_EDGE_DPKEY);

 tl.prependStage(trs);
 new BufferedLayouter(tl).doLayout(graph);
 tl.removeStage(trs);
 

Concept

This LayoutStage works in three steps:

1. Remove some edges to get a tree or forest from the graph
2. Invoke the core layout algorithm which supports tree graph handling
3. Reinsert all previously removed edges
4. Optionally route these edges using the non-tree edge router and place their labels using the non-tree edge labeling algorithm.

Features

The routing of the temporarily hidden non-tree edges can be customized by specifying an edge routing algorithm for those edges. Similarly, the placement of edge labels of non-tree edges can be delegated to a custom edge labeling algorithm. As default, both custom algorithms are not specified and, thus, non-tree edges are not routed and edge labels not placed.

This stage is also able to handle multi-parent structures, i.e., structures of multiple nodes that share the same predecessors as well as the same successors. More precisely, if the specified core layout algorithm supports multi-parent structures (see GenericTreeLayouter.setMultiParentAllowed(boolean)) and option setMultiParentAllowed(boolean) is enabled, this stage does not hide such structures, i.e., the multi-parent structures are passed to the core layout algorithm.

Non-tree edges can also be bundled together such that their common parts are to some degree merged into a bundled part. The edge bundling can be specified by means of method getEdgeBundling().

To get the non-tree edges computed internally, a DataAcceptor can be registered with the specified non-tree selection key. The algorithm will mark the non-tree edges.

If there are edges between group nodes, the TreeLayouter may throw a WrongGraphStructure-Exception. Such exceptions can be prevented by temporarily removing those edges.

Field Summary

static java.lang.Object

NON_TREE_EDGES_DPKEY A DataProvider key for explicitly marking (some) edges that should not be considered for the tree

Fields inherited from interface y.layout.Layouter

EDGE_ID_DPKEY, NODE_ID_DPKEY, NODE_TYPE_DPKEY, SELECTED_EDGES, SELECTED_NODES

Constructor Summary

TreeReductionStage()
Creates a new TreeReductionStage instance with default settings.

TreeReductionStage(Layouter core)
Creates a new TreeReductionStage instance with the given core layout algorithm and default settings.

Method Summary

boolean	canLayout(LayoutGraph graph) Accepts all general graphs without exception.
Layouter	createStraightlineRouter() Creates a routing algorithm that routes edges as a single straight segment.
void	doLayout(LayoutGraph graph) Determines a spanning tree of the graph and passes it to the core layout algorithm.
EdgeBundling	getEdgeBundling() Returns the EdgeBundling instance that defines the settings of the edge bundling feature.
Layouter	getNonTreeEdgeLabelingAlgorithm() Returns the labeling algorithm that is applied to all edge labels that belong to non-tree edges.
java.lang.Object	getNonTreeEdgeLabelSelectionKey() Returns the key to register a DataProvider that is used by the non-tree edge labeling algorithm to determine which edge labels it should place.
Layouter	getNonTreeEdgeRouter() Returns the edge routing algorithm that is applied to all non-tree edges.
java.lang.Object	getNonTreeEdgeSelectionKey() Returns the key to register a DataProvider that will be used by the non-tree edge routing algorithm to determine the edges that need to be routed.
boolean	isMultiParentAllowed() Returns whether or not multi-parent structures (structures of multiple nodes that share the same predecessors as well as the same successors) are allowed.
protected void	routeNonTreeEdges(LayoutGraph graph, EdgeMap nonTreeEdgeMap) Routes all edges that do not belong to the chosen spanning tree.
void	setMultiParentAllowed(boolean multiParentAllowed) Specifies whether or not multi-parent structures (structures of multiple nodes that share the same predecessors as well as the same successors) are allowed.
void	setNonTreeEdgeLabelingAlgorithm(Layouter nonTreeEdgeLabelingAlgorithm) Specifies the labeling algorithm that is applied to all edge labels that belong to non-tree edges.
void	setNonTreeEdgeLabelSelectionKey(java.lang.Object nonTreeEdgeLabelSelectionKey) Specifies the key to register a DataProvider that is used by the non-tree edge labeling algorithm to determine which edge labels it should place.
void	setNonTreeEdgeRouter(Layouter nonTreeEdgeRouter) Specifies the edge routing algorithm that is applied to all non-tree edges.
void	setNonTreeEdgeSelectionKey(java.lang.Object nonTreeEdgeSelectionKey) Specifies the key to register a DataProvider that will be used by the non-tree edge routing algorithm to determine the edges that need to be routed.

Methods inherited from class y.layout.AbstractLayoutStage

canLayoutCore, doLayoutCore, getCoreLayouter, setCoreLayouter

Methods inherited from class java.lang.Object

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

Field Detail

NON_TREE_EDGES_DPKEY

public static final java.lang.Object NON_TREE_EDGES_DPKEY

A DataProvider key for explicitly marking (some) edges that should not be considered for the tree

See Also:

getNonTreeEdgeRouter()

Constructor Detail

TreeReductionStage

public TreeReductionStage()

Creates a new TreeReductionStage instance with default settings.

TreeReductionStage

public TreeReductionStage(Layouter core)

Creates a new TreeReductionStage instance with the given core layout algorithm and default settings.

Parameters:

core - the core layout algorithm

Method Detail

canLayout

public boolean canLayout(LayoutGraph graph)

Accepts all general graphs without exception.

Parameters:

graph - the input graph

Returns:

true for all input graphs

See Also:

Layouter.doLayout(LayoutGraph)

doLayout

public void doLayout(LayoutGraph graph)

Determines a spanning tree of the graph and passes it to the core layout algorithm.

This LayoutStage reduces the graph to a tree. Then, it applies the core layout algorithm to that tree. After it gets the result, it reinserts the non-tree edges and routes them.

Parameters:

graph - the input graph

See Also:

Layouter.canLayout(LayoutGraph)

routeNonTreeEdges

protected void routeNonTreeEdges(LayoutGraph graph,
                                 EdgeMap nonTreeEdgeMap)

Routes all edges that do not belong to the chosen spanning tree.

This method is called by doLayout(LayoutGraph) after the tree was arranged by the core layout algorithm. It may be overridden to apply custom edge routes.

This method will do nothing if no non-tree edge routing algorithm was specified (i.e. if it is null).

Parameters:

graph - the graph containing tree and non-tree edges

nonTreeEdgeMap - the EdgeMap that marks all non-tree edges in the graph

isMultiParentAllowed

public boolean isMultiParentAllowed()

Returns whether or not multi-parent structures (structures of multiple nodes that share the same predecessors as well as the same successors) are allowed.

More precisely, if this option is enabled and the specified core layout algorithm can handle multi-parent structures (see GenericTreeLayouter.setMultiParentAllowed(boolean)), this stage does not hide such structures, but the multi-parent structures are passed on to the AbstractLayoutStage.getCoreLayouter() core layout algorithm}.

Returns:

true if multi-parent structures are allowed, false otherwise

See Also:

setMultiParentAllowed(boolean)

setMultiParentAllowed

public void setMultiParentAllowed(boolean multiParentAllowed)

Specifies whether or not multi-parent structures (structures of multiple nodes that share the same predecessors as well as the same successors) are allowed.

More precisely, if this option is enabled and the specified core layout algorithm can handle multi-parent structures (see GenericTreeLayouter.setMultiParentAllowed(boolean)), this stage does not hide such structures, but the multi-parent structures are passed on to the AbstractLayoutStage.getCoreLayouter() core layout algorithm}.

Default Value:

The default value is false. The reduced graph is a normal tree.

Parameters:

multiParentAllowed - true if multi-parent structures should be allowed, false otherwise

Sample Graphs:

false - the multi-parent structure was reduced to a tree, a non-tree edge is marked

true - the multi-parent structure was not reduced and arranged using an appropriate style

getNonTreeEdgeRouter

public Layouter getNonTreeEdgeRouter()

Returns the edge routing algorithm that is applied to all non-tree edges.

It is required that a suitable edge selection key is specified and the router's scope is reduced to the selected edges.

Returns:

the edge routing algorithm used for non-tree edges

See Also:

setNonTreeEdgeRouter(Layouter), setNonTreeEdgeSelectionKey(Object)

setNonTreeEdgeRouter

public void setNonTreeEdgeRouter(Layouter nonTreeEdgeRouter)

Specifies the edge routing algorithm that is applied to all non-tree edges.

It is required that a suitable edge selection key is specified and the router's scope is reduced to the selected edges.

Default Value:

The default value is null. Non-tree edges are not routed.

Parameters:

nonTreeEdgeRouter - the edge routing algorithm used for non-tree edges

See Also:

setNonTreeEdgeSelectionKey(Object)

getNonTreeEdgeSelectionKey

public java.lang.Object getNonTreeEdgeSelectionKey()

Returns the key to register a DataProvider that will be used by the non-tree edge routing algorithm to determine the edges that need to be routed.

If there is already a DataAcceptor registered with this key, the stage uses it to mark the non-tree edges. This way it can be determined which edges the layout treated as tree and which as non-tree edges.

Returns:

the DataProvider key

See Also:

setNonTreeEdgeSelectionKey(Object), setNonTreeEdgeRouter(Layouter)

setNonTreeEdgeSelectionKey

public void setNonTreeEdgeSelectionKey(java.lang.Object nonTreeEdgeSelectionKey)

Specifies the key to register a DataProvider that will be used by the non-tree edge routing algorithm to determine the edges that need to be routed.

If there is already a DataAcceptor registered with this key, the stage uses it to mark the non-tree edges. This way it can be determined which edges the layout treated as tree and which as non-tree edges.

Default Value:

The default value is null. There is no DataProvider key specified.

Parameters:

nonTreeEdgeSelectionKey - the DataProvider key

See Also:

setNonTreeEdgeRouter(Layouter)

getNonTreeEdgeLabelingAlgorithm

public Layouter getNonTreeEdgeLabelingAlgorithm()

Returns the labeling algorithm that is applied to all edge labels that belong to non-tree edges.

It is required that a suitable edge label selection key is set. Otherwise, the edge labeling algorithm might also place labels of tree edges.

A suitable labeling algorithm is SALabeling. Specify the edge label selection key as value of property AbstractLabelingAlgorithm.setSelection(Object) and remember to enable AbstractLabelingAlgorithm.setPlaceEdgeLabels(boolean).

Returns:

the labeling algorithm used for edge labels of non-tree edges

See Also:

setNonTreeEdgeLabelSelectionKey(Object), setNonTreeEdgeLabelingAlgorithm(Layouter)

setNonTreeEdgeLabelingAlgorithm

public void setNonTreeEdgeLabelingAlgorithm(Layouter nonTreeEdgeLabelingAlgorithm)

Specifies the labeling algorithm that is applied to all edge labels that belong to non-tree edges.

It is required that a suitable edge label selection key is set. Otherwise, the edge labeling algorithm might also place labels of tree edges.

A suitable labeling algorithm is SALabeling. Specify the edge label selection key as value of property AbstractLabelingAlgorithm.setSelection(Object) and remember to enable AbstractLabelingAlgorithm.setPlaceEdgeLabels(boolean).

Default Value:

The default value is null. Edge labels of non-tree edges are not placed.

Parameters:

nonTreeEdgeLabelingAlgorithm - the labeling algorithm used for edge labels of non-tree edges

See Also:

setNonTreeEdgeLabelSelectionKey(Object)

getNonTreeEdgeLabelSelectionKey

public java.lang.Object getNonTreeEdgeLabelSelectionKey()

Returns the key to register a DataProvider that is used by the non-tree edge labeling algorithm to determine which edge labels it should place.

During the layout, a DataProvider with this key will be registered with the graph. It will mark all EdgeLabelLayouts that belong to non-tree edges. The specified non-tree edge labeling algorithm needs to obey this selection. If using SALabeling as labeling algorithm, set this key as value of property AbstractLabelingAlgorithm.setSelection(Object).

When specifying a non-tree edge labeling algorithm but no edge label selection key, then the labeling algorithm might place all labels, including those that belong to actual tree edges.

Returns:

the non-tree edge label selection DataProvider key

See Also:

setNonTreeEdgeLabelSelectionKey(Object), setNonTreeEdgeLabelingAlgorithm(Layouter)

setNonTreeEdgeLabelSelectionKey

public void setNonTreeEdgeLabelSelectionKey(java.lang.Object nonTreeEdgeLabelSelectionKey)

Specifies the key to register a DataProvider that is used by the non-tree edge labeling algorithm to determine which edge labels it should place.

During the layout, a DataProvider with this key will be registered with the graph. It will mark all EdgeLabelLayouts that belong to non-tree edges. The specified non-tree edge labeling algorithm needs to obey this selection. If using SALabeling as labeling algorithm, set this key as value of property AbstractLabelingAlgorithm.setSelection(Object).

When specifying a non-tree edge labeling algorithm but no edge label selection key, then the labeling algorithm might place all labels, including those that belong to actual tree edges.

Default Value:

The default value is null. There is no DataProvider key specified.

Parameters:

nonTreeEdgeLabelSelectionKey - the non-tree edge label selection DataProvider key

See Also:

setNonTreeEdgeLabelingAlgorithm(Layouter)

createStraightlineRouter

public Layouter createStraightlineRouter()

Creates a routing algorithm that routes edges as a single straight segment.

The created instance can be used for routing non-tree edges.

Returns:

an edge routing algorithm that produces straight-line edges

See Also:

setNonTreeEdgeRouter(Layouter)

getEdgeBundling

public EdgeBundling getEdgeBundling()

Returns the EdgeBundling instance that defines the settings of the edge bundling feature.

The specified EdgeBundling defines global bundling properties. Settings for individual edges can be defined by assigning an EdgeBundleDescriptor to an edge using a DataProvider registered with key EdgeBundling.EDGE_BUNDLE_DESCRIPTOR_DPKEY. To enable bundling for all non-tree edges, set a default bundle descriptor which has bundling enabled.

If the graph contains self-loops that belong to the set of non-tree edges, the stage will invoke the router defined for the non-tree edges in order to route them. In the case where this is not desired, the user has to hide them from the stage and route them afterwards as desired.

To obtain a layout with bundled edges of nice quality, the TreeReductionStage should be combined with a layout algorithm that produces planar layouts of the underlying tree (i.e., no edges of the tree cross each other) as BalloonLayouter or GenericTreeLayouter.

The specified non-tree layouter is not applied to bundled edges.

Edge bundling has an effect only for non-tree edges for which bundling is enabled and if the graph does not contain multi-parent structures.

Returns:

the EdgeBundling instance defining the edge bundling setup