Chapter 11. Underlying Graph Model of the yFiles Graph Analysis Algorithms

Table of Contents

Basic Algorithms Graph Structure
Clear Responsibilities
Accessing Graph Elements
Storing Elements
Binding Data to Graph Elements
A Word on Subclassing Graph Elements

This chapter introduces the general concepts of the yFiles software library. These include purpose-specific, i.e., graph structure related topics as well as practical programming aspects.

Basic Algorithms Graph Structure

All yFiles functionality centers around the mathematical notion of a directed graph. A directed graph is defined as consisting of two sets, a node set and an edge set. A node represents any kind of entity and an edge represents a relation between any two nodes from the node set. Directed graph means that all edges from the edge set have direction, i.e., a distinct source node and a distinct target node. The mathematical notation for an edge is a pair where the first component denotes source and the second component denotes target node: edge e = (source, target).

This directed graph structure is reflected by the classes Graph, Node, and Edge in the yWorks.yFiles.Algorithms namespace. Together, these classes form the foundation for all graph functionality.

Figure 11.1, “A simple graph” shows the picture of an example graph with six nodes and seven edges where the nodes are represented by filled circles and the edges are drawn as straight lines between two nodes with an arrowhead at the target end indicating direction. The exact mathematical notation of this example graph would be: Graph G = (V,E), with node set V = {Y,W,O,R,K,S} and edge set E = {(Y,W), (W,O), (W,R), (W,K), (W,S), (R,K), (K,S)}.

Figure 11.1. A simple graph

A simple graph.

Some interesting aspects of the graph structure implementation should be observed. For example, there is no requirement that source and target node of a directed edge have to be different. When they are identical, the special kind of edge is also called "self-loop." (A self-loop at the node with label "Y", for example, would be written as (Y,Y).)

On another note, there is also no restriction on the number of edges connecting the same two nodes from a graph. This means that the yFiles graph structure in fact provides not only a set but a multi-set to store the edges of a graph. We will call such edge sets "parallel edges."

Another consequence with a directed graph is that edges connecting to a node can be distinguished into incoming edges and outgoing edges. Incoming edges are those that have the node as target, while outgoing edges are those that have the node as source. The set of all edges at a node is simply called its "edges." Figure 11.1, “A simple graph”, for example, shows four outgoing edges and one incoming edge for the node labeled "W."

Note

Despite the strong emphasis on the directedness of the graph structure it is nevertheless possible to mimic undirected behavior easily. Both the graph structure itself and many algorithms (where appropriate) offer methods to ignore edge direction entirely. (Effectively, this means that directedness/undirectedness ultimately is a matter of interpretation on the algorithm's side.)

Figure 11.2, “Various configurations” shows some graph excerpts that depict (from left to right) a directed edge and a self-loop, several self-loops at one node, and a set of parallel edges.

Figure 11.2. Various configurations

Various configurations.

Important

Keep in mind that the presented figures are only a guidance to demonstrate the various possibilities provided by yFiles. The yFiles algorithms graph structure has neither positional information nor any visual representation associated with the graph elements.

Clear Responsibilities

The yFiles graph structure implementation adheres to the idea that the graph should be the only instance in charge of all structural changes. (Structural changes most notably means node and edge creation and removal.) This paradigm has some important implications:

  • There must exist a valid instance of type Graph to create any graph elements ("inside" this graph instance) at all.
  • There is no way to create a node or an edge "outside" a graph.
  • All created graph elements instantly belong to a distinct graph.

Additionally, there is a clear cascade of responsibilities for providing access to certain graph element information:

  • A graph provides access to its nodes and edges.
  • A node provides access to its edges; this can be all edges, or all incoming and outgoing edges, respectively.
  • An edge provides access to its source and target node.

Accessing Graph Elements

A graph provides access to its nodes and edges by means of enumerators and bidirectional cursors. Similar to enumerators, a cursor is a general concept to iterate over a sequence of objects one after the other. Bidirectional means that it is possible to both move forward and backward on the sequence.

The actual methods from class Graph return either an IEnumerable<Node>, IEnumerable<Edge>, INodeCursor or an IEdgeCursor instance to be used for iterating over the respective elements. Both INodeCursor and IEdgeCursor present a read-only view on the actual graph elements. That way it is guaranteed that class Graph remains the single authority for any structural changes.

On a side note, observe that INodeCursor and IEdgeCursor are typed variants of their common superinterface ICursor.

Storing Elements

The yFiles library defines a base implementation of a doubly linked list, class YList. Most notably however, are the typed descendants of YList, classes NodeList and EdgeList. The latter two are used for the respective kinds of graph elements while their common superclass stores objects of arbitrary type. NodeList and EdgeList are frequently used as return types or as parameters in several methods throughout the yFiles library.