gumbo.visualize.data.layout
Class KinkyGraphLayoutPlacer

java.lang.Object
  |
  +--gumbo.visualize.data.layout.KinkyGraphLayoutPlacer

public class KinkyGraphLayoutPlacer

extends java.lang.Object

Utilities for kinky graph layout, processing stage III, for positioning nodes in layout space. Includes crude major and minor dimension placement, kink link straightening, and barycenter centering.

Todo: Eliminate negative priorities, simplifying priority allocation and handling. Do kink link straightening and spreading after priority placement to cleanup minor cases of crooked kinks. Generalize spreading (i.e. trace and shift) portion of kink straightening. Figure out why prioty placement often doesn't converge.

Version:

$Revision: 1.10 $

Author:

Jon Barrilleaux (jonb@jmbaai.com) of JMB and Associates Inc.

Field Summary

static int	FINE_BALANCE_ITER_MAX
static int	FINE_ITER_MAX
static int	FINE_KINK_ITER_MAX
static double	FINE_SAME

Constructor Summary

KinkyGraphLayoutPlacer()

Method Summary

protected static void	doCrudeMinorLayout(int dim, Point3 origin, double extraGap, GraphNodeOrdering ordering) Distibutes nodes in ordering in layout space by rank along the specified minor axis, centered about the origin.
protected static void	doFinalMinorLayout(int dim, Point3 origin, GraphNodeOrdering ordering) Absolutely positions the ranking nodes by centering it along the specified dimension about the specified origin.
protected static boolean	doFineMinorBalance(int dim, GraphNodeOrdering ordering) Iteratively sweeps up and down through the ranks of an ordering balancing "dangling" nodes relative to their parents.
protected static boolean	doFineMinorBalanceRank(int rankI, boolean doDown, int dim, GraphNodeOrdering ordering) Balances "dangling" nodes in the target rank relative to their parents in the fixed fixed rank.
protected static boolean	doFineMinorBalanceSweep(boolean doDown, int dim, GraphNodeOrdering ordering) Sweeps through the ranks of an ordering in a given direction.
protected static boolean	doFineMinorKinks(int dim, GraphNodeOrdering ordering) Iteratively sweeps up and down through the ranks of an ordering straightening kink-to-kink links and shifting surrounding nodes.
protected static boolean	doFineMinorKinksRank(int rankI, boolean doDown, java.util.Set placed, int dim, GraphNodeOrdering ordering) Performs kink-to-kink straighteneing for the nodes in the target rank.
protected static boolean	doFineMinorKinksSweep(boolean doDown, int dim, java.util.Set placed, GraphNodeOrdering ordering) Sweeps through the ranks of an ordering in a given direction.
protected static void	doFineMinorLayout(int dim, GraphNodeOrdering ordering) Iteratively sweeps up and down the ordering ranks positioning nodes along the specified minor axis based on the position priority of the nodes (see doPrioritizePositions()).
protected static void	doFineMinorPriority(GraphNodeOrdering ordering) Initializes the before and after (friend) priorities of the nodes in an ordering.
protected static boolean	doFineMinorRank(int rankI, boolean doDown, int dim, GraphNodeOrdering ordering) Performs fine layout of target nodes in the target rank of an ordering by moving target nodes towards their fixed rank barycenters.
protected static boolean	doFineMinorSweep(boolean doDown, int dim, GraphNodeOrdering ordering) Sweeps through the ranks of an ordering in a given direction.
protected static double	doMajorLayout(double origin, double extraGap, GraphNodeOrdering ordering) Distibutes nodes in an ordering by rank along the major layout space axis.
protected static void	doMultiEdgeLayout(Size3 kinkSize, java.util.Collection edges) Adds kink nodes to multi-edges based on the target node sizes (which includes the inter-node gap) and positions.
protected static void	doSelfLoopLayout(Size3 kinkSize, java.util.Collection edges) Adds kink nodes to self loop edges based on the target node size (which includes the inter-node gap) and position.

Methods inherited from class java.lang.Object

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

Field Detail

FINE_SAME

public static final double FINE_SAME

See Also:

Constant Field Values

FINE_ITER_MAX

public static final int FINE_ITER_MAX

See Also:

Constant Field Values

FINE_KINK_ITER_MAX

public static final int FINE_KINK_ITER_MAX

See Also:

Constant Field Values

FINE_BALANCE_ITER_MAX

public static final int FINE_BALANCE_ITER_MAX

See Also:

Constant Field Values

Constructor Detail

KinkyGraphLayoutPlacer

public KinkyGraphLayoutPlacer()

Method Detail

doMajorLayout

protected static double doMajorLayout(double origin,
                                      double extraGap,
                                      GraphNodeOrdering ordering)

Distibutes nodes in an ordering by rank along the major layout space axis. Ranks will be spaced according to the largest nodes in adjacent ranks to avoid overlap. Empty ranks will be ignored. All other dimensions of the node positions will remain unchanged. Node size is assumed to include an inter-node gap.

Parameters:

origin - Position of the leading edge of the first rank.

extraGap - Extra gap, positive or negative, added between adjacent nodes.

ordering - Node ordering to be laid out. Never null.

Returns:

The position of the last rank's trailing edge. Same as origin if nothing was placed.

doCrudeMinorLayout

protected static void doCrudeMinorLayout(int dim,
                                         Point3 origin,
                                         double extraGap,
                                         GraphNodeOrdering ordering)

