llvm/llvm/include/llvm/ADT/SCCIterator.h

//===- ADT/SCCIterator.h - Strongly Connected Comp. Iter. -------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
/// \file
///
/// This builds on the llvm/ADT/GraphTraits.h file to find the strongly
/// connected components (SCCs) of a graph in O(N+E) time using Tarjan's DFS
/// algorithm.
///
/// The SCC iterator has the important property that if a node in SCC S1 has an
/// edge to a node in SCC S2, then it visits S1 *after* S2.
///
/// To visit S1 *before* S2, use the scc_iterator on the Inverse graph. (NOTE:
/// This requires some simple wrappers and is not supported yet.)
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_SCCITERATOR_H
#define LLVM_ADT_SCCITERATOR_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/iterator.h"
#include <cassert>
#include <cstddef>
#include <iterator>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

namespace llvm {

/// Enumerate the SCCs of a directed graph in reverse topological order
/// of the SCC DAG.
///
/// This is implemented using Tarjan's DFS algorithm using an internal stack to
/// build up a vector of nodes in a particular SCC. Note that it is a forward
/// iterator and thus you cannot backtrack or re-visit nodes.
template <class GraphT, class GT = GraphTraits<GraphT>>
class scc_iterator : public iterator_facade_base<
                         scc_iterator<GraphT, GT>, std::forward_iterator_tag,
                         const std::vector<typename GT::NodeRef>, ptrdiff_t> {
  using NodeRef = typename GT::NodeRef;
  using ChildItTy = typename GT::ChildIteratorType;
  using SccTy = std::vector<NodeRef>;
  using reference = typename scc_iterator::reference;

  /// Element of VisitStack during DFS.
  struct StackElement {
    NodeRef Node;         ///< The current node pointer.
    ChildItTy NextChild;  ///< The next child, modified inplace during DFS.
    unsigned MinVisited;  ///< Minimum uplink value of all children of Node.

    StackElement(NodeRef Node, const ChildItTy &Child, unsigned Min)
        : Node(Node), NextChild(Child), MinVisited(Min) {}

    bool operator==(const StackElement &Other) const {
      return Node == Other.Node &&
             NextChild == Other.NextChild &&
             MinVisited == Other.MinVisited;
    }
  };

  /// The visit counters used to detect when a complete SCC is on the stack.
  /// visitNum is the global counter.
  ///
  /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
  unsigned visitNum;
  DenseMap<NodeRef, unsigned> nodeVisitNumbers;

  /// Stack holding nodes of the SCC.
  std::vector<NodeRef> SCCNodeStack;

  /// The current SCC, retrieved using operator*().
  SccTy CurrentSCC;

  /// DFS stack, Used to maintain the ordering.  The top contains the current
  /// node, the next child to visit, and the minimum uplink value of all child
  std::vector<StackElement> VisitStack;

  /// A single "visit" within the non-recursive DFS traversal.
  void DFSVisitOne(NodeRef N);

  /// The stack-based DFS traversal; defined below.
  void DFSVisitChildren();

  /// Compute the next SCC using the DFS traversal.
  void GetNextSCC();

  scc_iterator(NodeRef entryN) : … { … }

  /// End is when the DFS stack is empty.
  scc_iterator() = default;

public:
  static scc_iterator begin(const GraphT &G) { … }
  static scc_iterator end(const GraphT &) { … }

  /// Direct loop termination test which is more efficient than
  /// comparison with \c end().
  bool isAtEnd() const { … }

  bool operator==(const scc_iterator &x) const { … }

  scc_iterator &operator++() { … }

  reference operator*() const { … }

  /// Test if the current SCC has a cycle.
  ///
  /// If the SCC has more than one node, this is trivially true.  If not, it may
  /// still contain a cycle if the node has an edge back to itself.
  bool hasCycle() const;

  /// This informs the \c scc_iterator that the specified \c Old node
  /// has been deleted, and \c New is to be used in its place.
  void ReplaceNode(NodeRef Old, NodeRef New) { … }
};

template <class GraphT, class GT>
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) { … }

template <class GraphT, class GT>
void scc_iterator<GraphT, GT>::DFSVisitChildren() { … }

template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() { … }

template <class GraphT, class GT>
bool scc_iterator<GraphT, GT>::hasCycle() const { … }

/// Construct the begin iterator for a deduced graph type T.
template <class T> scc_iterator<T> scc_begin(const T &G) { … }

/// Construct the end iterator for a deduced graph type T.
template <class T> scc_iterator<T> scc_end(const T &G) { … }

/// Sort the nodes of a directed SCC in the decreasing order of the edge
/// weights. The instantiating GraphT type should have weighted edge type
/// declared in its graph traits in order to use this iterator.
///
/// This is implemented using Kruskal's minimal spanning tree algorithm followed
/// by Kahn's algorithm to compute a topological order on the MST. First a
/// maximum spanning tree (forest) is built based on all edges within the SCC
/// collection. Then a topological walk is initiated on tree nodes that do not
/// have a predecessor and then applied to all nodes of the SCC. Such order
/// ensures that high-weighted edges are visited first during the traversal.
template <class GraphT, class GT = GraphTraits<GraphT>>
class scc_member_iterator {
  using NodeType = typename GT::NodeType;
  using EdgeType = typename GT::EdgeType;
  using NodesType = std::vector<NodeType *>;

  // Auxilary node information used during the MST calculation.
  struct NodeInfo {
    NodeInfo *Group = this;
    uint32_t Rank = 0;
    bool Visited = false;
    DenseSet<const EdgeType *> IncomingMSTEdges;
  };

  // Find the root group of the node and compress the path from node to the
  // root.
  NodeInfo *find(NodeInfo *Node) { … }

  // Union the source and target node into the same group and return true.
  // Returns false if they are already in the same group.
  bool unionGroups(const EdgeType *Edge) { … }

  std::unordered_map<NodeType *, NodeInfo> NodeInfoMap;
  NodesType Nodes;

public:
  scc_member_iterator(const NodesType &InputNodes);

  NodesType &operator*() { … }
};

template <class GraphT, class GT>
scc_member_iterator<GraphT, GT>::scc_member_iterator(
    const NodesType &InputNodes) { … }
} // end namespace llvm

#endif // LLVM_ADT_SCCITERATOR_H