TarjanScc.hpp

Go to the documentation of this file.

/*
 * Copyright 2024 Håvard Krogstie <krogstie.havard@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_UTIL_TARJANSCC_HPP
#define JLM_UTIL_TARJANSCC_HPP
 
#include <jlm/util/common.hpp>
 
#include <cstddef>
#include <cstdint>
#include <limits>
#include <stack>
#include <vector>
 
namespace jlm::util
{
 
template<typename NodeType, typename UnificationRootFunctor, typename SuccessorFunctor>
NodeType
FindStronglyConnectedComponents(
    NodeType numNodes,
    UnificationRootFunctor unificationRoot,
    SuccessorFunctor & successors,
    std::vector<NodeType> & sccIndex,
    std::vector<NodeType> & reverseTopologicalOrder)
{
  NodeType sccsFinished = 0;
 
  // What SCC each node ends up in
  sccIndex.resize(numNodes);
  // Partially ordered topological order
  reverseTopologicalOrder.resize(0);
 
  // Use the max values of the NodeType as sentinel values
  const NodeType NOT_VISITED = std::numeric_limits<NodeType>::max();
  const NodeType SCC_FINISHED = NOT_VISITED - 1;
  JLM_ASSERT(numNodes <= SCC_FINISHED);
 
  // Non-recursive implementation of Tarjan's SCC
  std::vector<NodeType> order(numNodes, NOT_VISITED);
  NodeType nextOrder = 0;
  // The lowest order seen through any path of edges that do not enter finished SCCs
  std::vector<NodeType> lowLink(numNodes);
 
  // The DFS stack is a regular DFS traversal stack.
  // Note that the same element can be pushed many times, but will only be visited twice
  std::stack<NodeType> dfsStack;
  // The SCC stack is only popped once an SCC is found
  std::stack<NodeType> sccStack;
 
  // Find SCCs
  for (NodeType startNode = 0; startNode < numNodes; startNode++)
  {
    // Skip nodes that are not roots
    if (unificationRoot(startNode) != startNode)
      continue;
 
    // Only start DFSs at unvisited nodes
    if (order[startNode] != NOT_VISITED)
      continue;
 
    dfsStack.push(startNode);
    while (!dfsStack.empty())
    {
      auto node = dfsStack.top();
 
      if (order[node] == NOT_VISITED) // This is the first time node is visited
      {
        sccStack.push(node);
        order[node] = nextOrder++;
        lowLink[node] = order[node];
 
        for (auto next : successors(node))
        {
          next = unificationRoot(next);
 
          // Visit nodes that have not been visited before
          if (order[next] == NOT_VISITED)
            dfsStack.push(next);
        }
      }
      else if (order[node] == SCC_FINISHED) // This node has already been fully processed
      {
        dfsStack.pop();
      }
      else // This node is being visited for the second time, i.e., the dfs post-visit
      {
        dfsStack.pop();
 
        for (auto next : successors(node))
        {
          next = unificationRoot(next);
 
          // Ignore edges to nodes that are already part of a finished SCC
          if (order[next] == SCC_FINISHED)
            continue;
          lowLink[node] = std::min(lowLink[node], lowLink[next]);
        }
 
        // This node is the root of an SCC
        if (lowLink[node] == order[node])
        {
          const auto thisSccIndex = sccsFinished;
 
          while (true)
          {
            auto top = sccStack.top();
            sccStack.pop();
            order[top] = SCC_FINISHED;
            sccIndex[top] = thisSccIndex;
            reverseTopologicalOrder.push_back(top);
 
            if (top == node)
              break;
          }
 
          sccsFinished++;
        }
      }
    }
  }
  JLM_ASSERT(sccStack.empty());
 
  return sccsFinished;
}
 
template<typename NodeType, typename SuccessorFunctor>
NodeType
FindStronglyConnectedComponents(
    NodeType numNodes,
    SuccessorFunctor & successors,
    std::vector<NodeType> & sccIndex,
    std::vector<NodeType> & reverseTopologicalOrder)
{
  const auto identity = [](NodeType n)
  {
    return n;
  };
 
  // Because all nodes are roots, we know how long this vector needs to be
  reverseTopologicalOrder.reserve(numNodes);
 
  return FindStronglyConnectedComponents(
      numNodes,
      identity,
      successors,
      sccIndex,
      reverseTopologicalOrder);
}
 
}
 
#endif // JLM_UTIL_TARJANSCC_HPP