y.layout.grouping
Class Grouping

java.lang.Object
  y.layout.grouping.Grouping

All Implemented Interfaces:

GroupingKeys

public class Grouping
extends java.lang.Object
implements GroupingKeys

This class provides convenient and efficient access to the hierarchic graph structure.

The grouping information is provided through DataProviders registered with the graph with keys GroupingKeys.NODE_ID_DPKEY, GroupingKeys.PARENT_NODE_ID_DPKEY and GroupingKeys.GROUP_DPKEY. It describes the hierarchy as a tree where a group node is the parent of the nodes that it contains.

This is an example graph that contains group nodes.

The hierarchy tree of the grouped graph reveals the relationship among the nodes. The corresponding nodes have the same labels as in the grouped graph. Group nodes are considered as the parents of their content which can consist of group nodes and/or normal nodes. Top-level nodes are children of a virtual root. Leaf nodes can either be normal nodes or empty groups.

Once an instance of Grouping is not needed anymore, it should be disposed of.

Field Summary

Fields inherited from interface y.layout.grouping.GroupingKeys

GROUP_DPKEY, GROUP_NODE_INSETS_DPKEY, MINIMUM_NODE_SIZE_DPKEY, NODE_ID_DPKEY, PARENT_NODE_ID_DPKEY

Constructor Summary

Grouping(Graph graph)
Creates a new Grouping instance that represents the hierarchy of the graph.

Method Summary

protected NodeMap	createInfoMap(Graph graph) Creates a NodeMap to store hierarchy information for each node.
void	dispose() Disposes of all internal data structures held by this instance.
protected void	disposeInfoMap(Graph graph, NodeMap infoMap) Disposes of the NodeMap created to store hierarchy information for each node.
NodeList	getChildren(Node parent) Returns the direct children of the given group node.
NodeList	getDescendants(Node parent) Returns all descendants of the given group node.
EdgeList	getEdgesGoingIn(Node group) Returns all edges crossing the bounds of the given group node such that their targets are inside the group node while their sources lie outside the group node.
EdgeList	getEdgesGoingOut(Node group) Returns all edges crossing the bounds of the given group node such that their sources are inside the group node while their targets lie outside the group node.
Graph	getGraph() Returns the Graph instance for which this Grouping object provides hierarchy information.
LayoutGraph	getLayoutGraph() Returns the LayoutGraph instance for which this Grouping object provides hierarchy information.
Node	getNearestCommonAncestor(Node node1, Node node2) Returns the nearest common ancestor of the given nodes in the hierarchy structure.
Node	getParent(Node node) Returns the parent for the given node.
Node	getRepresentative(Node node, Node group) Returns an immediate child of the group node that represents the given node.
Node	getRoot() Returns a Node instance associated with the virtual root of the hierarchy tree.
boolean	hasChildren(Node node) Determines whether or not the given node is a group node with children.
protected void	init() Initializes internal data structures.
static boolean	isFlat(Graph graph) Returns whether or not the given graph is flat.
static boolean	isGrouped(Graph graph) Returns whether or not the given graph is grouped.
boolean	isGroupNode(Node node) Determines whether or not the given node is a group node.
boolean	isNormalEdge(Edge edge) Determines whether or not the given edge is a normal edge as opposed to an edge that crosses any group node bounds.

Methods inherited from class java.lang.Object

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

Constructor Detail

Grouping

public Grouping(Graph graph)

Creates a new Grouping instance that represents the hierarchy of the graph.

The hierarchy information is cached during the constructor call. Later modifications to the graph are not considered and may lead to errors when using this Grouping instance.

Since Grouping holds the current state of the graph instance, it should be disposed of once it is not needed anymore.

Parameters:

graph - the graph instance from which the hierarchy information is obtained

Method Detail

init

protected void init()

Initializes internal data structures.

This method is called from Grouping(Graph) and retrieves the state of the hierarchic graph at the moment of invocation. It may be overridden to append additional information used for group handling.

This method creates a state that should be disposed of if this instance of Grouping is not needed anymore.

See Also:

dispose()

getLayoutGraph

public LayoutGraph getLayoutGraph()

Returns the LayoutGraph instance for which this Grouping object provides hierarchy information.

Retrieving the LayoutGraph is only possible if this Grouping is associated with an instance of LayoutGraph class.

Returns:

the graph for which the hierarchic information is stored

getGraph

public Graph getGraph()

Returns the Graph instance for which this Grouping object provides hierarchy information.

Returns:

the graph for which the hierarchic information is stored or null if this instance was already disposed of.

createInfoMap

protected NodeMap createInfoMap(Graph graph)

Creates a NodeMap to store hierarchy information for each node.

This method is called in init() and may be overridden to customize how the NodeMap is created.

Parameters:

graph - the current graph

Returns:

the new instance of NodeMap

See Also:

init(), disposeInfoMap(Graph, NodeMap)

disposeInfoMap

protected void disposeInfoMap(Graph graph,
                              NodeMap infoMap)

Disposes of the NodeMap created to store hierarchy information for each node.

This method is called in dispose() and may be overridden to revert changes from createInfoMap(Graph).

Parameters:

graph - the current graph

infoMap - the NodeMap which contains the hierarchy information for each node

See Also:

dispose(), createInfoMap(Graph)

getParent

public Node getParent(Node node)

Returns the parent for the given node. The parent is the containing group node.

Parameters:

node - the node for which the parent is determined

Returns:

the parent of the given node or null for a top-level node

Throws:

java.lang.IllegalArgumentException - if the given node is null

See Also:

getChildren(Node), getDescendants(Node), getNearestCommonAncestor(Node, Node)

getRoot

public Node getRoot()

Returns a Node instance associated with the virtual root of the hierarchy tree. This instance can be given to the getChildren(Node) to obtain the nodes of the top level of the hierarchy.

