gumbo.visualize.data.layout
Class GraphNodeOrdering

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

public class GraphNodeOrdering

extends java.lang.Object

Similar to a graph node ranking (see GraphNodeRanking), but the nodes in each rank are ordered.

The nodes in an ordering constitute a set, with no nulls or duplicates. As such, each rank in an ordering is also a set. Placing a node in an ordering does not affect the topology of its graph, and a given node can be placed in more than one ordering (with the exception that GraphLayoutNode.setRanking() only allows a single ranking).

An ordering is loosely coupled to its host ranking. As such, changes to the host ranking are not reflected in the ordering. Instead, changes to the ordering and its ranking, such as adding or removing nodes, should be made to the ordering, which will relay the changes to its host ranking.

Version:

$Revision: 1.9 $

Author:

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

Constructor Summary

GraphNodeOrdering(GraphNodeOrdering ordering)
Creates an instance whose ranks are copied from the specified ordering.

GraphNodeOrdering(GraphNodeRanking ranking)
Creates an instance whose ranks are defined by the specified host ranking.

Method Summary

void	addNode(int rankI, GraphLayoutNode node) Adds a node to a rank in this ordering and its host ranking; and, calls GraphNodeRanking.initNodes() on the host ranking.
void	addNodes(int rankI, java.util.Collection nodes) Adds a group of nodes to a rank in this ordering and its host ranking.
static boolean	centerNodes(int dim, java.util.Collection nodes, java.util.Set hits, double centerPos, double same, java.util.List rank) Tries to compress and center a group of target nodes in a rank along a given dimension, even if the target nodes are discontiguous (mixed with hit nodes and non-target nodes).
static double	compressRank(int dim, int nodeI, int hitI, double delta, double same, java.util.List rank) Deprecated. Replaced by moveNode(), which uses nodes instead of indices.
boolean	containsNode(GraphLayoutNode node) Returns true if this ordering contains the specified node.
int	crossAfterCount(int rankI) Returns the number of link crossings between the target rank and the rank after it (rankI+1) based on their current orderings.
int	crossCount() Returns the number of link crossings in this ordering.
protected static int	findFirstHit(boolean doRight, int nodeI, java.util.Set hits, java.util.List rank) Finds the next hit node in a rank in a given direction.
boolean	getGraphChanged() Gets the graph changed flag of this ordering since the last resetGraphChanged().
int	getNodeCount() Gets the number of nodes in this ordering.
java.util.Set	getNodes() Returns an immutable view of the nodes in this ordering.
int	getRankCount() Gets the number of ranks in this ordering.
int	getRankIndex(GraphLayoutNode node) Gets the rank index of a node in this ordering.
GraphNodeRanking	getRanking() Gets the ranking associated with this ordering.
java.util.List	getRankList(GraphLayoutNode node) Gets an immutable view of the rank containing a given node in this ranking, as a list.
java.util.List	getRankList(int rankI) Gets an immutable view of a rank in this ordering, as a list.
java.util.Set	getRankSet(GraphLayoutNode node) Gets an immutable view of the rank containing a given node in this ranking, as a set.
java.util.Set	getRankSet(int rankI) Gets an immutable view of a rank in this ordering, as a set.
void	gridAlignRanks(int dim, double origin) Grid aligns the positions of the nodes in each rank.
void	indexCenterRank(int rankI, boolean useBefore, double speed, double noise) Computes and sets the index barycenters of the nodes in the target rank based on the node indices of the fixed reference rank.
java.util.List	indexList(int rankI, java.util.Collection nodes, java.util.List retVal) Returns a list with the nodes in a node group ordered according to their index in their target rank.
static double	moveNode(int dim, GraphLayoutNode node, java.util.Collection hits, double delta, double same, java.util.List rank) Tries to move a target node in a rank along a given dimension.
void	removeNode(GraphLayoutNode node) Removes a node from this ordering and its host ranking; and, calls GraphNodeRanking.initNodes() on the host ranking.
void	removeNodes(java.util.Collection nodes) Removes a group of nodes from this ordering and its host ranking.
void	resetGraphChanged() Resets the graph changed flag of this ordering to false.
void	setGraphChanged() Explicitely sets the graph changed flag of this ordering to true.
void	setRankList(int rankI, java.util.List rank) Sets a rank list in this ordering, replacing the previous ordering.
void	setRankLists(GraphNodeOrdering ordering) Sets the ranks lists in this ordering from those in the specified ordering.

Methods inherited from class java.lang.Object

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

Constructor Detail

GraphNodeOrdering

public GraphNodeOrdering(GraphNodeRanking ranking)

Creates an instance whose ranks are defined by the specified host ranking. Assumes that the ranking nodes have been initialized (see GraphNodeRanking.initNodes()).

Parameters:

ranking - The host ranking. Never null.

GraphNodeOrdering

public GraphNodeOrdering(GraphNodeOrdering ordering)

Creates an instance whose ranks are copied from the specified ordering.

Parameters:

ordering - The target ordering. Never null.

Method Detail

getRanking

public GraphNodeRanking getRanking()

