Enumerate Triangles
(graph/enumerate_triangles.hpp)

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

Overview

enumerate_triangles visits every triangle in a simple graph exactly once. Triangles are reported through a callback, so you can count them, aggregate vertex values, or process them online without storing every triple.

The implementation orients edges by (degree, vertex) and intersects the resulting forward neighborhoods. This avoids the cubic scan over all vertex triples.

Graph Requirements

The active edges must form a simple graph: self-loops and parallel edges are not supported. Each active edge is interpreted as undirected, regardless of whether it was inserted with add_edge or add_directed_edge. Edge costs are ignored, and inactive edges are ignored.

Callback

The callback signature is:

callback(int first, int second, int third);

It is invoked exactly once per triangle. The vertex indices are always ordered as first < second < third. The order in which different triangles are visited is unspecified.

Function

Function	Signature	Description	Complexity
enumerate_triangles	template <class T, class Callback> void enumerate_triangles(const Graph<T>& graph, Callback&& callback)	Invokes the callback once for every triangle. Does not mutate graph.	$O(N + M\sqrt M + K F)$ time and $O(N + M)$ memory, where $M$ is the number of active edges, $K$ is the number of triangles, and $F$ is the cost of one callback.

Example

#include "graph/enumerate_triangles.hpp"
#include "graph/graph.hpp"
#include <iostream>
#include <vector>

int main() {
    m1une::graph::Graph<> graph(4);
    graph.add_edge(0, 1);
    graph.add_edge(1, 2);
    graph.add_edge(2, 0);
    graph.add_edge(2, 3);

    std::vector<long long> value = {2, 3, 5, 7};
    long long sum = 0;
    m1une::graph::enumerate_triangles(
        graph,
        [&](int first, int second, int third) {
            sum += value[first] * value[second] * value[third];
        }
    );
    std::cout << sum << "\n";  // 30
}

Depends on

• Graph (graph/graph.hpp)

Required by

• Graph All (graph/all.hpp)
• Undirected Graph Algorithms (graph/undirected.hpp)

Verified with

• verify/graph/cow_game.test.cpp
• verify/graph/enumerate_triangles.test.cpp
• verify/graph/graph_algorithms.test.cpp
• verify/graph/range_edge_graph.test.cpp

Code

#ifndef M1UNE_GRAPH_ENUMERATE_TRIANGLES_HPP
#define M1UNE_GRAPH_ENUMERATE_TRIANGLES_HPP 1

#include <cassert>
#include <utility>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

template <class T, class Callback>
void enumerate_triangles(const Graph<T>& graph, Callback&& callback) {
    const int n = graph.size();
    const std::vector<Edge<T>> edges = graph.edges();

    std::vector<int> degree(n, 0);
    for (const Edge<T>& edge : edges) {
        assert(edge.from != edge.to);
        degree[edge.from]++;
        degree[edge.to]++;
    }

    std::vector<std::vector<int>> oriented(n);
    for (const Edge<T>& edge : edges) {
        int from = edge.from;
        int to = edge.to;
        if (degree[from] > degree[to] ||
            (degree[from] == degree[to] && from > to)) {
            std::swap(from, to);
        }
        oriented[from].push_back(to);
    }

    std::vector<int> marked(n, -1);
    for (int vertex = 0; vertex < n; vertex++) {
        for (int to : oriented[vertex]) marked[to] = vertex;
        for (int middle : oriented[vertex]) {
            for (int to : oriented[middle]) {
                if (marked[to] != vertex) continue;
                int first = vertex;
                int second = middle;
                int third = to;
                if (first > second) std::swap(first, second);
                if (second > third) std::swap(second, third);
                if (first > second) std::swap(first, second);
                callback(first, second, third);
            }
        }
    }
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_ENUMERATE_TRIANGLES_HPP

#line 1 "graph/enumerate_triangles.hpp"



#include <cassert>
#include <utility>
#include <vector>

#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 9 "graph/enumerate_triangles.hpp"

namespace m1une {
namespace graph {

template <class T, class Callback>
void enumerate_triangles(const Graph<T>& graph, Callback&& callback) {
    const int n = graph.size();
    const std::vector<Edge<T>> edges = graph.edges();

    std::vector<int> degree(n, 0);
    for (const Edge<T>& edge : edges) {
        assert(edge.from != edge.to);
        degree[edge.from]++;
        degree[edge.to]++;
    }

    std::vector<std::vector<int>> oriented(n);
    for (const Edge<T>& edge : edges) {
        int from = edge.from;
        int to = edge.to;
        if (degree[from] > degree[to] ||
            (degree[from] == degree[to] && from > to)) {
            std::swap(from, to);
        }
        oriented[from].push_back(to);
    }

    std::vector<int> marked(n, -1);
    for (int vertex = 0; vertex < n; vertex++) {
        for (int to : oriented[vertex]) marked[to] = vertex;
        for (int middle : oriented[vertex]) {
            for (int to : oriented[middle]) {
                if (marked[to] != vertex) continue;
                int first = vertex;
                int second = middle;
                int third = to;
                if (first > second) std::swap(first, second);
                if (second > third) std::swap(second, third);
                if (first > second) std::swap(first, second);
                callback(first, second, third);
            }
        }
    }
}

}  // namespace graph
}  // namespace m1une

Back to top page