1
\$\begingroup\$

I adapted this Tarjan algorithm in JavaScript to be a little more functional and not pollute the Vertex object with temporary metadata, and arrived here:

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)
}

How could you make this into a nicer more well-abstracted function? Ideally it would avoid the recursion as well, but that may be a bonus just to keep things optimized and I really enjoy seeing how recursive things can be made iterative. Do we need the onStack variable, not sure if that can be somehow removed. By making it iterative, I was hoping we could somehow build the components array in a clean way, so it doesn't have to be passed down through state like it is now.

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.