Chapter 9. Graph Analysis

Table of Contents

Using yFiles Graph Analysis Functionality
Analysis Algorithms
Quickly Checking for Graph Characteristics
Binding Data to Graph Elements
Breadth-First Search
Depth-First Search
Graph Connectivity
Shortest Paths
Centrality Measures
Spanning Trees
Transitivity
Trees

This chapter presents the graph analysis algorithms provided by the yFiles for Silverlight library and explains how to use them.

Using yFiles Graph Analysis Functionality

Internally, the analysis algorithms are tailored to the basic algorithms graph structure. By means of the adapter mechanisms presented in Chapter 8, Using yFiles for Silverlight Algorithms Functionality, however, the analysis algorithms can be used with an IGraph-based graph structure as well.

Adapter class YGraphAdapter provides services for necessary conversions prior and subsequent to running an analysis algorithm. Most notably, it creates a copy of an IGraph that can be used with such algorithms:

Example 9.1. Basic preparation for calling an analysis algorithm

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

// Create the graph model adapter to get a proper analysis graph structure.
YGraphAdapter graphAdapter = new YGraphAdapter(graph);

// The YGraph property returns the yWorks.yFiles.Algorithms.Graph instance that
// corresponds to the given IGraph above.
bool isConnected = GraphChecker.IsConnected(graphAdapter.YGraph);

The following detailed example shows the invocation of an analysis algorithm with additional intermittent conversions and updates to the original IGraph.

Example 9.2. Graph analysis with an IGraph-based graph using adapter mechanisms

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

// Create the graph model adapter to get a proper analysis graph structure.
YGraphAdapter graphAdapter = new YGraphAdapter(graph);

// Test if the graph is a tree.
if (Trees.IsTree(graphAdapter.YGraph)) {
  // Explicitly set the first node from the node set as the root node of the
  // tree.
  // Direct the tree; i.e., revert those edges that point towards the root
  // node.
  EdgeList el = Trees.DirectTree(graphAdapter.YGraph,
                                 graphAdapter.GetCopiedNode(graph.Nodes.First()));
  // Transfer back the result.
  IEnumerable<IEdge> el_igraph = graphAdapter.CreateEdgeEnumerable(el);
  foreach (IEdge e in el_igraph) {
    // Reverse the corresponding edges in the original IGraph.
    graph.Reverse(e);
  }

  // Get the leaf nodes of the tree.
  NodeList nl = Trees.GetLeafNodes(graphAdapter.YGraph, true);
  IEnumerable<INode> nl_igraph = graphAdapter.CreateNodeEnumerable(nl);
}