gumbo.visualize.data.layout
Class KinkyGraphLayoutRanker

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

public class KinkyGraphLayoutRanker

extends java.lang.Object

Utilities for kinky graph layout, processing stage I. Include sorting graph nodes into distinct layout groups, organizing the nodes in each group into "horizontal" ranks of nodes such that no edges are horizontal, and adding kink nodes to ranks spanned by long edges.

Note that in creating different rankings of a graph in the same layout it is important for a node to only be in one ranking. Otherwise, results will be unpredictable because a node's layout state is specific to its ranking and rankings only maintain references to the nodes, not copies.

Todo: Better minimization of edge distance see AT&T paper).

Version:

$Revision: 1.12 $

Author:

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

Constructor Summary

KinkyGraphLayoutRanker()

Method Summary

static void	doConnectedRanking(java.util.Set seeds, boolean floatSources, boolean floatSinks, java.util.Set prunes, GraphNodeRanking retVal) Creates a "connected" ranking from a group of seed nodes, which includes the seeds and all forward and backward traced nodes, with sources and sinks but without source and sink trace-through.
static void	doForwardRanking(java.util.Set seeds, boolean floatSinks, java.util.Set prunes, GraphNodeRanking retVal) Creates a "forward" ranking from a group of seed nodes, typically source nodes, which includes the seeds and all forward traced nodes, with sources and sinks but without source and sink trace-through.
protected static void	doKinkEdges(GraphNodeRanking ranking) Adds kinks along kinky edges that span multiple ranks in a ranking.
static void	doMainRanking(java.util.Set sources, GraphNodeRanking sourceRanking, java.util.Set sinks, GraphNodeRanking sinkRanking, GraphNodeRanking retVal) Deprecated. Used in earlier releases to broduce a rankings connected to all sources and sinks. This avoids cross ranking edges but introduces grunge into the main (forward) ranking. Before resurecting this code it needs to be verified with the latest release.
protected static void	doRankNodes(java.util.Collection seeds, boolean traceForward, boolean traceBackward, java.util.Set prunes, GraphNodeRanking retVal) Traces nodes in a graph from seed nodes, ranking the found nodes by relative distance from the seed nodes.
protected static void	doRefinedRanking(GraphNodeRanking ranking) Single-pass refinement of a raw ranking by moving a node up, never down, in the ranking to the rank just after that of its lowest connected node.

Methods inherited from class java.lang.Object

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

Constructor Detail

KinkyGraphLayoutRanker

public KinkyGraphLayoutRanker()

Method Detail

doForwardRanking

public static void doForwardRanking(java.util.Set seeds,
                                    boolean floatSinks,
                                    java.util.Set prunes,
                                    GraphNodeRanking retVal)

Creates a "forward" ranking from a group of seed nodes, typically source nodes, which includes the seeds and all forward traced nodes, with sources and sinks but without source and sink trace-through.

Parameters:

seeds - The seed nodes (GraphLayoutNode) to be traced and ranked. Never null.

floatSinks - If true, sinks will float in the ranking. If false, and there are sink nodes, the sinks will be moved to a new last rank.

prunes - Nodes (GraphLayoutNode) that will be pruned from the ranking (see doRankNodes()). Null if none.

retVal - Return value object. Node ranking (GraphLayoutNode). See doRankNodes(). Never null.

doConnectedRanking

public static void doConnectedRanking(java.util.Set seeds,
                                      boolean floatSources,
                                      boolean floatSinks,
                                      java.util.Set prunes,
                                      GraphNodeRanking retVal)

Creates a "connected" ranking from a group of seed nodes, which includes the seeds and all forward and backward traced nodes, with sources and sinks but without source and sink trace-through.

Parameters:

seeds - The seed nodes (GraphLayoutNode) to be traced and ranked. Never null.

floatSources - If true, sources will float in the ranking. If false, and there are source nodes, the sources will be moved to a new first rank.

floatSinks - If true, sinks will float in the ranking. If false, and there are sink nodes, the sinks will be moved to a new last rank.

prunes - Nodes (GraphLayoutNode) that will be pruned from the ranking (see doRankNodes()). Null if none.

retVal - Return value object. Node ranking (GraphLayoutNode). See doRankNodes(). Never null.

doRankNodes

protected static void doRankNodes(java.util.Collection seeds,
                                  boolean traceForward,
                                  boolean traceBackward,
                                  java.util.Set prunes,
                                  GraphNodeRanking retVal)

Traces nodes in a graph from seed nodes, ranking the found nodes by relative distance from the seed nodes. Seed nodes are traced and ranked in iterator order. The ranking is such that two nodes that are linked will never be in the same rank, including seeds (no flat edges). Sources and sinks are included but without source and sink trace-through.

Parameters:

seeds - The seed nodes (GraphLayoutNode). Must be a subset of nodes. Never null.

traceForward - If true, forward links are traced.

traceBackward - If true, backward links are traced.

prunes - Nodes (GraphLayoutNode) that will be excluded from the trace and result, except for seeds, which will be traced even if pruned (at the end). If null, all traced nodes will be included in the result.

retVal - Return value object. Node ranking (GraphLayoutNode). The first rank is the seed rank, which will be empty only if there are no seeds or if all the seeds are pruned. All other ranks are non-empty. Note that the seed rank will not contain all of the seeds if any seeds are interconnected. Never null.

doRefinedRanking

protected static void doRefinedRanking(GraphNodeRanking ranking)

Single-pass refinement of a raw ranking by moving a node up, never down, in the ranking to the rank just after that of its lowest connected node.

Parameters:

ranking - Raw ranking (GraphLayoutNode) to be refined. Never null.

doMainRanking

public static void doMainRanking(java.util.Set sources,
                                 GraphNodeRanking sourceRanking,
                                 java.util.Set sinks,
                                 GraphNodeRanking sinkRanking,
                                 GraphNodeRanking retVal)

Deprecated. Used in earlier releases to broduce a rankings connected to all sources and sinks. This avoids cross ranking edges but introduces grunge into the main (forward) ranking. Before resurecting this code it needs to be verified with the latest release.

Creates a "main" ranking by combining a source and sink group ranking, which are assumed to be distinct sets.

Parameters:

sources - Nodes (GraphLayoutNode) that will be in the source (first) rank of the result. Typically all the sources related to the source and sink rankings. Never null.

sourceRanking - Ranking (GraphLayoutNode) from source node seeds, but without the source node seeds. Never null.

sinks - Nodes (GraphLayoutNode) that will be in the sink (last) rank of the result. Typically all the sinks related to the source and sink rankings. Never null.

sinkRanking - Ranking (GraphLayoutNode) from sink node seeds, but without the sink node seeds. Never null.

retVal - Return value object. Normal node ranking (GraphLayoutNode), with the source nodes in the first rank and the sink nodes in the last rank. Never null.

doKinkEdges

protected static void doKinkEdges(GraphNodeRanking ranking)

Adds kinks along kinky edges that span multiple ranks in a ranking. Partial edges and non-kinky edges are ignored. (Sugiyama step I, phase II)