Graph Structure

The graph model found in the yWorks.yFiles.UI.Model namespace centers around interface IGraph. It serves as a visually rich representation of the mathematical notion of a directed graph and provides geometry as well as rendering support for the items it contains.

What is a 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.

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

The yFiles for Silverlight graph model adds further elements to this concept: so-called ports serve as linking elements between nodes and edges and can also be used to link edges to other edges. So-called bends, which are part of an edge, present a means to define a geometry for edges. Also, label elements can be used with nodes and edges and add to their visual appearance.

Nodes and edges of a graph are modeled by interfaces INode and IEdge. The ports that link nodes and edges (or edges to other edges) are defined by interface IPort, the bends that an edge can contain are defined by interface IBend. Finally, interface ILabel defines generic labels for both nodes and edges.

Figure 4.2, “Graph structure” depicts the central graph structure types in yFiles for Silverlight Viewer. Through a set of convenient properties, IGraph makes available collection views of the model items it contains. For example, the Nodes and Edges properties can be used to obtain a view of all nodes and all edges, respectively.

Figure 4.2. Graph structure

Graph structure.

The types surrounding IGraph consistently provide read-only views of their data, and to change a graph element's properties, methods defined in IGraph need to be used. In other words, IGraph holds responsibility for all changes to the graph model, be it of structural nature, changes of geometry, or regarding the visual appearance of graph elements.

Figure 4.3, “Type hierarchy of model items” shows the type hierarchy of the model items in a yFiles for Silverlight graph model.

Figure 4.3. Type hierarchy of model items

Type hierarchy of model items.

All graph structure interfaces either directly or indirectly have interface ILookup as their base type. Consequently, the powerful look-up mechanism as discussed in the section called “Look-up Mechanism” can be used to query dynamic sets of associated types that handle specific aspects of even single instances of such interface implementations.

The look-up support provided by class DefaultGraph, the default IGraph implementation, for example, is presented in the section called “Look-up Support”. The type requests that are handled by the model item types are listed in the section called “Look-up Support”. In the section called “Customizing User Interaction Behavior”, the look-up support provided by the model item types is discussed in the context of user interaction behavior and its customization.

Similarly, since IModelItem inherits from interface ITagOwner, all graph structure interfaces provide support for convenient tagging of model items with arbitrary objects. The tagging mechanism is discussed in the section called “User Tags”.

Figure 4.4, “Relationships between graph structure types” depicts the interrelations of graph structure elements. Nodes and edges connect to each other using ports, which logically belong to the nodes (i.e., the owner of an IPort is an INode). Edges, more precisely their paths, are defined by the ports at their ends and a sequence of zero or more bends in-between these (where each of the IBend will indicate the IEdge as its owner).

Figure 4.4. Relationships between graph structure types

Relationships between graph structure types.

The INode, IEdge, IPort, and IBend interfaces allow to obtain a graph element's geometry as well as the style object that manages visual appearance. While node geometry can be obtained directly from INode, edge geometry is available via an edge's IPort and IBend objects.

In addition to the immediate graph structure elements, there is also support for an arbitrary number of labels at both nodes and edges. The actual INode or IEdge a label belongs to, is indicated as the ILabel's owner. Figure 4.5, “ILabeledItem and ILabel” presents ILabel's relationship to other model items.

Figure 4.5. ILabeledItem and ILabel

ILabeledItem and ILabel.

Besides geometry and style, interface ILabel also grants access to label-specific data like the label's text. Label geometry is special since a label can be rotated and since its actual location is calculated by a so-called label model, which uses a label model parameter that is associated with the label. Label models and also the creation of valid label model parameters is explained in the section called “Label Support”.

Interface IGraph defines fundamental graph structure-related functionality including creation and deletion of graph elements, or querying of structural aspects, like, e.g., adjacency lists. Provided is also support for modifying the geometry of graph elements, i.e., their location and size, and for modifications to the visual appearance of model items.

Listed below are IGraph methods that deal with the creation of graph elements and modification of the graph structure.

Note

IGraph itself defines only a basic set of core functionality methods directly. Via the .NET extension methods mechanism, however, further overloads and methods that add convenience functionality are additionally available. Extension methods for interface IGraph specifically are provided by class GraphExtensions.

