grammarscope.jung2.layout

Class SugiyamaLayout<V,E>

java.lang.Object

edu.uci.ics.jung.algorithms.layout.AbstractLayout<V,E>

grammarscope.jung2.layout.SugiyamaLayout<V,E>

All Implemented Interfaces:

edu.uci.ics.jung.algorithms.layout.Layout<V,E>, org.apache.commons.collections15.Transformer<V,java.awt.geom.Point2D>

public class SugiyamaLayout<V,E>
extends edu.uci.ics.jung.algorithms.layout.AbstractLayout<V,E>

Arranges the nodes with the Sugiyama Layout Algorithm.
Link to the algorithm
Originally, source was posted to the Jung2 forum, for Jung 1.x. Not sure where the original code came from, but it didn't work for Jung2, but it was not that complicated, so I pounded it into shape for Jung2, complete with generics and such. Lays out either top-down to left-right. Seems to work. Parameterize with spacing and orientation. C. Schanck (chris at schanck dot net)

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(package private) static class	SugiyamaLayout.CellWrapper<VV> cell wrapper contains all values for one node
static class	SugiyamaLayout.Orientation

Field Summary

Fields

Modifier and Type	Field and Description
private static int	DEFAULT_HORIZONTAL_SPACING
private static SugiyamaLayout.Orientation	DEFAULT_ORIENTATION
private static int	DEFAULT_VERTICAL_SPACING
private boolean	executed
private int	gridAreaSize represents the size of the grid in horizontal grid elements
private int	horzSpacing
private SugiyamaLayout.Orientation	orientation
private java.util.Set<V>	traversalSet
private int	vertSpacing
private java.util.Map<V,SugiyamaLayout.CellWrapper<V>>	vertToWrapper

Fields inherited from class edu.uci.ics.jung.algorithms.layout.AbstractLayout

graph, initialized, locations, size

Constructor Summary

Constructors

Constructor and Description
SugiyamaLayout(edu.uci.ics.jung.graph.Graph<V,E> g)
SugiyamaLayout(edu.uci.ics.jung.graph.Graph<V,E> g, SugiyamaLayout.Orientation orientation, int horzSpacing, int vertSpacing)

Method Summary

Modifier and Type	Method and Description
private void	fillLevels(java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> levels, int level, V rootNode) Fills the LinkedList for the specified level with a wrapper for the MyGraphCell.
private java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>>	fillLevels(java.util.LinkedList<V> roots, java.util.Set<V> vertexSet) Method fills the levels and stores them in the member levels.
private java.util.Collection<E>	getNeighborEdges(V v)
void	initialize()
private boolean	move(boolean toRight, java.util.LinkedList<SugiyamaLayout.CellWrapper<V>> currentLevel, int currentIndexInTheLevel, int currentPriority)
private int	moveToBarycenter(java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> levels, int levelIndex)
private void	moveToBarycenter(java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> levels, java.util.Set<V> vertexSet)
void	reset()
private java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>>	runSugiyama() Implementation.
private java.util.LinkedList<V>	searchRoots(java.util.Set<V> vertexSet) Searches all Roots for the current Graph First the method marks any Node as not visited.
private int	solveEdgeCrosses(boolean down, java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> levels, int levelIndex) Solve edge crosses
private void	solveEdgeCrosses(java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> levels) Solve edge crosses
java.lang.String	toString()

Methods inherited from class edu.uci.ics.jung.algorithms.layout.AbstractLayout

getGraph, getSize, getX, getY, isLocked, lock, lock, offsetVertex, setGraph, setInitializer, setLocation, setLocation, setSize, transform

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_ORIENTATION

private static final SugiyamaLayout.Orientation DEFAULT_ORIENTATION

DEFAULT_HORIZONTAL_SPACING

private static final int DEFAULT_HORIZONTAL_SPACING

See Also:

Constant Field Values

DEFAULT_VERTICAL_SPACING

private static final int DEFAULT_VERTICAL_SPACING

See Also:

Constant Field Values

executed

private boolean executed

gridAreaSize

private int gridAreaSize

represents the size of the grid in horizontal grid elements

horzSpacing

private final int horzSpacing

vertSpacing

private final int vertSpacing

traversalSet

private final java.util.Set<V> traversalSet

vertToWrapper

private final java.util.Map<V,SugiyamaLayout.CellWrapper<V>> vertToWrapper

orientation

private final SugiyamaLayout.Orientation orientation

Constructor Detail

SugiyamaLayout

public SugiyamaLayout(edu.uci.ics.jung.graph.Graph<V,E> g)

SugiyamaLayout

public SugiyamaLayout(edu.uci.ics.jung.graph.Graph<V,E> g,
                      SugiyamaLayout.Orientation orientation,
                      int horzSpacing,
                      int vertSpacing)

Method Detail

initialize

public void initialize()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

runSugiyama

private java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> runSugiyama()

Implementation. First of all, the Algorithm searches the roots from the Graph. Starting from this roots the Algorithm creates levels and stores them in the member levels. The Member levels contains LinkedList Objects and the LinkedList per level contains Cell Wrapper Objects. After that the Algorithm tries to solve the edge crosses from level to level and goes top down and bottom up. After minimization of the edge crosses the algorithm moves each node to its bary center.

Returns:

list of lists of vertex wrappers

searchRoots

private java.util.LinkedList<V> searchRoots(java.util.Set<V> vertexSet)

Searches all Roots for the current Graph First the method marks any Node as not visited. Than calls searchRoots(MyGraphCell) for each not visited Cell. The Roots are stored in the LinkedList named roots

Parameters:

vertexSet - vertices

Returns:

returns a LinkedList with the roots

See Also:

searchRoots(java.util.Set<V>)

fillLevels

private java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> fillLevels(java.util.LinkedList<V> roots,
                                                                                             java.util.Set<V> vertexSet)

Method fills the levels and stores them in the member levels. Each level was represented by a LinkedList with Cell Wrapper objects. These LinkedLists are the elements in the levels LinkedList.

Parameters:

roots - roots

vertexSet - vertices

Returns:

list of list of vertex wrappers

fillLevels

private void fillLevels(java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> levels,
                        int level,
                        V rootNode)

Fills the LinkedList for the specified level with a wrapper for the MyGraphCell. After that the method called for each neighbor graph cell.

Parameters:

levels - The level for the graphCell

level - The levels for the graphCell

rootNode - The root node

solveEdgeCrosses

private void solveEdgeCrosses(java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> levels)

Solve edge crosses

Parameters:

levels - levels

solveEdgeCrosses

private int solveEdgeCrosses(boolean down,
                             java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> levels,
                             int levelIndex)

Solve edge crosses

Parameters:

down - down

levels - levels

levelIndex - level index

Returns:

edge crosses

moveToBarycenter

private void moveToBarycenter(java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> levels,
                              java.util.Set<V> vertexSet)

getNeighborEdges

private java.util.Collection<E> getNeighborEdges(V v)

moveToBarycenter

private int moveToBarycenter(java.util.LinkedList<java.util.LinkedList<SugiyamaLayout.CellWrapper<V>>> levels,
                             int levelIndex)

move

private boolean move(boolean toRight,
                     java.util.LinkedList<SugiyamaLayout.CellWrapper<V>> currentLevel,
                     int currentIndexInTheLevel,
                     int currentPriority)

Parameters:

toRight - true = try to move the currentWrapper to right; false = try to move the currentWrapper to left;

currentLevel - LinkedList which contains the CellWrappers for the current level

currentIndexInTheLevel - Current index in the level

currentPriority - Current priority

Returns:

The free GridPosition or -1 is position is not free.

reset

public void reset()