Managing Graph Hierarchies

Managing Graph Hierarchies
Prev	Chapter 7. Graph Hierarchies	Next

The management of a graph hierarchy is a multi-faceted undertaking that is handled by a small number of classes. Adding support for grouping and nesting to a "flat" graph can easily be achieved with little effort.

Class HierarchyManager

Class HierarchyManager maintains the model that is behind graph hierarchies, and manages all changes relevant to this model. Among other things, the HierarchyManager's responsibilities include:

Creation and removal of group nodes and folder nodes
Grouping and ungrouping nodes
Nesting and un-nesting of graph structures
Creation of a folder node's inner graph
Handling of inter-edges
Maintenance of the node visiting order for both hit-testing and drawing the graph elements
Provision of graph element information

Adding support for both grouping and nesting to a graph is achieved by creating a HierarchyManager instance that is associated with a given graph, which is considered the hierarchy's root graph. Example 7.1, “Adding support for grouping and nesting to a graph” demonstrates how to add a HierarchyManager instance to a yet "flat" graph, i.e., one that lacks support for grouping or nesting.

Important

There must not be more than one HierarchyManager associated with a given graph.

Example 7.1. Adding support for grouping and nesting to a graph

// 'rootGraph' is of type y.view.Graph2D.

// Create a hierarchy manager with the given graph.
HierarchyManager hm = new HierarchyManager(rootGraph);

Access to the HierarchyManager associated with a graph is provided through the following static method of class HierarchyManager:

static HierarchyManager getInstance(Graph graph)
Description	Returns the HierarchyManager instance associated with the given graph.

In order to keep the model it is maintaining synchronized and consistent, HierarchyManager relies on events that signal graph structure changes. The GraphListener that is used to listen for these events is registered with the root graph at HierarchyManager creation time. By means of class DefaultHierarchyGraphFactory, which, among other things, is used by the HierarchyManager to create so-called inner graphs (see below), this listener is ultimately registered with all graphs in a graph hierarchy.

Graph Hierarchy

A graph hierarchy consists of normal nodes, group nodes with their contents, and folder nodes. Group nodes and folder nodes are special proxy elements that can only be created by the HierarchyManager:

Node createGroupNode(Node parentNode) Node createGroupNode(Graph parentGraph)
Description	Methods to create a group node.
Node createFolderNode(Node parentNode) Node createFolderNode(Graph parentGraph)
Description	Methods to create a folder node.

Both group nodes as well as folder nodes can also be created by converting normal nodes:

void convertToGroupNode(Node node)
Description	Converts a normal node to a group node.
void convertToFolderNode(Node node) void convertToFolderNode(Node node, Graph innerGraph)
Description	Methods to convert a normal node to a folder node.

The following getter methods can be used to query what kind a given node is:

boolean isGroupNode(Node node)
boolean isFolderNode(Node node)
boolean isNormalNode(Node node)

To add content to a group node or a folder node, the following methods can be used:

void setParentNode(Node node, Node parentNode) void setParentNode(NodeList nodeList, Node parentNode)
Description	Methods to set the parent node for a given (list of) node(s). The parent node may either be a group node or a folder node, or `null`, which denotes the root graph.

The contents can afterwards be queried using:

NodeCursor getChildren(Node node)
Description	Returns the grouped nodes when given a group node or the nodes in the inner graph when given a folder node.

Creating Grouped Nodes

Conceptually, grouped nodes are one level below their containing group node in the graph hierarchy. Technically, however, they are in the same graph as their enclosing group node.

Nodes can be grouped within a group node using the above setParent methods as well as the following method, which maintains the existing hierarchical structure of the given nodes. Example 7.2, “Grouping nodes” shows the creation of a group node and how to add content to it.

void groupSubgraph(NodeList subgraphNodeList, Node groupNode)
Description	Sets the given group node as the common ancestor of the nodes from the given subgraph structure.

Example 7.2. Grouping nodes

// 'hm' is of type y.view.hierarchy.HierarchyManager.

// Create a new node in the root graph that is a group node.
Node groupNode = hm.createGroupNode(rootGraph);

NodeList nl = new NodeList();
// Create some (normal) nodes in the root graph also.
for (int i = 0; i < 3; i++) {
  nl.add(rootGraph.createNode());
}

// Add them to the group node by setting it their parent node.
hm.setParentNode(nl, groupNode);

nl.clear();
// Create another node in the root graph.
nl.add(rootGraph.createNode());

// Add this single node to the group node also.
hm.groupSubgraph(nl, groupNode);

Creating Nested Graphs

Conceptually, a nested graph structure is contained within its folder node. In the graph hierarchy, it is one level below its folder node, and is accordingly called the inner graph of the folder node. Technically, however, a nested graph structure is a proper graph that is stored separately from its parent graph, i.e., the graph where the folder node resides in.

The folder node within the parent graph serves as an anchor for the nested graph structure. This is why a folder node is also called an anchor node sometimes.

Nodes can be nested within a folder node using the above setParent methods as well as the following method. Example 7.3, “Nesting nodes” shows the creation of a folder node and how to add content to it. Also, extracting a nested graph structure from a folder node is shown, too.

void foldSubgraph(NodeList subgraphNodeList, Node folderNode)
Description	Transfers the subgraph induced by the given nodes to the given folder node's inner graph. Also creates inter-edges from edges where only one end is in the inner graph after the transfer.