Gets the ranking associated with this ordering.

resetGraphChanged

public void resetGraphChanged()

Resets the graph changed flag of this ordering to false.

setGraphChanged

public void setGraphChanged()

Explicitely sets the graph changed flag of this ordering to true.

getGraphChanged

public boolean getGraphChanged()

Gets the graph changed flag of this ordering since the last resetGraphChanged().

Returns:

True if the node order (i.e. graph topology) in any ranks has changed, if nodes have been added or removed, or if the flag was explicitely set with setGraphChanged(); false otherwise. Not intended to indicate if changes have occured within graph nodes.

indexCenterRank

public void indexCenterRank(int rankI,
                            boolean useBefore,
                            double speed,
                            double noise)

Computes and sets the index barycenters of the nodes in the target rank based on the node indices of the fixed reference rank. [Speed and noise are not needed at this time.]

Parameters:

rankI - Target rank index (0:size-1 depending on doBefore). Throws an exception if out of bounds.

useBefore - If true, the before rank (rankI-1) is used as the fixed reference rank; otherwise, the after rank (rankI+1) is used.

speed - Speed factor (>=0, <=1) applied to barycenter movement relative to old to new position delta. If zero, the new barycenter is ignored. If one, the old barycenter is ignored.

noise - Noise magnitude (>=0) applied to the barycenter movement delta. Ignored if zero.

Throws:

java.lang.IllegalStateException - Target's friend node not found in fixed rank.

crossAfterCount

public int crossAfterCount(int rankI)

Returns the number of link crossings between the target rank and the rank after it (rankI+1) based on their current orderings.

Parameters:

rankI - Target rank index (0:size-2). Throws an exception if out of bounds.

Returns:

Number of link crossings.

crossCount

public int crossCount()

Returns the number of link crossings in this ordering.

Returns:

Number of link crossings.

getNodes

public java.util.Set getNodes()

Returns an immutable view of the nodes in this ordering.

Returns:

Reference to an immutable view (GraphLayoutNode). Never null.

getRankSet

public java.util.Set getRankSet(int rankI)

Gets an immutable view of a rank in this ordering, as a set.

Parameters:

rankI - Rank index. Throws an exception if out of bounds.

Returns:

Immutable view of the rank (GraphLayoutNode). Never null.

setRankList

public void setRankList(int rankI,
                        java.util.List rank)

Sets a rank list in this ordering, replacing the previous ordering. The nodes in the new and old rank lists must be the same. The host ranking is unaffected. Sets graph changed if the rank order changes. A master mutator.

Parameters:

rankI - Rank index. Throws an exception if out of bounds.

rank - Value of the node rank (GraphLayoutNode). Possibly empty. Never null.

Throws:

java.lang.IllegalArgumentException - New and old rank nodes are different.

setRankLists

public void setRankLists(GraphNodeOrdering ordering)

Sets the ranks lists in this ordering from those in the specified ordering. The host ranking is unaffected.

Parameters:

ordering - The ordering with the new rank lists. Never null.

Throws:

java.lang.IllegalArgumentException - Ordering has a different ranking.

getRankList

public java.util.List getRankList(int rankI)

Gets an immutable view of a rank in this ordering, as a list.

Parameters:

rankI - Rank index. Throws an exception if out of bounds.

Returns:

Immutable view of the rank (GraphLayoutNode). Never null.

getRankSet

public java.util.Set getRankSet(GraphLayoutNode node)

Gets an immutable view of the rank containing a given node in this ranking, as a set.

Parameters:

node - Reference to the node. Ignored if null or missing.

Returns:

Immutable view of the rank (GraphLayoutNode). Null if node not found.

getRankList

public java.util.List getRankList(GraphLayoutNode node)

Gets an immutable view of the rank containing a given node in this ranking, as a list.

Parameters:

node - Reference to the node. Ignored if null or missing.

Returns:

Immutable view of the rank (GraphLayoutNode). Null if node not found.

getRankIndex

public int getRankIndex(GraphLayoutNode node)

Gets the rank index of a node in this ordering.

Parameters:

node - Reference to the node. Ignored if null or missing.

Returns:

Rank index. -1 if node not found.

getRankCount

public int getRankCount()

Gets the number of ranks in this ordering.

Returns:

Rank count.

getNodeCount

public int getNodeCount()

Gets the number of nodes in this ordering.

Returns:

Rank count.

containsNode

public boolean containsNode(GraphLayoutNode node)

Returns true if this ordering contains the specified node.

Parameters:

node - Reference to the node. Returns false if null.

Returns:

True if the node was found.

addNode

public void addNode(int rankI,
                    GraphLayoutNode node)

Adds a node to a rank in this ordering and its host ranking; and, calls GraphNodeRanking.initNodes() on the host ranking. Sets graph changed. A master mutator.

Parameters:

rankI - Rank index. Throws an exception if out of bounds.

node - Reference to the node. Ignored if null.

Throws:

java.lang.IllegalArgumentException - Node is already in this ordering.

removeNode

public void removeNode(GraphLayoutNode node)

