Using Graph Analysis

The analysis algorithms use a common pattern to configure, run, and return the results.

To configure an algorithm, most algorithm classes provide properties. Some of these properties are mandatory for the algorithm to run. These properties are often of type ItemMapping<TItem,TValue> or ItemCollection<TItem>. These types provide several properties to specify additional data for the graph in different ways. Type conversion allows you to omit these intermediate properties and directly assign the property of the actual algorithm.

Basic initialization and configuration of an algorithm

const shortestPath = new ShortestPath({
  source: node1,
  sink: node2
})

Graph items and values associated with graph items are provided as the same collection types as used by Layout Data. Namely, these are ItemCollection<TItem> if you need to provide a single item or a collection of items, and ItemMapping<TItem,TValue> for values associated with items. The example below shows how to use them.

Providing graph items

const singleSourceShortestPaths = new SingleSourceShortestPaths({
  // a single item: the given node
  source: node1,
  // a collection of items: the selected nodes
  sinks: graphComponent.selection.nodes,
  // a mapping: edge costs
  costs: (edge) =>
    edge.style.renderer
      .getPathGeometry(edge, edge.style)
      .getPath()
      .getLength()
})
const singleSourceShortestPaths = new SingleSourceShortestPaths({
  // a single item: the given node
  source: node1,
  // a collection of items: the selected nodes
  sinks: graphComponent.selection.nodes,
  // a mapping: edge costs
  costs: (edge) =>
    edge.style.renderer
      .getPathGeometry(edge, edge.style)
      .getPath()!
      .getLength()
})

After configuring the algorithm via its properties, call its run method. This method takes an IGraph and returns a ShortestPathResult object, whose class is specific to the chosen algorithm.

Running the algorithm

const shortestPathResult = shortestPath.run(graph)

The returned ShortestPathResult object provides the algorithm’s results as read-only properties.

Evaluating the algorithm result

const pathEdges = shortestPathResult.edges
pathEdges.forEach((edge) => highlightEdge(edge))

The properties of the various ShortestPathResult classes are commonly either of type ResultItemMapping<TKey,TValue> or ResultItemCollection<T>. The former maps an element (commonly a graph element) to an arbitrary object. The latter is a collection of items. These provide a convenient and type-safe way to access the collections and maps that the algorithm’s result consists of.

ResultItemMapping
size: number: Gets the number of elements in the result mapping.
keys: IEnumerable<TKey>: Gets all items that are keys in the result mapping.
values: IEnumerable<TValue>: Gets all values in the result mapping.
copyTo(mapper: IMapper<TKey, TValue>): void: Copies the entries of the result mapping into the given IMapper<K,V>.
copyTo(dictionary: IMap<TKey, TValue>): void: Copies the entries of the result mapping into the given IMap<TKey,TValue>.
getEnumerator(): IEnumerator<MapEntry<TKey, TValue>>: Gets an IEnumerator<T> to iterate the MapEntry<TKey,TValue> of this mapping.
get: Gets the result value for a given item.
ResultItemCollection
contains(item: T): boolean: Returns whether an item is contained in the result collection.
getEnumerator(): IEnumerator<T>: Gets an IEnumerator<T> to iterate the items in the result collection.
size: number: Returns the number of items in the result collection.
get: Gets the item at the specified index from the result collection.
forEach(action: Action3<T, number, IEnumerable<T>>, thisArg: Object): void: Performs the given action on each item.
copyTo(collection: ICollection<T>): void: Copies the items in the result collection into the given {T_ICollection}.

Analyzing Only Part of a Graph

Most analysis algorithms can be configured to analyze only a portion of the complete graph. This is useful for situations such as limiting an expensive analysis to a specific component or to the currently visible part of the graph.

Analysis algorithms that support subgraph analysis have two additional properties: subgraphNodes and subgraphEdges. If these properties are not set, the entire graph is analyzed. subgraphNodes takes precedence over subgraphEdges. Edges that do not connect two nodes within subgraphNodes are automatically excluded, even before subgraphEdges is considered.

There are two main ways to specify a subset. The first is to explicitly specify the items to include in the subset:

// Calculate centrality values only for the subgraph visible on the screen
const centrality = new BetweennessCentrality({
  subgraphNodes: (node) =>
    node.layout.toRect().intersects(graphComponent.viewport)
})
const result = centrality.run(graph)

The second option is to specify the items to exclude from the graph:

// Calculate centrality values over the subgraph without the given edges
const centrality = new BetweennessCentrality({
  subgraphEdges: {
    excludes: {
      source: ignoredEdges
    }
  }
})
const result = centrality.run(graph)

Includes and excludes can be combined. The following example demonstrates how to include all visible nodes while excluding group nodes:

// Calculate centrality values
const centrality = new BetweennessCentrality({
  subgraphNodes: {
    // only for the subgraph visible on the screen
    includes: (node) =>
      node.layout.toRect().intersects(graphComponent.viewport),
    // but not for group nodes
    excludes: (node) => graph.isGroupNode(node)
  }
})
const result = centrality.run(graph)
// Calculate centrality values
const centrality = new BetweennessCentrality({
  subgraphNodes: {
    // only for the subgraph visible on the screen
    includes: (node: INode): boolean =>
      node.layout.toRect().intersects(graphComponent.viewport),
    // but not for group nodes
    excludes: (node: INode): boolean => graph.isGroupNode(node)
  }
})
const result = centrality.run(graph)

The analysis results will only contain information about the analyzed subgraph.

Since both results and subgraphs are represented as collections, the output of one analysis algorithm can be used as the subgraph input for another. Here’s an example of determining the connected components of a graph and then running Betweenness Centrality only on the first component:

const componentResult = new ConnectedComponents().run(graph)

const centrality = new BetweennessCentrality({
  subgraphNodes: {
    source: componentResult.components.first().nodes
  }
})

const result = centrality.run(graph)
const componentResult = new ConnectedComponents().run(graph)

const centrality = new BetweennessCentrality({
  subgraphNodes: {
    source: componentResult.components.first()!.nodes
  }
})

const result = centrality.run(graph)

Graph Analysis Centrality Measures