Graph Structure Functionality

The yFiles graph structure implementation as depicted in Figure 12.1, “The basic algorithms graph structure” shows the main classes together with their associations and multiplicity. A graph can have an arbitrary number of nodes and edges, every node and edge, though, has exactly one graph. A node can have an arbitrary number of edges, but an edge always has two nodes (its source node and its target node).

Figure 12.1. The basic algorithms graph structure

The basic algorithms graph structure in yFiles for Silverlight.

More About Class Graph

In addition to the functionality presented in the section called “Creating Graphs and Graph Elements”, which covers simple graph element creation, class Graph also provides methods that offer more control in specific situations.

For example, in addition to the most frequently used simple edge creation, it is also possible to specify the exact place where a newly created edge should be inserted into both the sequence of outgoing edges at its source node and the sequence of incoming edges at its target node. Furthermore, an already existing edge can be completely remodeled, i.e., both its end nodes as well as the insertion places at either end node can be changed. Reversing an edge, as another variant of changing an edge, is also supported.

Example 12.1, “Exact edge insertion” shows the respective line of code for specifying the exact place of edge insertion.

Example 12.1. Exact edge insertion

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.
// 'source' and 'target' are of type yWorks.yFiles.Algorithms.Node.

// Create a new edge at the second position of all incoming edges at the target 
// node. 
graph.CreateEdge(source, source.FirstOutEdge, target, target.FirstInEdge, 
                 GraphElementInsertion.After, GraphElementInsertion.After);

Figure 12.2, “Exact edge insertion” shows the resulting graph. The newly created edge is inserted after the first incoming edge at the target node. Observe how the sequence of incoming edges (indicated by the numbers near the arrowheads) changes with the insertion.

Figure 12.2. Exact edge insertion

Three incoming edges at target node.
Fourth incoming edge inserted at place two.
(a) Graph before... (b) ... and after edge insertion.

The analogous operation to graph element creation is their removal. Class Graph offers methods to remove all graph elements at once, or to remove only a single node or a single edge. When removing either an instance of type Node or an instance of type Edge their reference to the containing graph is cleared.

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.

// Remove single graph elements from the graph. 
// Note that all edges adjacent to the given node are removed prior to the node 
// itself.
graph.RemoveNode(graph.FirstNode);
graph.RemoveEdge(graph.LastEdge);

// Remove all graph elements from the graph at once.
graph.Clear();

Note

When removing a single node from a graph, all its connecting edges are also removed. Technically, they are even removed before the node is, since an edge requires both its source node and target node to reside in the same graph.

An alternative to removing graph elements is to hide them. Hiding is a technique to only temporarily remove graph elements, i.e., taking them away from the graph structure to perform some task on the remaining graph, and thereafter putting them back into again, unhiding them. Note that both removing and hiding a graph element only takes them away from the graph, the objects themselves still exist.

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.

// Hide single graph elements from the graph. 
// Note that all edges adjacent to 'exampleNode' are hidden prior to the node 
// itself.
Node exampleNode = graph.FirstNode;
graph.Hide(exampleNode);

// Unhide single graph elements from the graph. 
// Note that *only* 'exampleNode' is unhidden, while its formerly adjacent edges 
// are not. 
graph.Unhide(exampleNode);

In order to be able to unhide previously hidden graph elements, it is necessary to retain them, for example, in a data structure. Hiding of graph elements can also be performed utilizing specialized classes which automatically keep track of all hidden elements. These classes are described in the section called “Advanced Topics”.

Important

Hiding a graph element only differs from removing a graph element in that there is no graph event fired that signals the structural change. (Please see the section called “Events and Listeners” for a description of graph events.) As a consequence, any listeners to such graph events won't be notified when either node or edge is hidden, which can easily result in data structures getting out of sync with the actual structure of the graph.

In addition to the number of nodes and the number of edges an instance of type Graph also knows whether a single graph element belongs to it or if there is an edge connecting two nodes. The latter feature is especially useful if there is no reference of an edge at hand, for instance.

