Graph Analysis: The Algorithms Graph API

The analysis classes with an IGraph-based API mainly provide a convenient wrapping of the actual algorithm implementations which work on the basic algorithms graph structure.

In most cases we recommend to use the classes described in Graph Analysis. You can however use the original analysis algorithms with an IGraph-based graph structure by means of an adapter mechanism similar to the one for automatic layouts.

YGraphAdapter

The adapter class YGraphAdapter provides services for the necessary conversions prior to and during a graph analysis. Most notably, it creates a copy of an IGraph that can be used with such algorithms:

const graph = getMyGraph()

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

// The yGraph property returns the Graph instance that
// corresponds to the given IGraph above.
const isConnected = GraphChecker.isConnected(graphAdapter.yGraph)
const graph: IGraph = getMyGraph()

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

// The yGraph property returns the Graph instance that
// corresponds to the given IGraph above.
const 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.

const graph = getMyGraph()

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

// Test if the graph is a tree.
if (TreeAlgorithm.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.
  const firstNode = graph.nodes.first()
  const el = TreeAlgorithm.directTree(graphAdapter.yGraph, graphAdapter.getCopiedNode(firstNode))
  // Transfer back the result.
  const elIGraph = graphAdapter.createEdgeEnumerable(el)
  elIGraph.forEach((e) => {
    // Reverse the corresponding edges in the original IGraph.
    graph.reverse(e)
  })

  // Get the leaf nodes of the tree.
  const nl = TreeAlgorithm.getLeafNodes(graphAdapter.yGraph, true)
  const nlIGraph = graphAdapter.createNodeEnumerable(nl)
}
const graph: IGraph = getMyGraph()

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

// Test if the graph is a tree.
if (TreeAlgorithm.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.
  const firstNode = graph.nodes.first()
  const el = TreeAlgorithm.directTree(graphAdapter.yGraph, graphAdapter.getCopiedNode(firstNode))
  // Transfer back the result.
  const elIGraph = graphAdapter.createEdgeEnumerable(el)
  elIGraph.forEach((e) => {
    // Reverse the corresponding edges in the original IGraph.
    graph.reverse(e)
  })

  // Get the leaf nodes of the tree.
  const nl = TreeAlgorithm.getLeafNodes(graphAdapter.yGraph, true)
  const nlIGraph = graphAdapter.createNodeEnumerable(nl)
}

The graph adapter YGraphAdapter is used in the demo application Graph Analysis.

Depth-First Search

One example of an algorithm that is not available with an IGraph-based API is the depth-first search (DFS).

Beginning at a starting node, DFS recursively visits the first yet undiscovered direct neighbor of every reached node before continuing in the same manner with the remaining neighbors at this node.

Look at the example graph in Depth-first search graph traversal. The numbers at the upper-right corners of the nodes denote the visiting sequence with directed DFS. Additionally, the emphasized edges show the path of the DFS run. Observe that the Start node is visited first and accordingly is assigned the first index (not shown).

Class Dfs is used as a framework to build customized depth-first search services. It offers a collection of callback methods for all important events during a DFS run. These callbacks are empty by default, and have to be overwritten appropriately by an inheriting class. Using class Dfs demonstrates how to use the callback methods provided by class Dfs.

Events during a DFS run are pre- and post-visit events with nodes and pre- and post-traversal events with edges. Another callback is provided to handle unconnected graphs when all nodes that are reachable from the starting node have been visited and there are still undiscovered nodes in the graph. Note that the invocation of this callback can optionally be disabled.

Class Dfs either ignores or respects edge directions, i.e., it interprets the graph structure either undirected or directed.

// Extend class Dfs.

class MyDFS extends DfsAlgorithm {
  graphAdapter

  /**
   * @param {!YGraphAdapter} graphAdapter
   */
  constructor(graphAdapter) {
    super()
    this.graphAdapter = graphAdapter
  }

  /**
   * Print the so-called "DFS number."
   * This number denotes when a node is visited.
   * @param {!YNode} node
   * @param {number} dfsNumber
   */
  preVisit(node, dfsNumber) {
    console.log('Node: ' + this.graphAdapter.getOriginalNode(node) + ' has DFS number: ' + dfsNumber)
  }

  /**
   * Print the so-called "completion number."
   * This number denotes when a node has been completed.
   * @param {!YNode} node
   * @param {number} dfsNumber
   * @param {number} compNumber
   */
  postVisit(node, dfsNumber, compNumber) {
    console.log(`Node: ${this.graphAdapter.getOriginalNode(node)} has completion numbers: ${compNumber}`)
  }

  /**
   * The graph is unconnected, i.e., it has multiple components.
   * @param {!YNode} v
   */
  lookFurther(v) {
    console.log(`New starting node: ${this.graphAdapter.getOriginalNode(v)}`)
  }

  /**
   * Instantiate the customized class.
   * @param {!IGraph} graph
   */
  static runDFS(graph) {
    // Create the graph model adapter to get a proper analysis graph structure.
    const graphAdapter = new YGraphAdapter(graph)

    const myDFS = new MyDFS(graphAdapter)
    // Set directed interpretation of the graph structure.
    myDFS.directedMode = true

    // Run the depth-first search algorithm on the given graph.
    myDFS.start(graphAdapter.yGraph)
  }
}// Extend class Dfs.

class MyDFS extends DfsAlgorithm {
  graphAdapter: YGraphAdapter

  constructor(graphAdapter: YGraphAdapter) {
    super()
    this.graphAdapter = graphAdapter
  }

  /**
   * Print the so-called "DFS number."
   * This number denotes when a node is visited.
   */
  preVisit(node: YNode, dfsNumber: number): void {
    console.log('Node: ' + this.graphAdapter.getOriginalNode(node) + ' has DFS number: ' + dfsNumber)
  }

  /**
   * Print the so-called "completion number."
   * This number denotes when a node has been completed.
   */
  postVisit(node: YNode, dfsNumber: number, compNumber: number): void {
    console.log(`Node: ${this.graphAdapter.getOriginalNode(node)} has completion numbers: ${compNumber}`)
  }

  /**
   * The graph is unconnected, i.e., it has multiple components.
   */
  lookFurther(v: YNode): void {
    console.log(`New starting node: ${this.graphAdapter.getOriginalNode(v)}`)
  }

  /**
   * Instantiate the customized class.
   */
  static runDFS(graph: IGraph): void {
    // Create the graph model adapter to get a proper analysis graph structure.
    const graphAdapter = new YGraphAdapter(graph)

    const myDFS = new MyDFS(graphAdapter)
    // Set directed interpretation of the graph structure.
    myDFS.directedMode = true

    // Run the depth-first search algorithm on the given graph.
    myDFS.start(graphAdapter.yGraph)
  }
}