Removes a node from this ordering and its host ranking; and, calls GraphNodeRanking.initNodes() on the host ranking. Sets graph changed. A master mutator.

Parameters:

node - Reference to the node. Ignored if null.

Throws:

java.lang.IllegalArgumentException - Node is not in this ordering.

addNodes

public void addNodes(int rankI,
                     java.util.Collection nodes)

Adds a group of nodes to a rank in this ordering and its host ranking.

Parameters:

rankI - Rank index. Throws an exception if out of bounds.

nodes - Value of the nodes (GraphLayoutNode). Ignored if null. Throws an exception if a node is already in this ranking.

removeNodes

public void removeNodes(java.util.Collection nodes)

Removes a group of nodes from this ordering and its host ranking.

Parameters:

nodes - Value of the nodes (GraphLayoutNode). Ignored if null. Ignores missing nodes.

indexList

public java.util.List indexList(int rankI,
                                java.util.Collection nodes,
                                java.util.List retVal)

Returns a list with the nodes in a node group ordered according to their index in their target rank.

Parameters:

rankI - Rank index. Throws an exception if out of bounds.

nodes - AbstractGroup of nodes (GraphLayoutNode) from the target rank. Never null. Throws an exception if not in the target rank.

retVal - Return value object. Ordered list (GraphLayoutNode). Never null.

Returns:

Reference to retVal. Never null.

gridAlignRanks

public void gridAlignRanks(int dim,
                           double origin)

Grid aligns the positions of the nodes in each rank. All nodes are assumed to be the same size, which includes any inter-node gap.

Parameters:

dim - The affected layout position dimension (1:2).

origin - The position of the minimum extent of the most negative node.

compressRank

public static double compressRank(int dim,
                                  int nodeI,
                                  int hitI,
                                  double delta,
                                  double same,
                                  java.util.List rank)

Deprecated. Replaced by moveNode(), which uses nodes instead of indices.

Tries to change the layout position of the target node in a rank of nodes by delta, along a given dimension. Inter-node gaps between the target node and an immovable hit node, if any, will be used until delta is absorbed.

Parameters:

dim - The affected layout position dimension (1:2).

nodeI - The target node index (0:size-1) in rankI to be moved.

hitI - The immovable node index in rankI (0:size-1). <0 if none. If no hit node then the shift will always be complete (no remainder).

delta - The desired change in target node position. The sign indicates the shift direction (>0 to right, <0 to left, 0 do nothing).

same - The tolerance for testing equality (>=0). Zero if <0.

rank - The target rank (GraphLayoutNode). Never null.

Returns:

The remaining delta that the target needs to be shifted. If equal to delta then the graph was unchanged. If zero, the target shift was complete.

centerNodes

public static boolean centerNodes(int dim,
                                  java.util.Collection nodes,
                                  java.util.Set hits,
                                  double centerPos,
                                  double same,
                                  java.util.List rank)

Tries to compress and center a group of target nodes in a rank along a given dimension, even if the target nodes are discontiguous (mixed with hit nodes and non-target nodes).

The algorithm is not very efficient, and disturbs non-target nodes more than it needs to.

Parameters:

dim - The affected layout position dimension (1:2).

nodes - The target nodes (GraphLayoutNode) to be moved. Must be a set. Throws an exception if not in the rank or is a hit. Never null.

hits - Immovable hit nodes. Null or empty if none. If no hit nodes the shift will always be complete (no remainder). Hits missing from the rank are ignored.

centerPos - The desired center position of the target nodes.

same - The tolerance for testing equality (>=0). Zero if <0.

rank - The target rank (GraphLayoutNode). Never null.

Returns:

True if graph changed, otherwise false.

findFirstHit

protected static int findFirstHit(boolean doRight,
                                  int nodeI,
                                  java.util.Set hits,
                                  java.util.List rank)

Finds the next hit node in a rank in a given direction.

Parameters:

doRight - If true, searches to the right; otherwise, to the left.

nodeI - Index of the starting node in the rank. Throws an exception if not in the rank.

hits - Rank hit nodes. Never null.

Returns:

Index of the first hit node found in the rank, which may be nodeI. -1 if no hit found.

moveNode

public static double moveNode(int dim,
                              GraphLayoutNode node,
                              java.util.Collection hits,
                              double delta,
                              double same,
                              java.util.List rank)

Tries to move a target node in a rank along a given dimension. Inter-node gaps between the target node and the first immovable hit node, if any, will be used until the target position delta is absorbed.

Parameters:

dim - The affected layout position dimension (1:2).

node - The target node to be moved. Throws an exception if not in the rank. If the target node is in hits, nothing happens. Never null.

hits - Immovable hit nodes. Null or empty if none. If no hit nodes the shift will always be complete (no remainder). Hits missing from the rank are ignored.

delta - The desired change in target node position. The sign indicates the shift direction (>0 to right, <0 to left, 0 do nothing).

same - The tolerance for testing equality (>=0). Zero if <0.

rank - The target rank (GraphLayoutNode). Never null.

Returns:

The remaining delta that the target needs to be shifted. If equal to delta then the graph was unchanged. If zero, the target shift was complete.