graph.hh

#pragma once
 
#include <cstddef>
#include <vector>
 
namespace CppClingo::Util {
 
 
class Graph {
  public:
    using IdVec = std::vector<size_t>;
    using SCCVec = std::vector<IdVec>;
 
    template <class Callback> void tarjan(Callback cb);
    void ensure_size(size_t n);
    void add_edge(size_t u, size_t v);
    [[nodiscard]] auto has_loop(size_t u) const -> bool;
    void clear() {
        phase_ = 0;
        nodes_.clear();
    }
 
  private:
    struct Node {
        Node(size_t visited) : visited_(visited) {}
        IdVec out;
        IdVec::iterator finished_;
        size_t visited_;
    };
 
    [[nodiscard]] auto prev_phase_() const -> size_t;
 
    std::vector<Node> nodes_;
    size_t phase_ = 0;
};
 
inline auto Graph::prev_phase_() const -> size_t {
    return phase_ == 0 ? 1 : 0;
}
 
inline void Graph::ensure_size(size_t n) {
    if (nodes_.size() < n) {
        while (nodes_.size() < n) {
            nodes_.emplace_back(prev_phase_());
        }
    }
}
 
inline void Graph::add_edge(size_t u, size_t v) {
    ensure_size(std::max(u, v) + 1);
    nodes_[u].out.emplace_back(v);
}
 
inline auto Graph::has_loop(size_t u) const -> bool {
    return std::ranges::find(nodes_[u].out, u) != nodes_[u].out.end();
}
 
template <class Callback> inline void Graph::tarjan(Callback cb) {
    IdVec scc;
    IdVec stack;
    IdVec trail;
    for (size_t id_x = 0, n = nodes_.size(); id_x != n; ++id_x) {
        auto &x = nodes_[id_x];
        if (x.visited_ == prev_phase_()) {
            unsigned index = 1;
            auto push = [&stack, &trail, &index, this](size_t id_x) {
                auto &x = nodes_[id_x];
                x.visited_ = ++index;
                x.finished_ = x.out.begin();
                stack.emplace_back(id_x);
                trail.emplace_back(id_x);
            };
            push(id_x);
            while (!stack.empty()) {
                auto id_y = stack.back();
                auto &y = nodes_[id_y];
                auto end = y.out.end();
                for (; y.finished_ != end && nodes_[*y.finished_].visited_ != prev_phase_(); ++y.finished_) {
                }
                if (y.finished_ != end) {
                    push(*y.finished_++);
                } else {
                    stack.pop_back();
                    bool root = true;
                    for (auto id_z : y.out) {
                        auto &z = nodes_[id_z];
                        if (z.visited_ != phase_ && z.visited_ < y.visited_) {
                            root = false;
                            y.visited_ = z.visited_;
                        }
                    }
                    if (root) {
                        do {
                            scc.emplace_back(trail.back());
                            nodes_[trail.back()].visited_ = phase_;
                            trail.pop_back();
                        } while (scc.back() != id_y);
                        cb(scc);
                        scc.clear();
                    }
                }
            }
        }
    }
    phase_ = prev_phase_();
}
 
 
} // namespace CppClingo::Util