m1une's library

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

View on GitHub

:heavy_check_mark: Enumerate Cliques
(graph/enumerate_cliques.hpp)

Overview

enumerate_cliques visits every nonempty clique of a simple graph exactly once. Cliques are reported through a callback, allowing their values to be aggregated without storing every result.

The implementation computes a degeneracy ordering and assigns each clique to its first vertex in that ordering. It then enumerates cliques inside that vertex’s forward neighborhood. This limits the exponential part to the graph’s degeneracy rather than its total vertex count.

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, including edges added with add_directed_edge. Edge costs are ignored and inactive edges are ignored.

Callback

The callback signature is:

callback(const std::vector<int>& clique);

It is invoked exactly once for every nonempty clique, including single-vertex cliques. Vertex and clique order are unspecified. The vector is reused by the enumerator, so copy it if it must remain available after the callback returns. The callback must not mutate the graph.

Function

Function Exact signature Description Complexity
enumerate_cliques template <class T, class Callback> void enumerate_cliques(const Graph<T>& graph, Callback&& callback) Invokes callback once for every nonempty clique without mutating graph. $O(N + M + Md\log N + K(d + F))$ time and $O(N + M + d^2)$ memory

Here, d is the graph degeneracy, K is the number of nonempty cliques, and F is the cost of one callback. Since $d = O(\sqrt M)$ for a simple graph, the bound is practical for sparse graphs whose clique output is manageable.

Example

#include "graph/enumerate_cliques.hpp"
#include "graph/graph.hpp"

#include <cassert>
#include <vector>

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

    int count = 0;
    m1une::graph::enumerate_cliques(
        graph,
        [&](const std::vector<int>&) { count++; }
    );
    assert(count == 7);
}

Depends on

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_ENUMERATE_CLIQUES_HPP
#define M1UNE_GRAPH_ENUMERATE_CLIQUES_HPP 1

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

#include "graph.hpp"