If a graph element has been hidden it does not belong to any graph until it is unhidden again.

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.

// Get the number of nodes in the graph.
// (Both methods are equivalent.)
int nodeCount = graph.NodeCount;
int N = graph.N;

// Get the number of edges in the graph.
// (Both methods are equivalent.)
int edgeCount = graph.EdgeCount;
int E = graph.E;

// Check if the graph is empty.
bool isEmpty = graph.Empty;

// Check if the first node belongs to the graph.
bool containsNode = graph.Contains(graph.FirstNode);

// Check if there is an edge between first and last node of the graph.
bool containsEdge = graph.ContainsEdge(graph.FirstNode, graph.LastNode);

Class Graph offers access to its graph elements in several different ways. It returns enumerators and cursors to iterate over the respective sets of graph elements, or creates arrays containing references to all nodes or all edges from the graph. As an additional convenience, there are properties to get the first, respectively last element of any of the two sets. While the returned cursors by definition have read-only behavior on the underlying container, the returned arrays actually are copies of the respective sets of elements from the graph at a certain point in time. In effect, this means that, for example, a returned node array can be modified in any way, i.e., nodes might be removed from the array or the sequence of nodes might be changed, without affecting the node set from the graph.

To change the sequence of any of the graph element sets class Graph has methods to move an element to the first or last position, respectively.

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.

// Get the first and last node of the node set from the graph.
Node firstNode = graph.FirstNode;
Node lastNode = graph.LastNode;

// Exchange first and last node of the node set.
graph.MoveToLast(firstNode);
graph.MoveToFirst(lastNode);

// Get the first and last edge of the edge set from the graph.
Edge firstEdge = graph.FirstEdge;
Edge lastEdge = graph.LastEdge;

// Exchange first and last edge of the edge set.
graph.MoveToLast(firstEdge);
graph.MoveToFirst(lastEdge);

// Get an enumerator of all nodes from the graph. 
IEnumerable<Node> ne = graph.Nodes;

// Get an enumerator of all edges from the graph. 
IEnumerable<Edge> ee = graph.Edges;

// Get a cursor of all nodes from the graph. 
INodeCursor nc = graph.GetNodeCursor();

// Get a cursor of all edges from the graph.
IEdgeCursor ec = graph.GetEdgeCursor();

// Get an array of all nodes from the graph. 
Node[] nodes = graph.GetNodeArray();

// Get an array of all edges from the graph.
Edge[] edges = graph.GetEdgeArray();

Graph Elements

Every instance of a graph element, i.e., every instance of type Node and type Edge holds a reference to the instance of type Graph it belongs to. This reference is cleared when the graph element has been removed or hidden from its graph.

// 'node' is of type yWorks.yFiles.Algorithms.Node.

// Get the graph the node belongs to.
Graph graph = node.Graph;

Furthermore, every graph element knows the position it has in the respective set of elements within its graph. More precisely, when an instance of type Graph is asked for an array of its nodes, for example, this array reflects the node iteration sequence exactly, i.e., a node at position 6 in the array will return the value 6 when asked for its position.

Important

The position of a removed graph element is undefined. The same holds for a hidden graph element.

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.
// 'node' is of type yWorks.yFiles.Algorithms.Node.

// Get the node's position.
int index = node.Index;

// Get an array of all nodes from the graph.
Node[] nodes = graph.GetNodeArray();
// Check the positions of all nodes.
for (int i = 0; i < graph.N; i++) {
  if (nodes[i].Index != i) {
    throw new System.ApplicationException("Mismatch at position " + i + ".");
  }
  else {
    Console.WriteLine("All is well at position " + i + ".");
  }
}

Class Node

Class Node is responsible for everything that is related to its connecting edges. More specifically, an instance of type Node knows the overall number of connecting edges (the so-called degree of the node) as well as the division into the number of incoming edges (in-degree) and the number outgoing edges (out-degree).

// 'node' is of type yWorks.yFiles.Algorithms.Node.

// Get the number of edges at a node.
int degree = node.Degree;

