How to break down Strongly Connected Components (SCC) in a graph to obtain smaller and smaller nested cycles in JavaScript?

Question

So I have been wondering about how to convert complex graphs with nested cycles into simple Directed Acyclic Graphs (DAGs). I think I landed on the solution (not 100% sure). The solution is to use Kosaraju's algorithm, which I have borrowed from here in JavaScript, and got it working on that first link's complex graph.

The code below isolates these SCCs:

[
  [ 'A' ],
  [ 'C' ],
  [ 'B' ],
  [
    'D', 'J', 'I',
    'H', 'F', 'E',
    'K', 'G'
  ],
  [ 'M' ],
  [ 'N' ],
  [ 'O' ],
  [ 'L' ]
]

The problem is, D-J-I-H-F-E-K-G actually contains 2 nested cycles (shown in that first link), F-G-K and H-I-J. Is there any way to get this code to break down that 8-node SCC into like 4 smaller ones (F-G-K, H-I-J, D, E)? Is there any way to sort of recursively break down the SCCs so they isolate smaller and smaller SCCs? That would be great, because I am thinking how to do like a module system which handles circular dependencies, and if you can have small cycles compose into larger cycles, then you can parallelize some work. In the end, this Kosaraju algorithm at least identifies and returns the broadest cycles it seems in these initial tests, but I would like to get more exact and break down the cycles further if possible.

Is there any technique which can do this? If so, what should I be looking at, and or if you know how it is implemented that would be helpful to know as well.

Here is the Kosaraju algorithm code. The first g1 graph is the image above, and the g2 graph is just the 8-node SCC. I tried to run it on just that to see if it would recursively break it down, but sadly it doesn't.

class Stack {
  constructor() {
    this.stack = [];
  }

  isEmpty() {
    return this.stack.length == 0;
  }

  size() {
    return this.stack.length;
  }

  push(item) {
    this.stack.push(item);
  }

  pop() {
    if (this.isEmpty()) {
      throw new Error("Stack is empty");
    }
    return this.stack.pop();
  }

  peek() {
    if (this.isEmpty()) {
      throw new Error("Stack is empty");
    }
    return this.stack[this.stack.length - 1];
  }
}

class Graph {
  constructor() {
    this.vertices = new Set();
    this.adjacencyMap = new Map();
    this.adjacencyMapReversed = new Map();
    this.stack = new Stack();
    this.colors = new Map();
  }

  addVertex(vertex) {
    this.vertices.add(vertex);
    this.adjacencyMap.set(vertex, new Set());
    this.adjacencyMapReversed.set(vertex, new Set());
    this.colors.set(vertex, "white");
  }

  addEdge(v1, v2) {
    this.adjacencyMap.get(v1).add(v2);
    this.adjacencyMapReversed.get(v2).add(v1);
  }

  kosaraju() {
    for (let v of this.vertices) {
      if (this.colors.get(v) == "white") {
        this.dfs(v);
      }
    }

    for (let v of this.colors.keys()) {
      this.colors.set(v, "white");
    }

    let connected = [];

    while (!this.stack.isEmpty()) {
      let v = this.stack.pop();
      if (this.colors.get(v) == "white") {
        let c = [];
        this.dfsReversed(v, c);
        if (c.length > 0) {
          connected.push(c);
        }
      }
    }

    return connected
  }

  dfs(vertex) {
    this.colors.set(vertex, "gray");

    let neighbours = this.adjacencyMap.get(vertex);
    for (let n of neighbours) {
      if (this.colors.get(n) == "white") {
        this.dfs(n);
      }
    }

    this.colors.set(vertex, "black");
    this.stack.push(vertex);
  }

  dfsReversed(v, c) {
    this.colors.set(v, "gray");
    c.push(v);

    let neighbours = this.adjacencyMapReversed.get(v);
    for (let n of neighbours) {
      if (this.colors.get(n) == "white") {
        this.dfsReversed(n, c);
      }
    }

    this.colors.set(v, "black");
  }
}

const g1 = new Graph();

addV(g1, 'A')
addV(g1, 'B')
addV(g1, 'C')
addV(g1, 'D')
addV(g1, 'E')
addV(g1, 'F')
addV(g1, 'G')
addV(g1, 'H')
addV(g1, 'I')
addV(g1, 'J')
addV(g1, 'M')
addV(g1, 'N')
addV(g1, 'K')
addV(g1, 'L')
addV(g1, 'O')

