Chordal Graph Recognition
(graph/chordal_graph_recognition.hpp)

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

Overview

A graph is chordal when every cycle of length at least four has a chord. Equivalently, it has a perfect elimination ordering: for each vertex, its neighbors appearing later in the ordering form a clique.

chordal_graph_recognition recognizes a chordal graph and returns a certificate in either case. A chordal graph gets a perfect elimination ordering; a non-chordal graph gets an induced cycle of length at least four.

The implementation uses bucketed maximum-cardinality search, verifies the resulting ordering, and performs one BFS only when it must construct a cycle.

Returned Certificates

Perfect Elimination Ordering

Let order be a permutation of all vertices. For each vertex order[i], look at only its neighbors in the suffix order[i + 1], order[i + 2], ..., order[N - 1]. The ordering is a perfect elimination ordering when those later neighbors are pairwise adjacent, and therefore form a clique, for every i.

The name comes from eliminating the vertices from left to right. Removing order[i] cannot create a missing connection between its remaining neighbors, because those neighbors already form a clique.

For example, consider the path 0 - 1 - 2. The ordering [0, 2, 1] is a perfect elimination ordering:

The only later neighbor of 0 is 1.
The only later neighbor of 2 is 1.
Vertex 1 has no later neighbors.

A set with zero or one vertex is always a clique, so all three conditions hold. Every chordal graph has such an ordering, and every graph with such an ordering is chordal.

Induced Cycle

An induced cycle is a sequence of distinct vertices cycle[0], cycle[1], ..., cycle[K - 1], with K >= 4, satisfying both of the following:

Consecutive vertices are adjacent, including cycle[K - 1] and cycle[0].
No other pair of vertices in the sequence is adjacent.

The second condition says that the cycle has no chord: an edge joining two non-consecutive cycle vertices. For example, the four-cycle 0 - 1 - 2 - 3 - 0 is induced if neither 0 - 2 nor 1 - 3 is an edge. Adding either edge gives the cycle a chord, so that four-vertex sequence is no longer an induced cycle.

An induced cycle of length at least four is a direct certificate that the graph is not chordal. The returned vector does not repeat its first vertex at the end; the closing edge from cycle.back() to cycle.front() is implicit.

Graph Interpretation

Every active edge of Graph<T> is treated as an undirected edge, regardless of how it was inserted. Self-loops are ignored. Parallel edges are treated as one edge, so they do not change the result.

Edge costs are ignored. The graph is not mutated.

API

struct ChordalGraphResult {
    bool is_chordal;
    std::vector<int> perfect_elimination_order;
    std::vector<int> induced_cycle;
};

template <class T>
ChordalGraphResult chordal_graph_recognition(const Graph<T>& graph);

template <class T>
bool is_chordal(const Graph<T>& graph);

Member or function	Description	Complexity
`is_chordal`	Whether the input graph is chordal.	–
`perfect_elimination_order`	A permutation in which the later neighbors of every vertex form a clique when the graph is chordal; empty otherwise.	–
`induced_cycle`	Distinct vertices of a chordless cycle in cyclic order when the graph is not chordal; empty otherwise. The first vertex is not repeated.	–
`chordal_graph_recognition(graph)`	Recognizes the graph and constructs the appropriate certificate.	$O(N+M)$ time and memory
`is_chordal(graph)`	Returns only whether the graph is chordal.	$O(N+M)$ time and memory

Example

#include "graph/chordal_graph_recognition.hpp"
#include "graph/graph.hpp"

#include <iostream>

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

    auto result = m1une::graph::chordal_graph_recognition(graph);
    std::cout << result.is_chordal << "\n";         // 0
    std::cout << result.induced_cycle.size() << "\n";  // 4
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_CHORDAL_GRAPH_RECOGNITION_HPP
#define M1UNE_GRAPH_CHORDAL_GRAPH_RECOGNITION_HPP 1

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

#include "graph.hpp"

namespace m1une {
namespace graph {

struct ChordalGraphResult {
    bool is_chordal;
    std::vector<int> perfect_elimination_order;
    std::vector<int> induced_cycle;
};

namespace internal {

class MaximumCardinalitySearch {
    std::vector<int> _head;
    std::vector<int> _next;
    std::vector<int> _previous;
    std::vector<int> _weight;

    void erase(int vertex) {
        const int weight = _weight[vertex];
        if (_previous[vertex] == -1) {
            _head[weight] = _next[vertex];
        } else {
            _next[_previous[vertex]] = _next[vertex];
        }
        if (_next[vertex] != -1) _previous[_next[vertex]] = _previous[vertex];
    }

    void insert(int vertex) {
        const int weight = _weight[vertex];
        _previous[vertex] = -1;
        _next[vertex] = _head[weight];
        if (_head[weight] != -1) _previous[_head[weight]] = vertex;
        _head[weight] = vertex;
    }

   public:
    explicit MaximumCardinalitySearch(int size)
        : _head(size + 1, -1),
          _next(size, -1),
          _previous(size, -1),
          _weight(size, 0) {
        for (int vertex = 0; vertex < size; vertex++) insert(vertex);
    }