// Get the number of incoming edges at a node.
int inDegree = node.InDegree;

// Get the number of outgoing edges at a node.
int outDegree = node.OutDegree;

A node also provides methods to easily test whether there is a connecting edge to another node.

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.

Node firstNode = graph.FirstNode;
Node lastNode = graph.LastNode;

// Check whether there is an edge between first and last node of the graph. 
// First check if there is a connecting edge outgoing to 'lastNode'.
Edge e = firstNode.GetEdgeTo(lastNode);
// If not, then check if there is a connecting edge incoming from 'lastNode'.
if (e == null) {
  e = firstNode.GetEdgeFrom(lastNode);
}

Furthermore, it can give enumerators and cursors to iterate over all connecting edges, iterate over all incoming edges, and iterate over all outgoing edges. When iterating over all edges incoming edges appear first, outgoing edges last.


// 'node' is of type yWorks.yFiles.Algorithms.Node.

// Get an enumerator to iterate over all edges at a node.
IEnumerable<Edge> edges = node.Edges;

// Get an enumerator to iterate over all incoming edges at a node.
IEnumerable<Edge> inEdges = node.InEdges;

// Get an enumerator to iterate over all outgoing edges at a node.
IEnumerable<Edge> outEdges = node.OutEdges;

// Get a cursor to iterate over all edges at a node.
IEdgeCursor edgeCursor = node.GetEdgeCursor();

// Get a cursor to iterate over all incoming edges at a node.
IEdgeCursor inEdgeCursor = node.GetInEdgeCursor();

// Get a cursor to iterate over all outgoing edges at a node.
IEdgeCursor outEdgeCursor = node.GetOutEdgeCursor();

Important

Since a self-loop is both an incoming and an outgoing edge at its node, it appears twice when iterating over all edges of the node. Also, a self-loop counts twice when asking for the degree of a node.

As a convenience, class Node furthermore provides enumerators and cursors to iterate over all its neighbors, to iterate over all its predecessors, or to iterate over all its successors. Predecessors and successors mean the nodes at the opposite of an incoming edge, and an outgoing edge, respectively.

// 'node' is of type yWorks.yFiles.Algorithms.Node.

// Get an enumerator to iterate over all neighbor nodes.
IEnumerable<Node> neighbors = node.Neighbors;

// Get an enumerator to iterate over the source nodes of all incoming edges.
// These nodes are called predecessors.
IEnumerable<Node> predecessors = node.Predecessors;

// Get an enumerator to iterate over the target nodes of all outgoing edges.
// These nodes are called successors.
IEnumerable<Node> successors = node.Successors;

// Get a cursor to iterate over all neighbor nodes.
INodeCursor neighborCursor = node.GetNeighborCursor();

// Get a cursor to iterate over the source nodes of all incoming edges.
// These nodes are called predecessors.
INodeCursor predecessorCursor = node.GetPredecessorCursor();

// Get a cursor to iterate over the target nodes of all outgoing edges.
// These nodes are called successors.
INodeCursor successorCursor = node.GetSuccessorCursor();

Class Edge

The most important information an instance of type Edge provides is its source node and its target node. Closely related is the method to get the opposite when holding one of the edge's end nodes.

// 'edge' is of type yWorks.yFiles.Algorithms.Edge.

// Get the two end nodes of an edge.
Node source = edge.Source;
Node target = edge.Target;

// Getting the opposite when holding one of either source or target node.
Node opposite = edge.Opposite(source);

Note

Although a hidden edge holds no reference to a graph, it can still provide access to its source and target node, independent of their status.

As a convenience, class Edge additionally offers information whether it is a self-loop.

// 'edge' is of type yWorks.yFiles.Algorithms.Edge.

// Ask the edge whether it is a self-loop.
bool isSelfLoop = edge.SelfLoop;

Note

Ignoring the directedness of the yFiles algorithms graph structure implementation and instead interpreting it undirected would be done using the Neighbors property, respectively method GetNeighborCursor of class Node, or a combination of property Edges, respectively method GetEdgeCursor of class Node and method Opposite of class Edge.

