incremental_cycles.h

// Copyright 2025 Google LLC.
// SPDX-License-Identifier: Apache-2.0

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>

#include "third_party/absl/container/flat_hash_set.h"
#include "third_party/absl/strings/str_cat.h"
#include "util/graph/graph.h"
#include "util/intops/strong_int.h"

template <class Node>
class AcyclicGraph {
 public:
  // Attempt to add an arc, returning false if this would create a cycle. To
  // save time in the fast path, the cycle itself is not returned.
  bool TryAddArc(Node tail, Node head);

  // Add a node to 'graph()'
  void AddNode(Node node);

  const util::ListGraph<Node>& graph() const { return graph_; }

 private:
  struct NodeInfo {
    uint32_t level = 1;
    uint32_t mark = 0;
    absl::flat_hash_set<Node> same_level_reverse_edges;
  };

  uint32_t mark_ = 1;
  std::vector<NodeInfo> nodes_;
  util::ListGraph<Node> graph_;
  std::vector<Node> stack_;

  static inline size_t I(size_t n) { return n; }
  template <class Tag, class T>
  static inline size_t I(util_intops::StrongInt<Tag, T> n) {
    return n.value();
  }

  uint32_t& Level(Node n) { return nodes_[I(n)].level; }
  uint32_t& Mark(Node n) { return nodes_[I(n)].mark; }
  absl::flat_hash_set<Node>& SameLevelReverseEdges(Node n) {
    return nodes_[I(n)].same_level_reverse_edges;
  }
};

template <class Node>
void AcyclicGraph<Node>::AddNode(Node node) {
  graph_.AddNode(node);
}

// The Guéneau-Jourdan-Charguéraud-Pottier incremental cycle detection algorithm
// with a few tweaks:
//
// * The cycle is not returned (since we didn't need it for our use case).
// * We use two forwards searches rather than one, first to look for a cycle and
// then to fix up the levels. This is because if we move 'head' above 'tail'
// and then find out that there's a cycle (a path from 'head' to 'tail') it will
// break the invariant that the levels are a partial topological order. This
// requires an additional mark to keep the same worst-case runtime.
// * Rather than a list of same-level reverse edges, we use a set to make the
// fixup step simpler. The constant factor makes very little difference.
// * A special case where the forwards search is skipped is removed to simplify
// the code.
// * The style is changed slightly to better fit the imperative language.
//
// See https://gallium.inria.fr/blog/incremental-cycle-detection/.
template <class Node>
bool AcyclicGraph<Node>::TryAddArc(Node tail, Node head) {
  AddNode(tail);
  AddNode(head);
  nodes_.resize(I(graph_.num_nodes()));

  // Self-loop.
  if (tail == head) return false;
  // No cycle.
  if (Level(head) > Level(tail)) {
    graph_.AddArc(tail, head);
    return true;
  }

  // Maintain the level invariant if we insert the edge.
  uint32_t new_level = Level(tail);

  // We pick a new number each time.
  const uint32_t mark = mark_;
  const uint32_t forwards_mark = mark_ + 1;
  mark_ += 2;

  // Mark reverse dependencies, exploring up to 'fuel' edges.
  stack_ = {tail};
  uint32_t fuel = Level(tail);
  while (!stack_.empty()) {
    Node node = stack_.back();
    stack_.pop_back();
    if (Mark(node) == mark) continue;

    Mark(node) = mark;
    for (Node parent : SameLevelReverseEdges(node)) {
      if (fuel == 0) {
        // If we ran out of fuel, we will bump 'head' up above 'tail'.
        new_level = Level(tail) + 1;
        break;
      }
      stack_.push_back(parent);
      --fuel;
    }
  }

  // Can we skip the forwards search?
  if (Mark(head) == mark) return false;

  // Search forwards for cycles.
  stack_ = {head};
  while (!stack_.empty()) {
    Node node = stack_.back();
    stack_.pop_back();
    for (Node child : graph_[node]) {
      if (Mark(child) == mark) return false;
      if (Level(child) < new_level && Mark(child) != forwards_mark) {
        Mark(child) = forwards_mark;
        stack_.push_back(child);
      }
    }
  }

  // No cycle.
  graph_.AddArc(tail, head);

  // Set 'head' to new_level and fix up the level invariant.
  stack_ = {tail};
  while (!stack_.empty()) {
    Node parent = stack_.back();
    stack_.pop_back();
    for (Node child : graph_[parent]) {
      if (Level(child) < new_level) {
        Level(child) = new_level;
        SameLevelReverseEdges(child).clear();
        stack_.push_back(child);
      }
      if (Level(child) == Level(parent)) {
        SameLevelReverseEdges(child).insert(parent);
      }
    }
  }

  return true;
}