Chapter 4. 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 yFiles FLEX Client Layout Extension 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 3, Using yFiles FLEX Client Layout Extension 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 4.1. Basic preparation for calling an analysis algorithm

// 'graph' is of type com.yworks.graph.model.IGraph.

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

// The yGraph property returns the com.yworks.yfiles.base.Graph instance that
// corresponds to the given IGraph above.
var isConnected:Boolean = 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 4.2. Graph analysis with an IGraph-based graph using adapter mechanisms

// 'graph' is of type com.yworks.graph.model.IGraph.

// Create the graph model adapter to get a proper analysis graph structure.
var graphAdapter:YGraphAdapter = 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.
  var el:EdgeList = Trees.directTreeWithRoot(
      graphAdapter.yGraph,
      graphAdapter.getCopiedNode(INode(graph.nodes.getItemAt(0))));

  // Transfer back the result.
  var el_it:Iterator = graphAdapter.createEdgeIterator(el);
  while (el_it.hasNext()) {
    var e:IEdge = IEdge(el_it.next());
    // Reverse the corresponding edges in the original IGraph.
    graph.setPorts(e, e.targetPort, e.sourcePort);
  }

  // Get the leaf nodes of the tree.
  var nl:NodeList = Trees.getLeafNodes(graphAdapter.yGraph, true);
  var nl_it:Iterator = graphAdapter.createNodeIterator(nl);
}

Tutorial demo application ShortestPathDemo.mxml also presents using the graph adapter mechanism.