INode CreateNode()
INode CreateNode(RectD bounds, INodeStyle style, object tag)
Description Node creation (extension) methods (excerpt).
IEdge CreateEdge(INode source, INode target)
IEdge CreateEdge(INode source, INode target, IEdgeStyle style, object tag)
IEdge CreateEdge(IPort sourcePort, IPort targetPort, IEdgeStyle style,
                 object tag)
Description Edge creation (extension) methods (excerpt).
IPort AddPort(IPortOwner portOwner, PointD location)
IPort AddPort(IPortOwner portOwner,
              IPortLocationModelParameter locationModelParameter,
              IPortStyle style, object tag)
Description Methods to create ports at nodes (excerpt). (Note that an INode is also an IPortOwner.)
IBend AddBend(IEdge edge, int index, PointD location)
Description Method to create a bend in an edge.
ILabel AddLabel(ILabeledItem item, string text)
ILabel AddLabel(ILabeledItem item, ILabelModelParameter labelModelParameter,
                ILabelStyle style, string text, SizeD preferredSize, object tag)
Description Methods to create a label with a graph element that can have labels (excerpt). (Note that an INode or an IEdge is also an ILabeledItem.)
void SetPorts(IEdge edge, IPort sourcePort, IPort targetPort)
Description Edge modification.

The following methods handle the deletion of graph elements:

void Clear()
void ClearBends(IEdge edge)
Description Methods to delete multiple graph elements.
void Remove(INode node)
Description Appropriate overloads delete a single edge, port, bend, or label.

IGraph methods that allow to query structural aspects of a graph, for example, the set of edges adjacent at a given node:

bool Contains(IModelItem item)

IListEnumerable<IEdge> EdgesAt(IPort port)
Description Methods for querying structural aspects of a graph.

The geometry of graph elements can be altered by means of the following methods. They allow to directly change the sizes of nodes and labels, and the locations of nodes, ports, and bends.

void SetBounds(INode node, RectD bounds)
void SetCenter(INode node, PointD center)
void SetLocation(IBend bend, PointD location)
void SetLocation(IPort port, PointD location)
void SetRelativeLocation(IPort port, PointD relativeLocation)
void SetPreferredSize(ILabel label, SizeD preferredSize)

Note that IGraph provides convenient support for default settings for graph elements. These are automatically used when no explicit values are specified, for example for the size of a node. Default node settings and default edge settings are available through the NodeDefaults and EdgeDefaults properties.

Modifying the visual appearance of model items is supported by the IGraph methods listed below. They can be used to conveniently handle styles, which are responsible for providing the visual presentation of graph elements (see also the section called “Visual Representation of Graph Elements”).

void SetStyle(INode node, INodeStyle style)
Description Appropriate overloads set the style for an edge, a label, or a port.

Note that through the default settings mechanism for graph elements, IGraph also provides the necessary support for a default style that it automatically binds to newly created graph elements. The default style is accessible via the Style property that is available with both the NodeDefaults and EdgeDefaults of IGraph.

To trigger redraw operations in views that display an IGraph, the following method can be used:

void InvalidateDisplays()

Look-up Support

All graph structure types support the look-up mechanism through their Lookup method or equivalent means. Table 4.1, “Supported type requests with look-up operations” lists the various type requests that can be initiated on the model items.

Table 4.1. Supported type requests with look-up operations

