gumbo.visualize.data.layout
Class KinkyGraphLayoutOrderer

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

public class KinkyGraphLayoutOrderer

extends java.lang.Object

Utilities for kinky graph layout, processing stage II. Include phase I ordering of rank nodes by barycenter, and phase II reversal of equal barycenters, all to minimize local and global edge crossings.

Todo: The current algorithm is extremely slow. Also, it sometimes fails to untwine equal barycenter kinks.

Version:

$Revision: 1.8 $

Author:

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

Field Summary

static double	ROUGH_NOISE
static int	ROUGH_PHASE1_ITER_MAX
static int	ROUGH_PHASE2_ITER_MAX
static double	ROUGH_SPEED

Constructor Summary

KinkyGraphLayoutOrderer()

Method Summary

protected static void	doRoughMinorLayout(boolean downFirst, GraphNodeOrdering ordering) Iteratively re-orders nodes in ranks to minimize node link crossings.
protected static int	doRoughPhase1(boolean downFirst, int oldCross, GraphNodeOrdering ordering) Iteratively sweeps forward then backward through the ranks of an ordering reducing edge crossings.
protected static int	doRoughPhase1Down(GraphNodeOrdering ordering) Sweeps up through the ranks of an ordering trying to reduce edge crossings.
protected static int	doRoughPhase1Rank(int rankI, boolean doDown, GraphNodeOrdering ordering) Reorders nodes in the target rank based on the barycenters of nodes in the fixed rank to reduce edge crossings between the ranks.
protected static int	doRoughPhase1Up(GraphNodeOrdering ordering) Sweeps up through the ranks of an ordering trying to reduce edge crossings.
protected static int	doRoughPhase2(boolean downFirst, GraphNodeOrdering ordering) Iteratively sweeps forward then backward through the ranks of an ordering reducing edge crossings by reversing same barycenter nodes and re-doing phase I.
protected static int	doRoughPhase2Down(int oldCross, GraphNodeOrdering ordering) Sweeps down through the ranks of an ordering to reverse same barycenters and redo phase 1.
protected static int	doRoughPhase2Rank(int rankI, boolean doDown, int oldCross, GraphNodeOrdering ordering) Reverses same barycenters in the target rank, and redoes phase 1 each time.
protected static int	doRoughPhase2Up(int oldCross, GraphNodeOrdering ordering) Sweeps up through the ranks of an ordering to reverse same barycenters and redo phase 1.

Methods inherited from class java.lang.Object

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

Field Detail

ROUGH_PHASE1_ITER_MAX

public static final int ROUGH_PHASE1_ITER_MAX

See Also:

Constant Field Values

ROUGH_PHASE2_ITER_MAX

public static final int ROUGH_PHASE2_ITER_MAX

See Also:

Constant Field Values

ROUGH_SPEED

public static final double ROUGH_SPEED

See Also:

Constant Field Values

ROUGH_NOISE

public static final double ROUGH_NOISE

See Also:

Constant Field Values

Constructor Detail

KinkyGraphLayoutOrderer

public KinkyGraphLayoutOrderer()

Method Detail

doRoughMinorLayout

protected static void doRoughMinorLayout(boolean downFirst,
                                         GraphNodeOrdering ordering)

Iteratively re-orders nodes in ranks to minimize node link crossings. Does nothing if less than two ranks. (Sugiyama stage II, phase I & II)

doRoughPhase1

protected static int doRoughPhase1(boolean downFirst,
                                   int oldCross,
                                   GraphNodeOrdering ordering)

Iteratively sweeps forward then backward through the ranks of an ordering reducing edge crossings. The ordering is returned unchanged if crossings were not reduced. (Sugiyama stage II, phase I)

Parameters:

oldCross - The graph crossing count to be reduced. If negative, it will be computed from the ordering.

Returns:

-1 if the crossings not reduced; 0 if crossings reduced to or were initially zero; otherwise, the reduced graph crossing count (note that if oldCross was greater than the actual crossing count then a reduction could have occured without changing the graph).

doRoughPhase1Up

protected static int doRoughPhase1Up(GraphNodeOrdering ordering)

Sweeps up through the ranks of an ordering trying to reduce edge crossings. (Sugiyama stage II, phase I, up)

Returns:

The resulting graph crossing count. If the graph changed, the ordering's graph changed flag will be true, otherwise it will be false.

doRoughPhase1Down

protected static int doRoughPhase1Down(GraphNodeOrdering ordering)

Sweeps up through the ranks of an ordering trying to reduce edge crossings. (Sugiyama stage II, phase I, down)

Returns:

The resulting graph crossing count. If the graph changed, the ordering's graph changed flag will be true, otherwise it will be false.

doRoughPhase1Rank

protected static int doRoughPhase1Rank(int rankI,
                                       boolean doDown,
                                       GraphNodeOrdering ordering)

Reorders nodes in the target rank based on the barycenters of nodes in the fixed rank to reduce edge crossings between the ranks. (Sugiyama stage II, phase I, up)

Parameters:

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

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

Returns:

The resulting rank crossing count. If the graph changed, the ordering's graph changed flag will be true, otherwise it will be false.

doRoughPhase2

protected static int doRoughPhase2(boolean downFirst,
                                   GraphNodeOrdering ordering)

Iteratively sweeps forward then backward through the ranks of an ordering reducing edge crossings by reversing same barycenter nodes and re-doing phase I. The ordering is returned unchanged if crossings were not reduced. (Sugiyama stage II, phase II)

Returns:

-1 if the crossings not reduced; 0 if crossings reduced to or were initially zero; otherwise, the reduced graph crossing count.

doRoughPhase2Up

protected static int doRoughPhase2Up(int oldCross,
                                     GraphNodeOrdering ordering)

Sweeps up through the ranks of an ordering to reverse same barycenters and redo phase 1. The ordering is returned unchanged if crossings were not reduced. (Sugiyama stage II, phase II, up)

Parameters:

oldCross - The graph crossing count to be reduced (>=0).

Returns:

-1 if the crossings not reduced; 0 if crossings reduced to or were initially zero; otherwise, the reduced graph crossing count.

doRoughPhase2Down

protected static int doRoughPhase2Down(int oldCross,
                                       GraphNodeOrdering ordering)

Sweeps down through the ranks of an ordering to reverse same barycenters and redo phase 1. The ordering is returned unchanged if crossings were not reduced. (Sugiyama stage II, phase II, down)

Parameters:

oldCross - The graph crossing count to be reduced (>=0).

Returns:

-1 if the crossings not reduced; 0 if crossings reduced to or were initially zero; otherwise, the reduced graph crossing count.

doRoughPhase2Rank

protected static int doRoughPhase2Rank(int rankI,
                                       boolean doDown,
                                       int oldCross,
                                       GraphNodeOrdering ordering)

Reverses same barycenters in the target rank, and redoes phase 1 each time. The ordering is returned unchanged if crossings were not reduced.

Parameters:

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

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

oldCross - The graph crossing count to be reduced (>=0).

ordering - The target ordering. Never null.

Returns:

-1 if the crossings not reduced; 0 if crossings reduced to or were initially zero; otherwise, the reduced graph crossing count.