Using Graph Analysis

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

For configuration most algorithm classes provide several properties, and some of those are mandatory to be set for the algorithm to run. These properties are often of type ItemMapping<TItem,TValue>, ItemCollection<TItem> or SingleItem<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 to graph items are provided as the same collection types as used by LayoutData. Namely, these are SingleItem<TItem> if exactly one item has to be provided, ItemCollection<TItem> for a collection of items, and ItemMapping<TItem,TValue> for values associated with items. The example below shows their usage.

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.selectedNodes,
  // 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.selectedNodes,
  // a mapping: edge costs
  costs: (edge) => edge.style.renderer.getPathGeometry(edge, edge.style).getPath()!.getLength()
})

After configuring the algorithm via its properties, its run method has to be called. 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 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. This is a convenient and type safe way to access the collections and maps the result of the algorithm 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.
forEach(action: Action3<MapEntry<TKey, TValue>, number, IEnumerable<T>>, thisArg: Object): void: Performs the given action on each item/value pair.
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 ICollection<T>.

Analyzing Only Part of a Graph

Most analysis algorithms support handling only part of the complete graph. This can be useful, e.g., to confine a costly analysis to just a single component, or the part of the graph that’s currently visible.

Analysis algorithms supporting analyzing only a subgraph all have two additional properties: subgraphNodes and subgraphEdges. When nothing is set on those properties, the complete graph is used. subgraphNodes is considered before subgraphEdges, and edges that don’t connect two nodes from subgraphNodes are automatically excluded, even before subgraphEdges are considered.

There are two main ways of specifying a subset. The first is to explicitly specify the items that belong to 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 items that should be excluded 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)

Both includes and excludes can be combined. The following example shows how to include all visible nodes but not the 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 result returned will also only contain information about the subgraph.

Since results and subgraphs are modeled with collections, the result of one analysis algorithm can be used as input for the subgraph of another. Here we first determine the connected components of the graph and run 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)

Graph Analysis Centrality Measures