    std::vector<int> run(const std::vector<std::vector<int>>& adjacency) {
        const int size = int(adjacency.size());
        std::vector<int> order;
        order.reserve(size);
        std::vector<char> selected(size, false);
        std::vector<int> seen_neighbor(size, -1);
        int maximum_weight = 0;

        while (int(order.size()) < size) {
            while (_head[maximum_weight] == -1) maximum_weight--;
            const int vertex = _head[maximum_weight];
            erase(vertex);
            selected[vertex] = true;
            order.push_back(vertex);

            for (int to : adjacency[vertex]) {
                if (to == vertex || selected[to] || seen_neighbor[to] == vertex) continue;
                seen_neighbor[to] = vertex;
                erase(to);
                _weight[to]++;
                insert(to);
                maximum_weight = std::max(maximum_weight, _weight[to]);
            }
        }
        return order;
    }
};

inline std::vector<int> chordless_cycle(
    const std::vector<std::vector<int>>& adjacency, int vertex, int first,
    int second
) {
    const int size = int(adjacency.size());
    std::vector<char> forbidden(size, false);
    for (int to : adjacency[vertex]) forbidden[to] = true;
    forbidden[vertex] = true;
    forbidden[first] = false;
    forbidden[second] = false;

    std::vector<int> parent(size, -1);
    std::queue<int> queue;
    parent[first] = first;
    queue.push(first);
    while (!queue.empty() && parent[second] == -1) {
        const int current = queue.front();
        queue.pop();
        for (int to : adjacency[current]) {
            if (forbidden[to] || parent[to] != -1) continue;
            parent[to] = current;
            queue.push(to);
        }
    }
    assert(parent[second] != -1);

    std::vector<int> path;
    for (int current = second; current != first; current = parent[current]) {
        path.push_back(current);
    }
    path.push_back(first);
    std::reverse(path.begin(), path.end());

    std::vector<int> cycle;
    cycle.reserve(path.size() + 1);
    cycle.push_back(vertex);
    cycle.insert(cycle.end(), path.begin(), path.end());
    return cycle;
}

}  // namespace internal

// Recognizes a chordal graph. On success, returns a perfect elimination
// ordering; on failure, returns an induced cycle of length at least four.
template <class T>
ChordalGraphResult chordal_graph_recognition(const Graph<T>& graph) {
    const int size = graph.size();
    std::vector<std::vector<int>> adjacency(size);
    for (const Edge<T>& edge : graph.edges()) {
        if (edge.from == edge.to) continue;
        adjacency[edge.from].push_back(edge.to);
        adjacency[edge.to].push_back(edge.from);
    }

    std::vector<int> order = internal::MaximumCardinalitySearch(size).run(adjacency);
    std::vector<int> position(size);
    for (int index = 0; index < size; index++) position[order[index]] = index;

    std::vector<int> parent(size, -1);
    std::vector<std::vector<int>> children(size);
    for (int vertex = 0; vertex < size; vertex++) {
        for (int to : adjacency[vertex]) {
            if (position[to] < position[vertex] &&
                (parent[vertex] == -1 || position[parent[vertex]] < position[to])) {
                parent[vertex] = to;
            }
        }
        if (parent[vertex] != -1) children[parent[vertex]].push_back(vertex);
    }

    std::vector<int> adjacent_stamp(size, -1);
    for (int center = 0; center < size; center++) {
        for (int to : adjacency[center]) adjacent_stamp[to] = center;
        for (int vertex : children[center]) {
            for (int to : adjacency[vertex]) {
                if (position[to] >= position[center] || adjacent_stamp[to] == center) continue;
                return ChordalGraphResult{
                    false,
                    {},
                    internal::chordless_cycle(adjacency, vertex, to, center),
                };
            }
        }
    }

    std::reverse(order.begin(), order.end());
    return ChordalGraphResult{true, std::move(order), {}};
}

template <class T>
bool is_chordal(const Graph<T>& graph) {
    return chordal_graph_recognition(graph).is_chordal;
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_CHORDAL_GRAPH_RECOGNITION_HPP

#line 1 "graph/chordal_graph_recognition.hpp"



#include <algorithm>
#include <cassert>
#include <queue>
#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 11 "graph/chordal_graph_recognition.hpp"

namespace m1une {
namespace graph {

struct ChordalGraphResult {
    bool is_chordal;
    std::vector<int> perfect_elimination_order;
    std::vector<int> induced_cycle;
};

namespace internal {

class MaximumCardinalitySearch {
    std::vector<int> _head;
    std::vector<int> _next;
    std::vector<int> _previous;
    std::vector<int> _weight;

    void erase(int vertex) {
        const int weight = _weight[vertex];
        if (_previous[vertex] == -1) {
            _head[weight] = _next[vertex];
        } else {
            _next[_previous[vertex]] = _next[vertex];
        }
        if (_next[vertex] != -1) _previous[_next[vertex]] = _previous[vertex];
    }

    void insert(int vertex) {
        const int weight = _weight[vertex];
        _previous[vertex] = -1;
        _next[vertex] = _head[weight];
        if (_head[weight] != -1) _previous[_head[weight]] = vertex;
        _head[weight] = vertex;
    }

   public:
    explicit MaximumCardinalitySearch(int size)
        : _head(size + 1, -1),
          _next(size, -1),
          _previous(size, -1),
          _weight(size, 0) {
        for (int vertex = 0; vertex < size; vertex++) insert(vertex);
    }

    std::vector<int> run(const std::vector<std::vector<int>>& adjacency) {
        const int size = int(adjacency.size());
        std::vector<int> order;
        order.reserve(size);
        std::vector<char> selected(size, false);
        std::vector<int> seen_neighbor(size, -1);
        int maximum_weight = 0;

        while (int(order.size()) < size) {
            while (_head[maximum_weight] == -1) maximum_weight--;
            const int vertex = _head[maximum_weight];
            erase(vertex);
            selected[vertex] = true;
            order.push_back(vertex);

            for (int to : adjacency[vertex]) {
                if (to == vertex || selected[to] || seen_neighbor[to] == vertex) continue;
                seen_neighbor[to] = vertex;
                erase(to);
                _weight[to]++;
                insert(to);
                maximum_weight = std::max(maximum_weight, _weight[to]);
            }
        }
        return order;
    }
};

inline std::vector<int> chordless_cycle(
    const std::vector<std::vector<int>>& adjacency, int vertex, int first,
    int second
) {
    const int size = int(adjacency.size());
    std::vector<char> forbidden(size, false);
    for (int to : adjacency[vertex]) forbidden[to] = true;
    forbidden[vertex] = true;
    forbidden[first] = false;
    forbidden[second] = false;

    std::vector<int> parent(size, -1);
    std::queue<int> queue;
    parent[first] = first;
    queue.push(first);
    while (!queue.empty() && parent[second] == -1) {
        const int current = queue.front();
        queue.pop();
        for (int to : adjacency[current]) {
            if (forbidden[to] || parent[to] != -1) continue;
            parent[to] = current;
            queue.push(to);
        }
    }
    assert(parent[second] != -1);

    std::vector<int> path;
    for (int current = second; current != first; current = parent[current]) {
        path.push_back(current);
    }
    path.push_back(first);
    std::reverse(path.begin(), path.end());

    std::vector<int> cycle;
    cycle.reserve(path.size() + 1);
    cycle.push_back(vertex);
    cycle.insert(cycle.end(), path.begin(), path.end());
    return cycle;
}

}  // namespace internal

// Recognizes a chordal graph. On success, returns a perfect elimination
// ordering; on failure, returns an induced cycle of length at least four.
template <class T>
ChordalGraphResult chordal_graph_recognition(const Graph<T>& graph) {
    const int size = graph.size();
    std::vector<std::vector<int>> adjacency(size);
    for (const Edge<T>& edge : graph.edges()) {
        if (edge.from == edge.to) continue;
        adjacency[edge.from].push_back(edge.to);
        adjacency[edge.to].push_back(edge.from);
    }

    std::vector<int> order = internal::MaximumCardinalitySearch(size).run(adjacency);
    std::vector<int> position(size);
    for (int index = 0; index < size; index++) position[order[index]] = index;

    std::vector<int> parent(size, -1);
    std::vector<std::vector<int>> children(size);
    for (int vertex = 0; vertex < size; vertex++) {
        for (int to : adjacency[vertex]) {
            if (position[to] < position[vertex] &&
                (parent[vertex] == -1 || position[parent[vertex]] < position[to])) {
                parent[vertex] = to;
            }
        }
        if (parent[vertex] != -1) children[parent[vertex]].push_back(vertex);
    }

    std::vector<int> adjacent_stamp(size, -1);
    for (int center = 0; center < size; center++) {
        for (int to : adjacency[center]) adjacent_stamp[to] = center;
        for (int vertex : children[center]) {
            for (int to : adjacency[vertex]) {
                if (position[to] >= position[center] || adjacent_stamp[to] == center) continue;
                return ChordalGraphResult{
                    false,
                    {},
                    internal::chordless_cycle(adjacency, vertex, to, center),
                };
            }
        }
    }

    std::reverse(order.begin(), order.end());
    return ChordalGraphResult{true, std::move(order), {}};
}

template <class T>
bool is_chordal(const Graph<T>& graph) {
    return chordal_graph_recognition(graph).is_chordal;
}

}  // namespace graph
}  // namespace m1une

m1une's library

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

Chordal Graph Recognition
(graph/chordal_graph_recognition.hpp)

Overview

Returned Certificates

Perfect Elimination Ordering

Induced Cycle

Graph Interpretation

API

Example

Depends on

Required by

Verified with

Code

Chordal Graph Recognition (graph/chordal_graph_recognition.hpp)

Overview

Returned Certificates

Perfect Elimination Ordering

Induced Cycle

Graph Interpretation

API

Example

Depends on

Required by

Verified with

Code

Chordal Graph Recognition
(graph/chordal_graph_recognition.hpp)