This Node instance is not part of the graph.

Returns:

the virtual root of the hierarchy tree

See Also:

getChildren(Node)

getChildren

public NodeList getChildren(Node parent)

Returns the direct children of the given group node.

If the virtual root of the hierarchy tree is passed, all top-level nodes are returned.

Parameters:

parent - the group node

Returns:

a set of child nodes of the given parent node

See Also:

getRoot(), getParent(Node), getDescendants(Node)

Sample Graphs:

The marked nodes are children of group node 5 (grouped graph)

The marked nodes are children of group node 5 (hierarchy tree)

getDescendants

public NodeList getDescendants(Node parent)

Returns all descendants of the given group node. All nodes in the subtree rooted at this group node are collected recursively.

If the virtual root of the hierarchy tree is passed, all nodes in the graph are returned.

Parameters:

parent - the group node

Returns:

a set of nodes that belong to a subtree of the hierarchy tree rooted at the given parent

See Also:

getRoot(), getParent(Node), getChildren(Node)

Sample Graphs:

The marked nodes are descendants of group node 5 (grouped graph)

The marked nodes are descendants of group node 5(hierarchy tree)

isGroupNode

public boolean isGroupNode(Node node)

Determines whether or not the given node is a group node. While group nodes may have children, normal nodes never have children.

Parameters:

node - the potential group node

Returns:

true if the given node is a group node or is null, false otherwise

See Also:

hasChildren(Node)

hasChildren

public boolean hasChildren(Node node)

Determines whether or not the given node is a group node with children. Normal nodes never have children.

Parameters:

node - the potential parent

Returns:

true if the given node has children, false otherwise

See Also:

getChildren(Node), isGroupNode(Node)

isNormalEdge

public boolean isNormalEdge(Edge edge)

Determines whether or not the given edge is a normal edge as opposed to an edge that crosses any group node bounds. Source and target of a normal edge are part of the same hierarchy level and share the same parent node.

Parameters:

edge - the edge to check

Returns:

true if the given edge is normal, false otherwise

See Also:

getEdgesGoingIn(Node), getEdgesGoingOut(Node)

getEdgesGoingIn

public EdgeList getEdgesGoingIn(Node group)

Returns all edges crossing the bounds of the given group node such that their targets are inside the group node while their sources lie outside the group node.

Parameters:

group - the group node whose bounds are crossed

Returns:

a set of edges that cross the bounds of the group node starting outside the group node

See Also:

getEdgesGoingOut(Node), isNormalEdge(Edge)

Sample Graph:

The marked edges cross the bounds of the group node from outside to the inside

getEdgesGoingOut

public EdgeList getEdgesGoingOut(Node group)

Returns all edges crossing the bounds of the given group node such that their sources are inside the group node while their targets lie outside the group node.

Parameters:

group - the group node whose bounds are crossed

Returns:

a set of edges that cross the bounds of the group node starting inside the group node

See Also:

getEdgesGoingIn(Node), isNormalEdge(Edge)

Sample Graph:

The marked edges cross the bounds of the group node from inside to the outside

getRepresentative

public Node getRepresentative(Node node,
                              Node group)

Returns an immediate child of the group node that represents the given node. If this node is already a child of the group node, the group node will be its representative. In case the node is located further down in the hierarchy, the child of the group node, which is also an ancestor of the node, is used. There is no representative if the node is not a descendant of the group.

Parameters:

node - the node for which a representative is searched

group - the group node to which the representative should belong

Returns:

the representative or null if the node is not a descendant of the group

Throws:

java.lang.IllegalArgumentException - if the given node is null

Sample Graphs:

Node 4 is the representative for node 2 in group node 5 (grouped graph)

Node 4 is the representative for node 2 in group node 5 (hierarchy tree)

dispose

public void dispose()

Disposes of all internal data structures held by this instance.

Grouping should be disposed of when it is not needed anymore, or if the state of the graph changes (e.g. new nodes are added).

After disposal this instance becomes useless. For subsequent group handling, a new Grouping instance needs to be created.

isGrouped

public static boolean isGrouped(Graph graph)

Returns whether or not the given graph is grouped. A graph is considered to be grouped if there are DataProviders registered with the graph with keys GroupingKeys.GROUP_DPKEY, GroupingKeys.NODE_ID_DPKEY and GroupingKeys.PARENT_NODE_ID_DPKEY.

Parameters:

graph - the input graph

Returns:

true if the graph contains hierarchic information, false otherwise

See Also:

isFlat(Graph)

isFlat

public static boolean isFlat(Graph graph)

Returns whether or not the given graph is flat. A graph is considered to be flat if there exist no group nodes or there exist group nodes but none of them has children.

Parameters:

graph - the input graph

Returns:

true if there are no groups or only empty groups in the graph, false otherwise

See Also:

isGrouped(Graph)

getNearestCommonAncestor

public Node getNearestCommonAncestor(Node node1,
                                     Node node2)

Returns the nearest common ancestor of the given nodes in the hierarchy structure.

The nearest common ancestor is the local root of the smallest subtree in the hierarchy tree that contains both nodes. This group is the first node that contains these two nodes. If no such node exists, the virtual root is returned.

Common ancestors in special cases:

• node1 == node2: the parent of node1/node2
• node1 is parent of node2: the parent of node1
• node2 is parent of node1: the parent of node2

Parameters:

node1 - one of the two nodes whose common ancestor is determined

node2 - one of the two nodes whose common ancestor is determined

Returns:

the nearest common ancestor node or getRoot()

Sample Graphs:

The nearest common ancestor of the nodes 1 and 2 is group node 5 (grouped graph)

The nearest common ancestor of the nodes 1 and 2 is group node 5 (hierarchy tree)