DAG Reachability and Transitive Reduction
(graph/dag_reachability.hpp)

View this file on GitHub
Last update: 2026-08-24 00:41:13+09:00
Include: #include "graph/dag_reachability.hpp"

Overview

This header provides batched reachability queries and transitive reduction for a directed acyclic graph. Both use dynamic bitsets propagated in reverse topological order. A cyclic graph returns std::nullopt.

dag_reachability includes every zero-edge path, so reachable(v, v) is true. The table is most appropriate when many reachability queries justify quadratic memory.

dag_transitive_reduction removes every edge whose endpoints remain connected by another directed path. It also reduces parallel edges to one representative. The returned graph has the same reachability relation as the active input graph; inactive edges are omitted. Costs do not affect reduction.

Types

Type	Member / method	Meaning	Complexity
`DagReachability`	`reachable_vertices`	Bitset of vertices reachable from each vertex.	Access to a bitset: $O(1)$
`DagReachability`	`topological_order`	Topological order used to build the table.	Access: $O(1)$
`DagReachability`	`int size() const`	Number of vertices.	$O(1)$
`DagReachability`	`bool reachable(int from, int to) const`	Tests directed reachability, including `from == to`.	$O(1)$
`DagTransitiveReductionResult<T>`	`graph`	Reduced graph. Its edge ids are newly assigned.	Access: $O(1)$
`DagTransitiveReductionResult<T>`	`original_edge_ids`	Maps each new edge id to the retained input edge id.	Access: $O(1)$

Functions

Function	Signature	Complexity
`dag_reachability`	`template <class T> std::optional<DagReachability> dag_reachability(const Graph<T>& g)`	$O((N + M)\lceil N / 64\rceil)$ time and $O(N\lceil N / 64\rceil)$ memory
`dag_transitive_reduction`	`template <class T> std::optional<DagTransitiveReductionResult<T>> dag_transitive_reduction(const Graph<T>& g)`	$O((N + M)\lceil N / 64\rceil + M\log M)$ time and $O(N\lceil N / 64\rceil + M)$ memory

The sorting term is the sum of sorting outgoing edges at each vertex and is at most $O(M\log M)$.

Example

#include "graph/dag_reachability.hpp"
#include "graph/graph.hpp"
#include <iostream>

int main() {
    m1une::graph::Graph<> g(3);
    g.add_directed_edge(0, 1);
    g.add_directed_edge(1, 2);
    g.add_directed_edge(0, 2);  // Redundant.

    auto reach = m1une::graph::dag_reachability(g);
    if (reach) std::cout << reach->reachable(0, 2) << '\n';

    auto reduction = m1une::graph::dag_transitive_reduction(g);
    if (reduction) std::cout << reduction->graph.edge_count() << '\n';  // 2
}

Depends on

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_DAG_REACHABILITY_HPP
#define M1UNE_GRAPH_DAG_REACHABILITY_HPP 1

#include <algorithm>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>

#include "../utilities/dynamic_bitset.hpp"
#include "graph.hpp"
#include "topological_sort.hpp"

namespace m1une {
namespace graph {

struct DagReachability {
    std::vector<utilities::DynamicBitset> reachable_vertices;
    std::vector<int> topological_order;

    int size() const {
        return int(reachable_vertices.size());
    }