Distibutes nodes in ordering in layout space by rank along the specified minor axis, centered about the origin. All other dimensions of the node positions are unaffected. Node size is assumed to include an inter-node gap.

Parameters:

dim - The minor dimension (1 or 2).

origin - Origin of the layout in layout space. Never null.

extraGap - Extra gap, positive or negative, added between adjacent nodes.

doFinalMinorLayout

protected static void doFinalMinorLayout(int dim,
                                         Point3 origin,
                                         GraphNodeOrdering ordering)

Absolutely positions the ranking nodes by centering it along the specified dimension about the specified origin.

doSelfLoopLayout

protected static void doSelfLoopLayout(Size3 kinkSize,
                                       java.util.Collection edges)

Adds kink nodes to self loop edges based on the target node size (which includes the inter-node gap) and position. A self-loop edge is one whose head and tail node are the same. Only affects kinkable self-loop edges. Should be done after all other node layout is complete.

Parameters:

edges - AbstractGroup of edges possibly containing self-loops. Never null.

doMultiEdgeLayout

protected static void doMultiEdgeLayout(Size3 kinkSize,
                                        java.util.Collection edges)

Adds kink nodes to multi-edges based on the target node sizes (which includes the inter-node gap) and positions. A multi-edge edge is one that has no kinks nodes and has the same head and tail node (same or different direction) as another kinkless edge. Only affects multi-edge edges that are kinkable. Should be done after all other node layout is complete.

Parameters:

kinkSize - Edge kink size, in layout space. Never null.

edges - AbstractGroup of edges possibly containing self-loops. Never null.

doFineMinorLayout

protected static void doFineMinorLayout(int dim,
                                        GraphNodeOrdering ordering)

Iteratively sweeps up and down the ordering ranks positioning nodes along the specified minor axis based on the position priority of the nodes (see doPrioritizePositions()). The positioning will start at the origin, but may drift. All other node position dimensions will remain unchanged. (Sugiyama stage III)

doFineMinorSweep

protected static boolean doFineMinorSweep(boolean doDown,
                                          int dim,
                                          GraphNodeOrdering ordering)

Sweeps through the ranks of an ordering in a given direction.

Returns:

True if the graph changed; otherwise false.

doFineMinorRank

protected static boolean doFineMinorRank(int rankI,
                                         boolean doDown,
                                         int dim,
                                         GraphNodeOrdering ordering)

Performs fine layout of target nodes in the target rank of an ordering by moving target nodes towards their fixed rank barycenters. Target nodes are placed in priority order, highest to lowest. Only nodes with an equal or lesser priority in the target ranks will be affected. If a node's priority is zero, it will not be placed, but will be moved by all other nodes. If a node's priority is negative, it will not be placed, and will be immovable (always a hit node).

Parameters:

rankI - The target rank index (0:size-1, depends on doDown).

doDown - If true, the fixed rank is before the target rank (rankI-1); otherwise, the fixed rank is after it (rankI+1).

dim - The affected position dimension (0:2).

ordering - The target ordering. Never null.

Returns:

True if the graph changed; otherwise false.

doFineMinorPriority

protected static void doFineMinorPriority(GraphNodeOrdering ordering)

Initializes the before and after (friend) priorities of the nodes in an ordering. The priority is based on the before and after node counts, with no-link nodes having the lowest priority, kink nodes having the highest, and the rest having a priority proportional to the friend count.

doFineMinorKinks

protected static boolean doFineMinorKinks(int dim,
                                          GraphNodeOrdering ordering)

Iteratively sweeps up and down through the ranks of an ordering straightening kink-to-kink links and shifting surrounding nodes.

Returns:

True if the graph changed.

doFineMinorKinksSweep

protected static boolean doFineMinorKinksSweep(boolean doDown,
                                               int dim,
                                               java.util.Set placed,
                                               GraphNodeOrdering ordering)

Sweeps through the ranks of an ordering in a given direction.

Returns:

True if the graph changed; otherwise false.

doFineMinorKinksRank

protected static boolean doFineMinorKinksRank(int rankI,
                                              boolean doDown,
                                              java.util.Set placed,
                                              int dim,
                                              GraphNodeOrdering ordering)

Performs kink-to-kink straighteneing for the nodes in the target rank.

Returns:

True if the graph changed; otherwise false.

doFineMinorBalance

protected static boolean doFineMinorBalance(int dim,
                                            GraphNodeOrdering ordering)

Iteratively sweeps up and down through the ranks of an ordering balancing "dangling" nodes relative to their parents.

Returns:

True if the graph changed.

doFineMinorBalanceSweep

protected static boolean doFineMinorBalanceSweep(boolean doDown,
                                                 int dim,
                                                 GraphNodeOrdering ordering)

Sweeps through the ranks of an ordering in a given direction.

Returns:

True if the graph changed; otherwise false.

doFineMinorBalanceRank

protected static boolean doFineMinorBalanceRank(int rankI,
                                                boolean doDown,
                                                int dim,
                                                GraphNodeOrdering ordering)

Balances "dangling" nodes in the target rank relative to their parents in the fixed fixed rank. Dangling nodes are nodes with only a single connection, to the "parent" node. Only dangling nodes in the target rank will be affected.

Parameters:

rankI - The target rank index (0:size-1, depening on doDown).

doDown - If true, the fixed rank is before the target rank (rankI-1); otherwise, the fixed rank is after (rankI+1).

dim - The affected position dimension (0:2).

ordering - The target ordering. Never null.

Returns:

True if the graph changed; otherwise false.