Model Item Type Requested Type Description
all model items IMementoSupport The returned IMementoSupport implementation can be used to create IUndoUnit objects.
IClipboardHelper The returned IClipboardHelper implementation allows to augment clipboard-related actions like Cut, Copy, and Paste.
IHandleProvider Holds a collection of IHandle implementations.
IPositionHandler and ISelectionInstaller See the section called “Customizing User Interaction Behavior”.
IMarqueeTestable The returned IMarqueeTestable implementation can be used to test whether a model item is inside a given marquee rectangle.
IFocusIndicatorInstaller and IHighlightInstaller The returned IFocusIndicatorInstaller/IHighlightInstaller implementation can be used to install visual decorations for a model item in the canvas that serve as a highlight/focus indication. See also the section called “Customizing User Interaction Behavior”.
INode IReshapeHandleProvider and IPortCandidateProvider See the section called “Customizing User Interaction Behavior”.
IGroupBoundsCalculator, IInsetsProvider<T>, and ISizeConstraintProvider<T> Implementations for these interfaces are in the look-up for non-leaf nodes in a grouped graph.
IShapeGeometry The returned IShapeGeometry implementation describes the geometry of the node's shape.
ISnapLineProvider, INodeSnapResultProvider, and INodeReshapeSnapResultProvider Implementations for these interfaces define the snapping behavior of a node. See also the section called “Customizing User Interaction Behavior”.
IEdge IEdgePortHandleProvider and IEdgePortCandidateProvider See the section called “Customizing User Interaction Behavior”.
IBendCreator The returned IBendCreator implementation helps in creating new bends in an IEdge.
IBendSelectionTester Helps in getting the IBend objects at specified coordinates in the canvas.
IPathGeometry The returned IPathGeometry implementation describes the geometry of the edge's path.
ISnapLineProvider and IEdgeSnapResultProvider Implementations for these interfaces define the snapping behavior of an edge. See also the section called “Customizing User Interaction Behavior”.
IOrthogonalEdgeHelper Defines orthogonal edge editing behavior of an IEdge. See also the section called “Customizing User Interaction Behavior”.
IPortCandidateProvider Provides port candidates along the edge path for other edges to connect to. See also the section called “Customizing User Interaction Behavior”.
IPort IHandle The returned IHandle implementation represents the UI element that is displayed in the canvas for moving the IPort.
IEdgeIntersectionCalculator Enables calculating the visible portion of an IEdge's path.
ISnapLineProvider and IPortSnapResultProvider Implementations for these interfaces define the snapping behavior of a port. See also the section called “Customizing User Interaction Behavior”.
IBend IHandle The returned IHandle implementation represents the UI element that is displayed in the canvas for moving the IBend.
IBendSnapResultProvider Enables selection of "matching" snap lines from the set of collected possible snap lines. See also the section called “Customizing User Interaction Behavior”.
ILabel ILabelModelParameterProvider Provides possible label candidates for an ILabel according to the label's model.
ILabelModelParameterFinder Enables finding the best matching label model parameter for an ILabel's position according to the label's model.