Example 7.3. Nesting nodes

// 'hm' is of type y.view.hierarchy.HierarchyManager. 

// Create a new node in the root graph that is a folder node.
Node folderNode = hm.createFolderNode(rootGraph);

NodeList nl = new NodeList();
// Create some (normal) nodes in the root graph also.
for (int i = 0; i < 3; i++) {
  nl.add(rootGraph.createNode());
}

// Add them to the folder node by setting it their parent node.
hm.setParentNode(nl, folderNode);

nl.clear();
// Create another node in the root graph.
nl.add(rootGraph.createNode());

// Add this single node to the folder node also.
hm.foldSubgraph(nl, folderNode);

// Move the node added last up one level back to the parent graph.
hm.unfoldSubGraph(hm.getInnerGraph(folderNode), nl);

Whenever the HierarchyManager is asked to populate a folder node, the involved nodes are removed from their original graph and created anew inside the folder node's inner graph.

Access to a folder node's inner graph is provided through:

Graph getInnerGraph(Node folderNode)
Description	Returns the inner graph of a folder node.

Handling Inter-edges

In a grouped graph that contains folder nodes, there can also occur edges that connect nodes from inner graphs to nodes from other graphs within the graph hierarchy. Generally, these edges have to be remodeled to connect nodes that are on the same hierarchy level, since an edge whose nodes are in different graphs is not legal.

Remodeling an edge to an inter-edge that represents its original is automatically done by the HierarchyManager. Both edge ends are promoted to the nearest common graph up in the hierarchy that contains all folder nodes of the involved inner graphs.

The HierarchyManager afterwards provides information on the "real" source and target of the inter-edge. The following methods return the real source and target of an inter-edge:

Node getRealSource(Edge interEdge)
Description	Returns the real source node associated with the given inter-edge.
Node getRealTarget(Edge interEdge)
Description	Returns the real target node associated with the given inter-edge.

Node Visiting Order

The HierarchyManager instance that has been added to a graph is also responsible for maintaining the node visiting order that is used, e.g., for drawing or for hit-testing the graph elements. The following methods provide a way to affect the node visiting order by changing the order of children of either group node or folder node:

void moveToFirst(Node childNode)
Description	Makes the given node the first child of its parent.
void moveToLast(Node childNode)
Description	Makes the given node the last child of its parent.

Important

The visiting order that is maintained by class HierarchyManager is not preserved when the grouped graph is saved to a file.

To preserve the visiting order between file export and import, all HierarchyManager operations that affect the node order have to be accompanied by corresponding Graph operations on the particular graph (root graph or nested graph). See Table 7.1, “Corresponding node order methods”.

Table 7.1. Corresponding node order methods

HierarchyManager	Graph
moveToFirst(Node)	moveToFirst(Node)
moveToLast(Node)	moveToLast(Node)

Traversal Policies

Class HierarchyManager offers two different node traversal orders which can be applied to a grouped graph:

Pre-traverse visits the parent before the children, and the children themselves from first to last.
Post-visit visits the children before the parent, and the children themselves from last to first.

Following are HierarchyManager's methods for both traversal policies:

void postTraverse(HierarchyManager.NodeVisitor visitor) void postTraverse(Node rootNode, HierarchyManager.NodeVisitor visitor)
Description	Node traversal used for drawing.
void preTraverse(HierarchyManager.NodeVisitor visitor) void preTraverse(Node rootNode, HierarchyManager.NodeVisitor visitor)
Description	Node traversal used for hit-testing.

Pre-traverse is used, e.g., for drawing the nodes of a grouped graph, since it makes sure that children are drawn atop their parents. Post-traverse on the other hand, is useful for hit-testing the graph elements, since elements atop of others should receive hit events first.

Class DefaultHierarchyGraphFactory

Class DefaultHierarchyGraphFactory is used by HierarchyManager to have new graph elements within the grouped graph created and properly configured. The graph factory handles creation of both normal graph elements as well as nested graph structures (i.e., the inner graph of a folder node). It also creates and configures the corresponding proxy nodes, i.e., group nodes and folder nodes.

Nested graph structures created by DefaultHierarchyGraphFactory are of type Graph2D, the realizer implementations taken for group nodes and folder nodes can be controlled using appropriate methods. By default, class GroupNodeRealizer is used for both group nodes and folder nodes, since it can render both presentations. See also the section called “Node Realizers”.

Figure 7.4. Class DefaultHierarchyGraphFactory

Whenever a new graph is created by this graph factory, it will inherit all listeners that are registered with its parent graph, i.e., all GraphListener, Graph2DListener, and Graph2DSelectionListener references are copied. In particular, this copies the GraphListener that is needed by HierarchyManager in order to keep its model of the hierarchic structure synchronized over to any inner graph that is created in conjunction with a folder node.

To control the creation of graph objects the instance of DefaultGraphFactory that is used can be replaced with a customized factory using the appropriate method of class HierarchyManager.

Tutorial Demo Code

HierarchyDemo.java is an extensive tutorial demo application that discusses all aspects of graph hierarchies and in particular shows how to work with class HierarchyManager. Further demos that present working with graph hierarchies include:

Where to Find Up-to-date yFiles Information