Package org.jungrapht.visualization.layout.algorithms

Class DAGLayoutAlgorithm<V,E>

java.lang.Object

org.jungrapht.visualization.layout.algorithms.AbstractLayoutAlgorithm<V>

org.jungrapht.visualization.layout.algorithms.AbstractIterativeLayoutAlgorithm<V>

org.jungrapht.visualization.layout.algorithms.SpringLayoutAlgorithm<V,E>

org.jungrapht.visualization.layout.algorithms.DAGLayoutAlgorithm<V,E>

All Implemented Interfaces:

IterativeLayoutAlgorithm<V>, LayoutAlgorithm<V>, AfterRunnable, ExecutorConsumer, IterativeContext, Threaded

public class DAGLayoutAlgorithm<V,E>
extends SpringLayoutAlgorithm<V,E>

An implementation of Layout suitable for tree-like directed acyclic graphs. Parts of it will probably not terminate if the graph is cyclic! The layout will result in directed edges pointing generally upwards. Any vertices with no successors are considered to be level 0, and tend towards the top of the layout. Any vertex has a level one greater than the maximum level of all its successors.

Author:

John Yesberg

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	DAGLayoutAlgorithm.Builder<V,E,T extends DAGLayoutAlgorithm<V,E>,B extends DAGLayoutAlgorithm.Builder<V,E,T,B>>

Nested classes/interfaces inherited from class org.jungrapht.visualization.layout.algorithms.SpringLayoutAlgorithm

SpringLayoutAlgorithm.SpringVertexData

Nested classes/interfaces inherited from interface org.jungrapht.visualization.layout.algorithms.LayoutAlgorithm

LayoutAlgorithm.NoOp<V>

Nested classes/interfaces inherited from interface org.jungrapht.visualization.layout.algorithms.util.Threaded

Threaded.NoOp

Field Summary

Fields

Modifier and Type	Field	Description
protected Collection<E>	feedbackArcs

Fields inherited from class org.jungrapht.visualization.layout.algorithms.SpringLayoutAlgorithm

force_multiplier, lengthFunction, repulsion_range_sq, repulsionContract, repulsionContractBuilder, springVertexData, stretch

Fields inherited from class org.jungrapht.visualization.layout.algorithms.AbstractIterativeLayoutAlgorithm

afterRunnable, cancelled, executor, layoutModel, preRelaxDurationMs, random, shouldPreRelax, threaded

Fields inherited from class org.jungrapht.visualization.layout.algorithms.AbstractLayoutAlgorithm

after

Constructor Summary

Constructors

Modifier	Constructor	Description
	DAGLayoutAlgorithm()
protected	DAGLayoutAlgorithm(DAGLayoutAlgorithm.Builder<V,E,?,?> builder)

Method Summary

Modifier and Type	Method	Description
static <V,E> DAGLayoutAlgorithm.Builder<V,E,?,?>	builder()
boolean	done()	Override incrementsAreDone so that we can eventually stop.
void	initialize()	Had to override this one as well, to ensure that setRoot() is called.
protected void	moveVertices()	Override the moveVertices() method from SpringLayout.
void	propagateMinimumLevel(V vertex)	A recursive method for allocating the level for each vertex.
protected void	relaxEdges()	Overridden relaxEdges.
void	setLocation(V picked, double x, double y)	Override forceMove so that if someone moves a vertex, we can re-layout everything.
void	setLocation(V picked, Point p)	Override forceMove so that if someone moves a vertex, we can re-layout everything.
void	setRoot()	Calculates the level of each vertex in the graph.
void	setRoot(V vertex)	Set vertex v to be level 0.
void	visit(LayoutModel<V> layoutModel)	Override to create the BarnesHutOctTree

Methods inherited from class org.jungrapht.visualization.layout.algorithms.SpringLayoutAlgorithm

getForceMultiplier, getRepulsionRange, getStretch, setForceMultiplier, setRepulsionRange, setStretch, step, toString

Methods inherited from class org.jungrapht.visualization.layout.algorithms.AbstractIterativeLayoutAlgorithm

cancel, getExecutor, isThreaded, preRelax, setExecutor, setRandomSeed, setThreaded

Methods inherited from class org.jungrapht.visualization.layout.algorithms.AbstractLayoutAlgorithm

computeAverageVertexDimension, computeLayoutExtent, expandToFill, runAfter, setAfter

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jungrapht.visualization.layout.algorithms.util.AfterRunnable

runAfter, setAfter

Methods inherited from interface org.jungrapht.visualization.layout.algorithms.LayoutAlgorithm

constrained

Field Detail

feedbackArcs

protected Collection<E> feedbackArcs

Constructor Detail

DAGLayoutAlgorithm

protected DAGLayoutAlgorithm(DAGLayoutAlgorithm.Builder<V,E,?,?> builder)

DAGLayoutAlgorithm

public DAGLayoutAlgorithm()

Method Detail

builder

public static <V,E> DAGLayoutAlgorithm.Builder<V,E,?,?> builder()

visit

public void visit(LayoutModel<V> layoutModel)

Description copied from class: SpringLayoutAlgorithm

Override to create the BarnesHutOctTree

Specified by:

visit in interface LayoutAlgorithm<V>

Overrides:

visit in class SpringLayoutAlgorithm<V,E>

Parameters:

layoutModel - the mediator between the container for vertices (the Graph) and the mapping from Vertex to Point

setRoot

public void setRoot()

Calculates the level of each vertex in the graph. Level 0 is allocated to each vertex with no successors. Level n+1 is allocated to any vertex whose successors' maximum level is n.

setRoot

public void setRoot(V vertex)

Set vertex v to be level 0.

Parameters:

vertex - the vertex to set as root

propagateMinimumLevel

public void propagateMinimumLevel(V vertex)

A recursive method for allocating the level for each vertex. Ensures that all predecessors of v have a level which is at least one greater than the level of v.

Parameters:

vertex - the vertex whose minimum level is to be calculated

initialize

public void initialize()

Had to override this one as well, to ensure that setRoot() is called.

Overrides:

initialize in class SpringLayoutAlgorithm<V,E>

moveVertices

protected void moveVertices()

Override the moveVertices() method from SpringLayout. The only change we need to make is to make sure that vertices don't float higher than the minY coordinate, as calculated by their minimumLevel.

Overrides:

moveVertices in class SpringLayoutAlgorithm<V,E>

done

public boolean done()

Override incrementsAreDone so that we can eventually stop.

Specified by:

done in interface IterativeContext

Overrides:

done in class SpringLayoutAlgorithm<V,E>

Returns:

false

setLocation

public void setLocation(V picked,
                        double x,
                        double y)

Override forceMove so that if someone moves a vertex, we can re-layout everything.

Parameters:

picked - the vertex whose location is to be set

x - the x coordinate of the location to set

y - the y coordinate of the location to set

setLocation

public void setLocation(V picked,
                        Point p)

Override forceMove so that if someone moves a vertex, we can re-layout everything.

Parameters:

picked - the vertex whose location is to be set

p - the location to set

relaxEdges

protected void relaxEdges()

Overridden relaxEdges. This one reduces the effect of edges between greatly different levels.

Overrides:

relaxEdges in class SpringLayoutAlgorithm<V,E>