    bool reachable(int from, int to) const {
        assert(0 <= from && from < size());
        assert(0 <= to && to < size());
        return reachable_vertices[from].test(to);
    }
};

template <class T>
std::optional<DagReachability> dag_reachability(const Graph<T>& g) {
    const int n = g.size();
    auto order = topological_sort(g);
    if (!order) return std::nullopt;

    DagReachability result;
    result.reachable_vertices.assign(n, utilities::DynamicBitset(n));
    result.topological_order = *order;
    for (int i = n - 1; i >= 0; i--) {
        int v = (*order)[i];
        result.reachable_vertices[v].set(v);
        for (const auto& e : g[v]) {
            if (e.alive) result.reachable_vertices[v] |= result.reachable_vertices[e.to];
        }
    }
    return result;
}

template <class T>
struct DagTransitiveReductionResult {
    Graph<T> graph;
    std::vector<int> original_edge_ids;
};

template <class T>
std::optional<DagTransitiveReductionResult<T>> dag_transitive_reduction(const Graph<T>& g) {
    auto reachability = dag_reachability(g);
    if (!reachability) return std::nullopt;

    const int n = g.size();
    std::vector<int> position(n);
    for (int i = 0; i < n; i++) position[reachability->topological_order[i]] = i;

    std::vector<char> kept(g.edge_count(), false);
    for (int v = 0; v < n; v++) {
        std::vector<const Edge<T>*> outgoing;
        outgoing.reserve(g[v].size());
        for (const auto& e : g[v]) {
            if (e.alive) outgoing.push_back(&e);
        }
        std::stable_sort(outgoing.begin(), outgoing.end(), [&](const auto* lhs, const auto* rhs) {
            return position[lhs->to] < position[rhs->to];
        });

        utilities::DynamicBitset covered(n);
        for (const auto* e : outgoing) {
            if (covered.test(e->to)) continue;
            kept[e->id] = true;
            covered |= reachability->reachable_vertices[e->to];
        }
    }

    DagTransitiveReductionResult<T> result;
    result.graph = Graph<T>(n);
    for (int v = 0; v < n; v++) {
        for (const auto& e : g[v]) {
            if (!e.alive || !kept[e.id]) continue;
            result.graph.add_directed_edge(e.from, e.to, e.cost);
            result.original_edge_ids.push_back(e.id);
        }
    }
    return result;
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_DAG_REACHABILITY_HPP

#line 1 "graph/dag_reachability.hpp"



#include <algorithm>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>

#line 1 "utilities/dynamic_bitset.hpp"



#line 6 "utilities/dynamic_bitset.hpp"
#include <cstddef>
#include <cstdint>
#line 9 "utilities/dynamic_bitset.hpp"

namespace m1une {
namespace utilities {

struct DynamicBitset {
   private:
    static constexpr int BITS_PER_BLOCK = 64;
    static constexpr uint64_t FULL_BLOCK = ~uint64_t{0};

    int _n;
    std::vector<uint64_t> blocks;

    static int block_count(int n) {
        assert(n >= 0);
        return (n + BITS_PER_BLOCK - 1) >> 6;
    }

    uint64_t tail_mask() const {
        const int rem = _n & (BITS_PER_BLOCK - 1);
        return rem == 0 ? FULL_BLOCK : ((uint64_t{1} << rem) - 1);
    }

    // Keep unused bits in the last block equal to zero.
    void clean() {
        if (!blocks.empty()) blocks.back() &= tail_mask();
    }

   public:
    DynamicBitset() : _n(0), blocks() {}

    explicit DynamicBitset(int n, bool val = false) : _n(n), blocks(block_count(n), val ? FULL_BLOCK : 0) {
        if (val) clean();
    }

    // Returns the logical number of bits.
    int size() const {
        return _n;
    }

    // Returns whether the bit at index i is set.
    bool test(int i) const {
        assert(0 <= i && i < _n);
        return (blocks[i >> 6] >> (i & (BITS_PER_BLOCK - 1))) & 1;
    }

    // Sets the bit at index i to true.
    void set(int i) {
        assert(0 <= i && i < _n);
        blocks[i >> 6] |= uint64_t{1} << (i & (BITS_PER_BLOCK - 1));
    }

    // Sets all bits to true.
    void set() {
        std::fill(blocks.begin(), blocks.end(), FULL_BLOCK);
        clean();
    }

    // Sets the bit at index i to false.
    void reset(int i) {
        assert(0 <= i && i < _n);
        blocks[i >> 6] &= ~(uint64_t{1} << (i & (BITS_PER_BLOCK - 1)));
    }

    // Sets all bits to false.
    void reset() {
        std::fill(blocks.begin(), blocks.end(), uint64_t{0});
    }

    // Flips the bit at index i.
    void flip(int i) {
        assert(0 <= i && i < _n);
        blocks[i >> 6] ^= uint64_t{1} << (i & (BITS_PER_BLOCK - 1));
    }

    // Flips all bits.
    void flip() {
        for (uint64_t& block : blocks) block = ~block;
        clean();
    }

    // Returns the number of set bits.
    int popcount() const {
        int res = 0;
        for (uint64_t block : blocks) res += __builtin_popcountll(block);
        return res;
    }

    // Returns the index of the least significant set bit, or -1 if no bit is set.
    int lowbit() const {
        const int m = static_cast<int>(blocks.size());
        for (int i = 0; i < m; ++i) {
            if (blocks[i] != 0) return (i << 6) + __builtin_ctzll(blocks[i]);
        }
        return -1;
    }

    // Returns the index of the most significant set bit, or -1 if no bit is set.
    int topbit() const {
        for (int i = static_cast<int>(blocks.size()) - 1; i >= 0; --i) {
            if (blocks[i] != 0) return (i << 6) + (BITS_PER_BLOCK - 1 - __builtin_clzll(blocks[i]));
        }
        return -1;
    }

    // Returns whether at least one bit is set.
    bool any() const {
        for (uint64_t block : blocks) {
            if (block != 0) return true;
        }
        return false;
    }

    // Returns whether every logical bit is set.
    bool all() const {
        if (_n == 0) return true;

        const int m = static_cast<int>(blocks.size());
        for (int i = 0; i + 1 < m; ++i) {
            if (blocks[i] != FULL_BLOCK) return false;
        }
        return blocks.back() == tail_mask();
    }

    // Returns whether no bit is set.
    bool none() const {
        return !any();
    }

    DynamicBitset& operator&=(const DynamicBitset& other) {
        assert(_n == other._n);
        const std::size_t m = blocks.size();
        for (std::size_t i = 0; i < m; ++i) blocks[i] &= other.blocks[i];
        return *this;
    }

    DynamicBitset& operator|=(const DynamicBitset& other) {
        assert(_n == other._n);
        const std::size_t m = blocks.size();
        for (std::size_t i = 0; i < m; ++i) blocks[i] |= other.blocks[i];
        return *this;
    }

    DynamicBitset& operator^=(const DynamicBitset& other) {
        assert(_n == other._n);
        const std::size_t m = blocks.size();
        for (std::size_t i = 0; i < m; ++i) blocks[i] ^= other.blocks[i];
        return *this;
    }

    DynamicBitset operator~() const {
        DynamicBitset res = *this;
        res.flip();
        return res;
    }

    friend DynamicBitset operator&(DynamicBitset lhs, const DynamicBitset& rhs) {
        lhs &= rhs;
        return lhs;
    }

    friend DynamicBitset operator|(DynamicBitset lhs, const DynamicBitset& rhs) {
        lhs |= rhs;
        return lhs;
    }

    friend DynamicBitset operator^(DynamicBitset lhs, const DynamicBitset& rhs) {
        lhs ^= rhs;
        return lhs;
    }
};

}  // namespace utilities
}  // namespace m1une


#line 1 "graph/graph.hpp"



#include <array>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 1 "graph/topological_sort.hpp"



#line 5 "graph/topological_sort.hpp"
#include <queue>
#line 7 "graph/topological_sort.hpp"

#line 9 "graph/topological_sort.hpp"

namespace m1une {
namespace graph {

template <class T>
std::optional<std::vector<int>> topological_sort(const Graph<T>& g) {
    int n = g.size();
    std::vector<int> indeg(n, 0);
    for (int v = 0; v < n; v++) {
        for (const auto& e : g[v]) {
            if (!e.alive) continue;
            indeg[e.to]++;
        }
    }

    std::queue<int> que;
    for (int v = 0; v < n; v++) {
        if (indeg[v] == 0) que.push(v);
    }

    std::vector<int> order;
    order.reserve(n);
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        order.push_back(v);
        for (const auto& e : g[v]) {
            if (!e.alive) continue;
            indeg[e.to]--;
            if (indeg[e.to] == 0) que.push(e.to);
        }
    }

    if (int(order.size()) != n) return std::nullopt;
    return order;
}

template <class T>
bool is_dag(const Graph<T>& g) {
    return topological_sort(g).has_value();
}

}  // namespace graph
}  // namespace m1une


#line 13 "graph/dag_reachability.hpp"

namespace m1une {
namespace graph {

struct DagReachability {
    std::vector<utilities::DynamicBitset> reachable_vertices;
    std::vector<int> topological_order;