namespace m1une {
namespace graph {

// Invokes callback once for every nonempty clique. The callback receives a
// const reference to a temporary vector that is reused after it returns.
template <class T, class Callback>
void enumerate_cliques(const Graph<T>& graph, Callback&& callback) {
    const int n = graph.size();
    std::vector<std::vector<int>> adjacency(n);
    for (const Edge<T>& edge : graph.edges()) {
        assert(edge.from != edge.to);
        if (edge.from == edge.to) continue;
        adjacency[edge.from].push_back(edge.to);
        adjacency[edge.to].push_back(edge.from);
    }

    for (std::vector<int>& neighbors : adjacency) {
        std::sort(neighbors.begin(), neighbors.end());
#ifndef NDEBUG
        for (int i = 1; i < int(neighbors.size()); i++) {
            assert(neighbors[i - 1] != neighbors[i]);
        }
#endif
        neighbors.erase(
            std::unique(neighbors.begin(), neighbors.end()),
            neighbors.end()
        );
    }

    int maximum_degree = 0;
    std::vector<int> degree(n);
    for (int vertex = 0; vertex < n; vertex++) {
        degree[vertex] = int(adjacency[vertex].size());
        maximum_degree = std::max(maximum_degree, degree[vertex]);
    }

    // Compute a degeneracy ordering in linear time. A clique is assigned to
    // its first vertex in this ordering, and all its other vertices are among
    // that vertex's forward neighbors.
    std::vector<std::vector<int>> bucket(maximum_degree + 1);
    for (int vertex = 0; vertex < n; vertex++) {
        bucket[degree[vertex]].push_back(vertex);
    }
    std::vector<char> active(n, true);
    std::vector<std::vector<int>> forward(n);
    int minimum_degree = 0;
    int degeneracy = 0;
    for (int removed = 0; removed < n; removed++) {
        while (true) {
            while (bucket[minimum_degree].empty()) minimum_degree++;
            int vertex = bucket[minimum_degree].back();
            if (active[vertex] && degree[vertex] == minimum_degree) break;
            bucket[minimum_degree].pop_back();
        }

        int vertex = bucket[minimum_degree].back();
        bucket[minimum_degree].pop_back();
        active[vertex] = false;
        degeneracy = std::max(degeneracy, minimum_degree);
        forward[vertex].reserve(minimum_degree);
        for (int to : adjacency[vertex]) {
            if (!active[to]) continue;
            forward[vertex].push_back(to);
            degree[to]--;
            bucket[degree[to]].push_back(to);
            minimum_degree = std::min(minimum_degree, degree[to]);
        }
    }

    std::vector<int> clique;
    clique.reserve(degeneracy + 1);
    std::vector<std::vector<int>> candidates(degeneracy + 1);
    for (int vertex = 0; vertex < n; vertex++) {
        const std::vector<int>& neighbors = forward[vertex];
        const int neighbor_count = int(neighbors.size());

        clique.clear();
        clique.push_back(vertex);
        callback(std::as_const(clique));
        if (neighbor_count == 0) continue;

        std::vector<char> connected(
            std::size_t(neighbor_count) * neighbor_count,
            false
        );
        for (int first = 0; first < neighbor_count; first++) {
            for (int second = first + 1; second < neighbor_count; second++) {
                bool adjacent = std::binary_search(
                    adjacency[neighbors[first]].begin(),
                    adjacency[neighbors[first]].end(),
                    neighbors[second]
                );
                connected[std::size_t(first) * neighbor_count + second] =
                    adjacent;
                connected[std::size_t(second) * neighbor_count + first] =
                    adjacent;
            }
        }

        candidates[0].resize(neighbor_count);
        for (int i = 0; i < neighbor_count; i++) candidates[0][i] = i;
        auto enumerate = [&](auto&& self, int depth) -> void {
            const std::vector<int>& current = candidates[depth];
            for (int position = 0; position < int(current.size()); position++) {
                int chosen = current[position];
                clique.push_back(neighbors[chosen]);
                callback(std::as_const(clique));

                std::vector<int>& next = candidates[depth + 1];
                next.clear();
                for (int next_position = position + 1;
                     next_position < int(current.size());
                     next_position++) {
                    int candidate = current[next_position];
                    if (connected[
                            std::size_t(chosen) * neighbor_count + candidate
                        ]) {
                        next.push_back(candidate);
                    }
                }
                if (!next.empty()) self(self, depth + 1);
                clique.pop_back();
            }
        };
        enumerate(enumerate, 0);
    }
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_ENUMERATE_CLIQUES_HPP
#line 1 "graph/enumerate_cliques.hpp"



#include <algorithm>
#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 10 "graph/enumerate_cliques.hpp"

namespace m1une {
namespace graph {

// Invokes callback once for every nonempty clique. The callback receives a
// const reference to a temporary vector that is reused after it returns.
template <class T, class Callback>
void enumerate_cliques(const Graph<T>& graph, Callback&& callback) {
    const int n = graph.size();
    std::vector<std::vector<int>> adjacency(n);
    for (const Edge<T>& edge : graph.edges()) {
        assert(edge.from != edge.to);
        if (edge.from == edge.to) continue;
        adjacency[edge.from].push_back(edge.to);
        adjacency[edge.to].push_back(edge.from);
    }

    for (std::vector<int>& neighbors : adjacency) {
        std::sort(neighbors.begin(), neighbors.end());
#ifndef NDEBUG
        for (int i = 1; i < int(neighbors.size()); i++) {
            assert(neighbors[i - 1] != neighbors[i]);
        }
#endif
        neighbors.erase(
            std::unique(neighbors.begin(), neighbors.end()),
            neighbors.end()
        );
    }

    int maximum_degree = 0;
    std::vector<int> degree(n);
    for (int vertex = 0; vertex < n; vertex++) {
        degree[vertex] = int(adjacency[vertex].size());
        maximum_degree = std::max(maximum_degree, degree[vertex]);
    }

    // Compute a degeneracy ordering in linear time. A clique is assigned to
    // its first vertex in this ordering, and all its other vertices are among
    // that vertex's forward neighbors.
    std::vector<std::vector<int>> bucket(maximum_degree + 1);
    for (int vertex = 0; vertex < n; vertex++) {
        bucket[degree[vertex]].push_back(vertex);
    }
    std::vector<char> active(n, true);
    std::vector<std::vector<int>> forward(n);
    int minimum_degree = 0;
    int degeneracy = 0;
    for (int removed = 0; removed < n; removed++) {
        while (true) {
            while (bucket[minimum_degree].empty()) minimum_degree++;
            int vertex = bucket[minimum_degree].back();
            if (active[vertex] && degree[vertex] == minimum_degree) break;
            bucket[minimum_degree].pop_back();
        }

        int vertex = bucket[minimum_degree].back();
        bucket[minimum_degree].pop_back();
        active[vertex] = false;
        degeneracy = std::max(degeneracy, minimum_degree);
        forward[vertex].reserve(minimum_degree);
        for (int to : adjacency[vertex]) {
            if (!active[to]) continue;
            forward[vertex].push_back(to);
            degree[to]--;
            bucket[degree[to]].push_back(to);
            minimum_degree = std::min(minimum_degree, degree[to]);
        }
    }

    std::vector<int> clique;
    clique.reserve(degeneracy + 1);
    std::vector<std::vector<int>> candidates(degeneracy + 1);
    for (int vertex = 0; vertex < n; vertex++) {
        const std::vector<int>& neighbors = forward[vertex];
        const int neighbor_count = int(neighbors.size());

        clique.clear();
        clique.push_back(vertex);
        callback(std::as_const(clique));
        if (neighbor_count == 0) continue;

        std::vector<char> connected(
            std::size_t(neighbor_count) * neighbor_count,
            false
        );
        for (int first = 0; first < neighbor_count; first++) {
            for (int second = first + 1; second < neighbor_count; second++) {
                bool adjacent = std::binary_search(
                    adjacency[neighbors[first]].begin(),
                    adjacency[neighbors[first]].end(),
                    neighbors[second]
                );
                connected[std::size_t(first) * neighbor_count + second] =
                    adjacent;
                connected[std::size_t(second) * neighbor_count + first] =
                    adjacent;
            }
        }

        candidates[0].resize(neighbor_count);
        for (int i = 0; i < neighbor_count; i++) candidates[0][i] = i;
        auto enumerate = [&](auto&& self, int depth) -> void {
            const std::vector<int>& current = candidates[depth];
            for (int position = 0; position < int(current.size()); position++) {
                int chosen = current[position];
                clique.push_back(neighbors[chosen]);
                callback(std::as_const(clique));

                std::vector<int>& next = candidates[depth + 1];
                next.clear();
                for (int next_position = position + 1;
                     next_position < int(current.size());
                     next_position++) {
                    int candidate = current[next_position];
                    if (connected[
                            std::size_t(chosen) * neighbor_count + candidate
                        ]) {
                        next.push_back(candidate);
                    }
                }
                if (!next.empty()) self(self, depth + 1);
                clique.pop_back();
            }
        };
        enumerate(enumerate, 0);
    }
}

}  // namespace graph
}  // namespace m1une
Back to top page