How to take the output of Tarjan's algorithm (Strongly Connected Components) and then iterate over the nodes in topologically sorted order?

Question

Here is an adapted Tarjan's JavaScript code:

function execute(graph) {
  const state = {
    stack: [],
    indexCounter: 0,
    traversibleVertex: {},
    components: [],
  }

  for (const vertex in graph) {
    if (!state.traversibleVertex[vertex]) {
      const v = state.traversibleVertex[vertex] = {
        name: vertex,
        index: null,
        lowLink: null,
        onStack: false,
      }
      strongConnect(graph, state, v)
    }
  }

  return state.components
}

function strongConnect(graph, state, vertex) {
  vertex.index = state.indexCounter;
  vertex.lowLink = state.indexCounter;
  state.indexCounter++;

  state.stack.push(vertex);
  vertex.onStack = true;

  const children = graph[vertex.name]

  for (var childName of children) {
    let child = state.traversibleVertex[childName]
    if (!child) {
      child = state.traversibleVertex[childName] = {
        name: childName,
        index: null,
        lowLink: null,
        onStack: false,
      }
      strongConnect(graph, state, child);
      vertex.lowLink = Math.min(vertex.lowLink, child.lowLink);
    } else if (child.onStack) {
      vertex.lowLink = Math.min(vertex.lowLink, child.lowLink);
    }
  }

  if (vertex.lowLink === vertex.index) {
    const stronglyConnectedComponents = [];
    let w = null;

    while (vertex != w) {
      w = state.stack.pop();
      w.onStack = false;
      stronglyConnectedComponents.push(w.name);
    }

    state.components.push(stronglyConnectedComponents)
  }
}

const graph = {}

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

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

console.log(execute(graph))

function addV(vertex) {
  graph[vertex] = []
}

function addE(v1, edges) {
  graph[v1].push(...edges)
}

It outputs:

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

But the correct sort order (I think) is something more like this:

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

Did I miss something basic in the description of Tarjan's algorithm? Is there a way to order it according to the topological sort? I'm not sure if I just need to reverse the top-level array (I may have read that somewhere), or if something more intense needs to be done.

How do you topologically sort the output from Tarjan's algorithm, or get the result in sorted order somehow? Just want to make sure here I'm on the right track.

score 0 · Accepted Answer · answered Nov 16 '22 at 12:33

Since it's based on depth-first-search, the order in which it completes each SCC is the reverse of a valid topological ordering among SCCs.

The question is whether or not your particular implementation produces its output in this particular order. After examining your code, I believe it does, so yes, you just have to reverse the top-level array.

How to take the output of Tarjan's algorithm (Strongly Connected Components) and then iterate over the nodes in topologically sorted order?

1 Answers1