Complexity

Table 12.1, “Time complexities” shows time complexities for several of the most frequent tasks when working with the yFiles graph structure implementation.

Creation of graph elements takes constant time as does the removal of an edge. Removing a node, though, implies the removal of all its connecting edges first, so this task takes linear time, i.e., time proportional to the number of connecting edges. Also, all iteration is done in linear time. Checking whether a given node or edge belong to a graph is done in constant time, while testing if there is an edge connecting two nodes takes linear time.

Table 12.1. Time complexities

Task Involved Type(s) Complexity
Creating a node Graph O(1)
Creating an edge Graph O(1)
Removing/hiding a node Graph O(Node.Degree)
Removing/hiding an edge Graph O(1)
Clearing the graph Graph O(Graph.N + Graph.E)
Iterating over the node set Graph, INodeCursor/IEnumerator O(Graph.N)
Iterating over the edge set Graph, IEdgeCursor/IEnumerator O(Graph.E)
Iterating over all edges connecting to a node Node, IEdgeCursor/IEnumerator O(Node.Degree)
Iterating over all incoming edges Node, IEdgeCursor/IEnumerator O(Node.InDegree)
Iterating over all outgoing edges Node, IEdgeCursor/IEnumerator O(Node.OutDegree)
Checking if a node belongs to a graph Graph O(1)
Checking if an edge belongs to a graph Graph O(1)
Checking if there is an edge connecting two nodes Graph O(min(source.OutDegree, target.InDegree))

Advanced Topics

Hiding Graph Elements

Support for hiding graph elements is further completed by classes GraphHider and GraphPartitionManager from the yWorks.yFiles.Algorithms.Util namespace. In addition to the methods from class Graph, GraphHider offers various methods to hide arbitrary collections of graph elements or even all elements from the graph at once. Moreover, it automatically keeps track of all elements hidden as a result of such method calls.

To unhide graph elements, class GraphHider provides a small set of methods that collectively employ all-at-once behavior when unhiding, i.e., all elements previously hidden are unhidden at once.

Class GraphPartitionManager extends the idea from class GraphHider in a way so that it is possible to mark parts of the graph as so-called "partitions" and hide/unhide these. Example 9.4, “Making a graph connected” is a rather extensive code snippet where an instance of GraphPartitionManager is used to hide/unhide connected components.

Important

When working with graph hierarchies graph elements must not be hidden, but instead should be removed.

Copying a Graph

Class GraphCopier provides convenient support for copying a Graph object. It enables the complete range from copying the entire Graph to copying only sets of graph elements. Optionally, any data associated to either nodes or edges by means of data accessors, i.e., data providers or node maps and edge maps, respectively, can also be copied.

GraphCopier relies on implementations of nested interface ICopyFactory to delegate the actual work of copying nodes and edges from one graph to another to. A simple default implementation for a copy factory that is capable of handling a Graph object is provided by class GraphCopyFactory. Initially, i.e., when no other copy factory has been set, class Graph returns a similar implementation when its GraphCopyFactory property is invoked.

Example 12.2. Creating a GraphCopier

// 'graph' is of type yWorks.yFiles.Algorithms.Graph.

// Create a new GraphCopier.
GraphCopier gc = new GraphCopier();

The following methods from class GraphCopier can be used to copy either an entire Graph object or the subgraph that is induced by a given set of nodes from a given source graph:

By default, copying a Graph object or a set of nodes does not include any data associated with either the nodes or edges. The following properties can be used to control whether the contents of data accessors, i.e., both data providers and node maps and edge maps, respectively, that are registered with the source graph are copied over to the target graph, too.

bool DataProviderContentCopying { get; set; }
Description Controls whether to copy data provider contents.
bool NodeMapCopying { get; set; }
bool EdgeMapCopying { get; set; }
Description Determines whether to copy the contents of node maps and edge maps registered with the source graph.

Data accessors are presented in the section called “Binding Data to Graph Elements”.