    int size() const {
        return int(reachable_vertices.size());
    }

    bool reachable(int from, int to) const {
        assert(0 <= from && from < size());
        assert(0 <= to && to < size());
        return reachable_vertices[from].test(to);
    }
};

template <class T>
std::optional<DagReachability> dag_reachability(const Graph<T>& g) {
    const int n = g.size();
    auto order = topological_sort(g);
    if (!order) return std::nullopt;

    DagReachability result;
    result.reachable_vertices.assign(n, utilities::DynamicBitset(n));
    result.topological_order = *order;
    for (int i = n - 1; i >= 0; i--) {
        int v = (*order)[i];
        result.reachable_vertices[v].set(v);
        for (const auto& e : g[v]) {
            if (e.alive) result.reachable_vertices[v] |= result.reachable_vertices[e.to];
        }
    }
    return result;
}

template <class T>
struct DagTransitiveReductionResult {
    Graph<T> graph;
    std::vector<int> original_edge_ids;
};

template <class T>
std::optional<DagTransitiveReductionResult<T>> dag_transitive_reduction(const Graph<T>& g) {
    auto reachability = dag_reachability(g);
    if (!reachability) return std::nullopt;

    const int n = g.size();
    std::vector<int> position(n);
    for (int i = 0; i < n; i++) position[reachability->topological_order[i]] = i;

    std::vector<char> kept(g.edge_count(), false);
    for (int v = 0; v < n; v++) {
        std::vector<const Edge<T>*> outgoing;
        outgoing.reserve(g[v].size());
        for (const auto& e : g[v]) {
            if (e.alive) outgoing.push_back(&e);
        }
        std::stable_sort(outgoing.begin(), outgoing.end(), [&](const auto* lhs, const auto* rhs) {
            return position[lhs->to] < position[rhs->to];
        });

        utilities::DynamicBitset covered(n);
        for (const auto* e : outgoing) {
            if (covered.test(e->to)) continue;
            kept[e->id] = true;
            covered |= reachability->reachable_vertices[e->to];
        }
    }

    DagTransitiveReductionResult<T> result;
    result.graph = Graph<T>(n);
    for (int v = 0; v < n; v++) {
        for (const auto& e : g[v]) {
            if (!e.alive || !kept[e.id]) continue;
            result.graph.add_directed_edge(e.from, e.to, e.cost);
            result.original_edge_ids.push_back(e.id);
        }
    }
    return result;
}

}  // namespace graph
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

DAG Reachability and Transitive Reduction
(graph/dag_reachability.hpp)

Overview

Types

Functions

Example

Depends on

Required by

Verified with

Code

DAG Reachability and Transitive Reduction (graph/dag_reachability.hpp)

Overview

Types

Functions

Example

Depends on

Required by

Verified with

Code

DAG Reachability and Transitive Reduction
(graph/dag_reachability.hpp)