Customizing Graph Analysis

The analysis classes and algorithms described in chapter Graph Analysis work on instances of IGraph, and in most cases, we recommend using them. However, algorithms available for the LayoutGraph API (for example, those from class LayoutGraphAlgorithms or custom ones) can also be applied to an IGraph-based graph structure by means of an adapter mechanism.

Structure Graph Adapter

The adapter class StructureGraphAdapter provides services for the necessary conversions before and during an analysis algorithm. Most notably, it creates a copy of an IGraph that can be used with these algorithms.

The following example demonstrates how the StructureGraphAdapter can be used, even though this specific use case would be much easier to achieve by using TreeAnalysis. It is meant to show the basic approach.

const iGraph = getGraph()

// Create the graph model adapter from the original IGraph.
const adapter = new StructureGraphAdapter(iGraph)
const structureGraph = adapter.structureGraph

// Test if the graph is a tree using an algorithm defined for LayoutGraph instances
if (LayoutGraphAlgorithms.isTree(structureGraph)) {
  // 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 originalFirstNode = iGraph.nodes.first()
  const copiedFirstNode = adapter.getCopiedNode(originalFirstNode)
  const reversedEdges = LayoutGraphAlgorithms.makeTreeDirected(
    structureGraph,
    copiedFirstNode
  )

  // Transfer back the result.
  for (const structureGraphEdge of reversedEdges) {
    // Reverse the corresponding edges of the original IGraph.
    iGraph.reverse(adapter.getOriginalEdge(structureGraphEdge))
  }
}
const iGraph = getGraph()

// Create the graph model adapter from the original IGraph.
const adapter = new StructureGraphAdapter(iGraph)
const structureGraph = adapter.structureGraph

// Test if the graph is a tree using an algorithm defined for LayoutGraph instances
if (LayoutGraphAlgorithms.isTree(structureGraph)) {
  // 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 originalFirstNode = iGraph.nodes.first()
  const copiedFirstNode = adapter.getCopiedNode(originalFirstNode!)
  const reversedEdges = LayoutGraphAlgorithms.makeTreeDirected(
    structureGraph,
    copiedFirstNode!
  )

  // Transfer back the result.
  for (const structureGraphEdge of reversedEdges) {
    // Reverse the corresponding edges of the original IGraph.
    iGraph.reverse(adapter.getOriginalEdge(structureGraphEdge)!)
  }
}

Depth-First Search

One example of an algorithm that is not available as a class working on IGraph is the depth-first search (DFS).

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

Take a 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. Note that the Start node is visited first and accordingly is assigned the first index (not shown).

The method LayoutGraphAlgorithms.dfs provides an implementation of the DFS algorithm. Through its several callback functions for events during a DFS run, it is highly customizable. The callbacks do nothing by default. The example code below demonstrates how to use the callback functions.

Events during a DFS run are pre- and post-visit events for nodes, and pre- and post-traversal events for edges. Another callback is provided to handle unconnected graphs, which is triggered when all nodes that are reachable from the starting node have been visited and there are still undiscovered nodes in the graph.

const iGraph = getGraph()
const myStartNode = getDfsStartNode()

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

// Run the depth-first search algorithm on the structure graph and define custom callbacks
LayoutGraphAlgorithms.dfs({
  graph: adapter.structureGraph,
  startingNode: adapter.getCopiedNode(myStartNode),

  nodeVisiting: (node, order) => {
    // Print the so-called "DFS number". it denotes when a node is currently visited.
    console.log(
      'Node: ' + adapter.getOriginalNode(node) + ' has DFS number: ' + order
    )
  },
  nodeVisited: (node, order, completionOrder) => {
    // Print the so-called "completion number". It denotes when a node has been completed.
    console.log(
      'Node: ' +
        adapter.getOriginalNode(node) +
        ' has completion number: ' +
        completionOrder
    )
  },
  nextTreeVisiting: (root) => {
    // Dfs starts from a new root node. Happens when the graph is unconnected, i.e., it has multiple components.
    console.log('New starting node: ' + adapter.getOriginalNode(root))
  }
})
const iGraph = getGraph()
const myStartNode = getDfsStartNode()

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

// Run the depth-first search algorithm on the structure graph and define custom callbacks
LayoutGraphAlgorithms.dfs({
  graph: adapter.structureGraph,
  startingNode: adapter.getCopiedNode(myStartNode)!,

  nodeVisiting: (node, order) => {
    // Print the so-called "DFS number". it denotes when a node is currently visited.
    console.log(
      'Node: ' + adapter.getOriginalNode(node) + ' has DFS number: ' + order
    )
  },
  nodeVisited: (node, order, completionOrder) => {
    // Print the so-called "completion number". It denotes when a node has been completed.
    console.log(
      'Node: ' +
        adapter.getOriginalNode(node) +
        ' has completion number: ' +
        completionOrder
    )
  },
  nextTreeVisiting: (root) => {
    // Dfs starts from a new root node. Happens when the graph is unconnected, i.e., it has multiple components.
    console.log('New starting node: ' + adapter.getOriginalNode(root))
  }
})