**Table of Contents**

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.

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)}.

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."

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.

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.

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.

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^{}.

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.

Copyright ©2004-2015, yWorks GmbH. All rights reserved. |