addE(g1, 'A', ['B', 'C'])
addE(g1, 'B', ['D', 'G'])
addE(g1, 'C', ['D'])
addE(g1, 'D', ['E'])
addE(g1, 'E', ['F', 'K'])
addE(g1, 'F', ['G', 'H', 'M'])
addE(g1, 'G', ['H', 'L', 'N', 'K'])
addE(g1, 'H', ['I'])
addE(g1, 'I', ['J'])
addE(g1, 'J', ['D', 'H'])
addE(g1, 'M', ['O'])
addE(g1, 'N', ['O'])
addE(g1, 'K', ['L', 'F'])

console.log(g1.kosaraju());

// just the outer and inner cycles, not the rest:
const g2 = new Graph();

addV(g2, "D");
addV(g2, "E");
addV(g2, "F");
addV(g2, "G");
addV(g2, "H");
addV(g2, "I");
addV(g2, "J");
addV(g2, "K");

addE(g2, "D", ["E"]);
addE(g2, "E", ["F", "K"]);
addE(g2, "F", ["G", "H"]);
addE(g2, "G", ["H", "K"]);
addE(g2, "H", ["I"]);
addE(g2, "I", ["J"]);
addE(g2, "J", ["D", "H"]);
addE(g2, "K", ["F"]);

console.log(g2.kosaraju());

function addV(g, vertex) {
  g.addVertex(vertex);
}

function addE(g, vertex, edges) {
  edges.forEach((edge) => g.addEdge(vertex, edge));
}

Answer 1

Here are two algorithms based on a depth first search traversal of the complex graph found in the question, highlighting the challenges of identifying subcycles as mentioned in @Bergi's comments to the question.

The first algorithm applies no heuristics, and simply captures all cycles found during the traversal.

The second algorithm, when finding a cycle, orders the chain by the least of the nodes, to eliminate cycles that are duplicate only because the cycle was traversed beginning with a different node in the chain.

nodes = {
  a: [ 'b', 'c' ],
  b: [ 'd', 'g' ],
  c: [ 'd' ],
  d: [ 'e' ],
  e: [ 'f', 'k' ],
  f: [ 'g', 'h' , 'm' ],
  g: [ 'h', 'k', 'l', 'n' ],
  h: [ 'i' ],
  i: [ 'j' ],
  j: [ 'h', 'd' ],
  k: [ 'f', 'l' ],
  l: [],
  m: [ 'o' ],
  n: [ 'o' ],
  o: []
};



function findCyclesV1( rootNode) {

  function findCycles( node, chain ) {
    let n = chain.indexOf( node );
    if ( 0 <= n ) {
      result.add( chain.slice( n ) );
      return;
    } 
      
    chain += node;
    
    for ( let nextNode of nodes[ node ] ) {
      findCycles( nextNode, chain );
    }
  }
  
  let result = new Set();
  findCycles( rootNode, '' );
  return result;
}


function findCyclesV2( rootNode) {

  function findCycles( node, chain ) {
    let n = chain.indexOf( node );
    if ( 0 <= n ) {
      let subChain = chain.slice( n )

      // Normalize the chain by ensuring the lowest node is first.
      let leastNode = subChain.split('').reduce( ( t, c ) => t = c < t ? c : t );
      let m = subChain.indexOf( leastNode );
      
      result.add( subChain.slice( m ) + subChain.slice( 0, m ) );
      return;
    } 
      
    chain += node;
    
    for ( let nextNode of nodes[ node ] ) {
      findCycles( nextNode, chain );
    }
  }
  
  let result = new Set();
  findCycles( rootNode, '' );
  return result;
}

console.log( 'Algorithm 1: ', [ ...findCyclesV1( 'a' ) ].sort() );

console.log( 'Algorithm 2: ', [ ...findCyclesV2( 'a' ) ].sort() );

A couple of notables about the results of the second algorithm...

• The algorithm assumes that there is a root entry into the graph, that when traversed, can reach all nodes.
• Note that of the cycles de..., half are due to a side step to node g which is a node path slipped betwixt nodes f and h. The same holds for node k which is a side step betwixt nodes e and f.
• Subcycle hij is easily recognizable in the de... cycles, but the same can't be said for subcycle fgk, which does appear in cycle dekfghij, but as kfg. So any algorithm that attempts to draw out subcycles will have to take variations of the subcycle node order into consideration.

Given all of the above, the challenge is to define a data structure that allows for incorporation of sidesteps and subcycles. In a regexp-ish like way, something along the following lines...

• de[k*fg*|[kfg]][hij]

...implying that the cycle must...

• 1) begin with de, optionally followed by
• 2a) k*fg* (where k and g are optional, and thus this is not a subcycle due to side steps) or
• 2b) subcycle kfg, followed by
• 3) subcycle hij...

Note also that it's not clear whether there will be other substructures that emerge from more complex graphs that will have to be taken into consideration when attempting to incorporate the cyclic flows into a compact data structure...