Through the GraphDecorator class specialized decorators for the graph element types are available. These decorators provide convenient access to the most common decorations for an actual graph element type (which largely match the table's content). The following IGraph method can be used to retrieve the GraphDecorator for a graph:

public GraphDecorator GetDecorator()
Description Getter (extension) method for the GraphDecorator of a graph.

Note that the main purpose of the available decorations is to enable customization of specific aspects of a graph element's look and feel as described in the section called “Look-up Support”, but with respect to quickly seeing what is "in the look-up" of a given graph element, the decorators are also useful.

Working with the Graph Structure

Class DefaultGraph is the default IGraph (see above) implementation used in yFiles for Silverlight. It holds the central graph structure that is displayed by the canvas, i.e., class GraphControl.

DefaultGraph fully supports the notion of default settings for graph elements as laid out in interface IGraph. Most notably, this also covers default styles for nodes and edges.

Default styles can be associated with a model item either by reference or as a cloned copy. The actual behavior can be specified using the ShareStyleInstance property of interfaces INodeDefaults and IEdgeDefaults, respectively.

Note

Initially, classes ShapeNodeStyle and PolylineEdgeStyle are used as the styles for the node defaults and edge defaults in class DefaultGraph, respectively. Similarly, SimpleLabelStyle is used as the node label and edge label style for both node defaults and edge defaults.

Node styles and edge styles are described in the section called “Visual Representation of Graph Elements”.

Look-up Support

Class DefaultGraph supports the look-up mechanism as described in the section called “Look-up Mechanism” by means of a look-up chain (see the section called “Look-up Chaining”) that it is maintaining. The look-up chain can be easily customized using the following methods:

void AddLookup(IContextLookupChainLink lookup)
void RemoveLookup(IContextLookupChainLink lookup)
Description Methods for modifying the look-up chain of class DefaultGraph.

Additionally, DefaultGraph also directly maintains look-up chains for the graph element types, i.e., for nodes, edges, labels, etc. These look-up chains can be customized by means of implementations of interface ILookupDecorator as described below.

Table 4.2, “Supported type requests with look-up operations” presents a sample of types that are supported with look-up operations initiated on a DefaultGraph instance. Further types that are supported when grouping support is enabled are listed in the section called “Look-up Modifications”.

Table 4.2. Supported type requests with look-up operations

Requested Type Description
ILookupDecorator The returned ILookupDecorator enables convenient manipulation of look-up chains maintained for the graph elements of the queried DefaultGraph, i.e., for all its nodes, edges, labels, etc. As a convenience, manipulation of the graph's own look-up chain is also supported. (See below for a description on using ILookupDecorator.)

Note that through the GraphDecorator class further ILookupDecorator implementations are made available that enable direct customization of specific types in the look-up chain of a graph element type.

IUndoSupport The returned IUndoSupport implementation allows to indicate to the undo engine any pending modifications to items in the canvas.
INodeBoundsChangeReporter The returned INodeBoundsChangeReporter implementation allows to register an event listener that signals changes in the layout of INode model items.

The ILookupDecorator that is returned when querying DefaultGraph's look-up for this type makes available further look-up chains for decoration. These look-up facilities are maintained for the model items in the DefaultGraph, i.e., specifically look-up operations initiated on the following types can be decorated: INode, IEdge, IPort, IBend, and ILabel. Example 4.1, “Modifying the look-up chain for the nodes of a DefaultGraph” shows the typical pattern that is used to modify the look-up chain for the items of a DefaultGraph.

Example 4.1. Modifying the look-up chain for the nodes of a DefaultGraph

void PrependMyCustomLookupBehavior(IGraph graph) {
  // Get the graph's ILookupDecorator that enables manipulation of all look-up 
  // operations for the contained graph elements.
  ILookupDecorator decorator = graph.Get<ILookupDecorator>();
  if (decorator != null) {
    // Test whether decoration of look-up operations initiated on type INode is 
    // supported.
    if (decorator.CanDecorate(typeof (INode))) {
      // Prepend a custom look-up provider.
      decorator.AddLookup(typeof (INode), new MyCustomReshapeableChainLink());
    }
  }
}

The look-up chains for model items can also be customized directly using the respective decorators that are made available by class GraphDecorator. These decorators provide support for modifying specific types in a look-chain. Example 4.2, “Type-specific modification of the look-up chain for nodes using NodeDecorator” shows code equivalent to the example above using the NodeDecorator class to decorate the look-up chain for nodes.

Example 4.2. Type-specific modification of the look-up chain for nodes using NodeDecorator

void PrependMyCustomLookupBehavior(IGraph graph) {
  // Get the NodeDecorator for the nodes of the given graph. NodeDecorator
  // enables type-specific manipulation of the look-up operations.
  NodeDecorator decorator = graph.GetDecorator().NodeDecorator;
  // Prepend a custom look-up provider to decorate look-up operations initiated
  // on type INode.
  decorator.ReshapeHandleProviderDecorator.AddChainLink(
      new MyCustomReshapeableChainLink());
}

The tutorial demo applications that present user interaction customization, like, e.g., PositionHandlerWindow, show how interactive behavior of model items in a DefaultGraph can be customized using the services of ILookupDecorator.

Working with DefaultGraph

Example 4.3, “Creating a graph” shows how to create a graph and how to populate it with newly created graph elements. The example also demonstrates how to add labels to both nodes and edges.

Example 4.3. Creating a graph

IGraph graph = new DefaultGraph();

// Create 10 nodes. 
INode[] nodes = new INode[10];
for (int i = 0; i < nodes.Length; i++) {
  nodes[i] = graph.CreateNode();
  graph.AddLabel(nodes[i], "Node #" + i.ToString());
}

// Create 5 edges. Each edge has "even" source node and "odd" target node. 
IEdge[] edges = new IEdge[5];
for (int i = 0, j = 0; i < nodes.Length - 1; i += 2, j++) {
  edges[j] = graph.CreateEdge(nodes[i], nodes[i + 1]);
  graph.AddLabel(edges[j], "Edge #" + j.ToString());
}

Connecting edges to the ports of some nodes and also adding bends to edges is presented in Example 4.4, “Creating a graph”.

Example 4.4. Creating a graph

IGraph graph = new DefaultGraph();
// Node style configuration.
INodeDefaults nodeDefault = graph.NodeDefaults;
nodeDefault.Style = new ShapeNodeStyle();
((ShapeNodeStyle)nodeDefault.Style).Shape = ShapeNodeShape.RoundRectangle;
nodeDefault.Size = new SizeD(80, 40);

// Create two nodes.
INode fst = graph.CreateNode(new PointD(100, 200)), 
      snd = graph.CreateNode(new PointD(300, 200));
// Add a port to each node.
IPort fstSouth = graph.AddPort(fst, new PointD(120, 220)), 
      sndNorth = graph.AddPort(snd, new PointD(280, 180));

// Create two edges connecting the ports.
IEdge back = graph.CreateEdge(sndNorth, fstSouth), 
      forth = graph.CreateEdge(fstSouth, sndNorth);
// Add some bends to each edge.
graph.AppendBend(back, new PointD(240, 100));
graph.AppendBend(back, new PointD(160, 300));

graph.AppendBend(forth, new PointD(120, 300));
graph.AppendBend(forth, new PointD(200, 300));
graph.AppendBend(forth, new PointD(200, 100));
graph.AppendBend(forth, new PointD(280, 100));

Iterating over the elements of a graph is supported in a number of ways. Example 4.5, “Iterating over graph elements”, for example, presents iteration over the nodes of a graph and iteration over the edges adjacent at a node.

Example 4.5. Iterating over graph elements

// 'graph' is of type yWorks.yFiles.UI.Model.IGraph.

// Iterate over all nodes in the graph.
foreach (INode node in graph.Nodes) {
  if (!FulfillsSomeCondition(node)) {
    continue;
  }
  
  // Iterate over all outgoing edges at nodes that fulfill some condition.
  // (Technically, the edges are adjacent to an IPortOwner.)
  foreach (IEdge edge in graph.OutEdgesAt(node)) {
    DoSomethingWithThisEdge(edge);
  }
}

Getting all edges that connect to some ports from a given set of nodes is shown in Example 4.6, “Iterating over graph elements (cont.)”.

Example 4.6. Iterating over graph elements (cont.)

// 'graph' is of type yWorks.yFiles.UI.Model.IGraph.

foreach (INode node in myNodeList) {
  foreach (IPort port in node.Ports) {
    if (!FulfillsSomeCondition(port)) {
      continue;
    }
    
    // Iterate over all adjacent edges at ports that fulfill some condition.
    foreach (IEdge edge in graph.EdgesAt(port)) {
      DoSomethingWithThisEdge(edge);
    }
  }
}

Example 4.7, “Iterating over graph elements (cont.)” shows iteration over all bends of a set of edges.

Example 4.7. Iterating over graph elements (cont.)

foreach (IEdge edge in myEdgeList) {
  // Iterate over all bends of the current edge.
  foreach (IBend bend in edge.Bends) {
    IPoint bl = bend.Location;
    Console.WriteLine("bend location: X=" + bl.X + " Y=" + bl.Y);
  }
}

The code snippet in Example 4.8, “Iterating over graph elements (cont.)” iterates over all node labels in the graph and prints out their content.

Example 4.8. Iterating over graph elements (cont.)

// 'graph' is of type yWorks.yFiles.UI.Model.IGraph.

// Iterating over all node labels from the graph.
foreach (ILabel nodeLabel in graph.NodeLabels) {
  Console.WriteLine(nodeLabel.Owner.ToString() + ": '" + 
                         nodeLabel.Text + "'");
}

Example 4.9, “Getting an edge's source and target node” shows how to get the source and target node of an edge.

Example 4.9. Getting an edge's source and target node

// Get the source node of an edge.
INode sourceNode = edge.GetSourceNode();
// Get the target node of an edge.
INode targetNode = edge.GetTargetNode();

Example 4.10, “Getting a node's neighbors” shows how to get a node's predecessor and successor nodes, i.e., the nodes at the other end of incoming and outgoing edges, respectively.

Example 4.10. Getting a node's neighbors

// Get the predecessors of a node.
foreach (INode predecessor in graph.Predecessors<INode>(node)) {
  // Do something with 'predecessor'...
}

// Get the successors of a node.
foreach (INode successor in graph.Successors<INode>(node)) {
  // Do something with 'successor'...
}

Example 4.11, “Getting a node's in degree and out degree” shows how to get the number of incoming and outgoing edges at a node, i.e., the node's in degree and out degree, respectively.

Example 4.11. Getting a node's in degree and out degree

// Determine the in degree of a node.
graph.InDegree(node);
// Determine the out degree of a node.
graph.OutDegree(node);