Lexicographic BFS
(graph/lex_bfs.hpp)

View this file on GitHub
Last update: 2024-01-08 13:32:33+09:00
Include: #include "graph/lex_bfs.hpp"

Description

辞書順最小幅優先探索 (Lex-BFS) は，グラフ $G$ の頂点の並べ方 $(v_1,v_2,\dots,v_n)$ であって，以下の性質を持つものである．

各 $i=1,2,\dots,n$ について，集合 $S_i$ を $S_i={j \mid j \lt i, v_j \in N(v_i) }$ と定義する (ここで， $N(v)$ は頂点 $v$ の隣接頂点の集合である)．列 $(S_1,S_2,\dots,S_n)$ は辞書順の昇順に並んでいる．

Partition refinement を用いて線形時間で実行できる．

Operations

vector<int> lex_bfs(vector<vector<int>> G)
- $G$ の頂点を Lex-BFS 順に並べたリストを返す
- 時間計算量: $O((n+m)\log n)$

Note

Partition refinement の実装をサボって log をつけているので，この実装でも時間計算量に log がついている．

Lex-BFS はいくつかのグラフクラスの認識のサブルーチンとして用いられる．

chordal graph
- Chordal Graph Recognition を参照
- 任意の長さ $4$ 以上のサイクルが弧 (chord) を持つグラフ
- Perfect Elimination Ordering を持つ (参考文献参照)
- Lex-BFS の逆順が PEO になる
cograph
- よくわかっていないが，参考文献 (hos さんのスライド) には色々な応用例が載っている

Reference

Depends on

Partition Refinement (data-structure/partition_refinement.hpp)

Required by

Chordal Graph Recognition (graph/chordal_graph_recognition.hpp)

Verified with

test/yosupo/chordal_graph_recognition.test.cpp

Code

#pragma once
#include <set>
#include <vector>

#include "../data-structure/partition_refinement.hpp"

std::vector<int> lex_bfs(const std::vector<std::vector<int>>& G) {
    const int n = G.size();
    PartitionRefinement pr(n);
    std::vector<int> prv(1, -1), nxt(1, -1);
    std::vector<int> ord;
    int k = 0;
    for (int i = 0; i < n; ++i) {
        while (pr.size(k) == 0) {
            k = nxt[k];
        }
        int x = pr.member(k);
        ord.push_back(x);
        pr.erase(x);
        std::vector<int> pivot;
        std::set<int> neighbor;
        for (int y : G[x]) {
            if (pr.contains(y)) {
                pivot.push_back(y);
                neighbor.insert(y);
            }
        }
        for (auto [s, t] : pr.refine(pivot)) {
            if ((int)prv.size() <= t) {
                prv.resize(t + 1, -1);
                nxt.resize(t + 1, -1);
            }
            if (neighbor.contains(pr.member(s))) {
                if (nxt[s] >= 0) prv[nxt[s]] = t;
                nxt[t] = nxt[s];
                prv[t] = s;
                nxt[s] = t;
            } else {
                if (prv[s] >= 0) nxt[prv[s]] = t;
                prv[t] = prv[s];
                prv[s] = t;
                nxt[t] = s;
            }
        }
        if (prv[k] != -1) k = prv[k];
    }
    return ord;
}

#line 2 "graph/lex_bfs.hpp"
#include <set>
#include <vector>

#line 2 "data-structure/partition_refinement.hpp"
#include <algorithm>
#include <cassert>
#include <map>
#line 7 "data-structure/partition_refinement.hpp"

class PartitionRefinement {
   public:
    PartitionRefinement() = default;
    explicit PartitionRefinement(int n) : sets(1), cls(n, 0) {
        for (int i = 0; i < n; ++i) sets[0].insert(i);
    }

    int find(int x) const { return cls[x]; }

    bool same(int x, int y) const {
        int cx = find(x), cy = find(y);
        return cx != -1 && cy != -1 && cx == cy;
    }

    bool contains(int x) const { return cls[x] != -1; }

    void erase(int x) {
        if (contains(x)) {
            sets[cls[x]].erase(x);
            cls[x] = -1;
        }
    }

    int size(int i) const { return sets[i].size(); }

    int member(int i) const {
        assert(0 <= i && i < (int)sets.size());
        return *sets[i].begin();
    }

    std::vector<int> members(int i) const {
        assert(0 <= i && i < (int)sets.size());
        return std::vector<int>(sets[i].begin(), sets[i].end());
    }

    std::vector<std::pair<int, int>> refine(const std::vector<int>& pivot) {
        std::map<int, std::vector<int>> split;
        for (auto x : pivot) {
            if (!contains(x)) continue;
            int i = cls[x];
            split[i].push_back(x);
            sets[i].erase(x);
        }
        std::vector<std::pair<int, int>> updated;
        for (auto& [i, s] : split) {
            int ni = sets.size();
            sets.emplace_back(s.begin(), s.end());
            if (sets[i].size() < sets[ni].size()) {
                std::swap(sets[i], sets[ni]);
            }
            if (sets[ni].empty()) {
                sets.pop_back();
                continue;
            }
            for (auto x : sets[ni]) {
                cls[x] = ni;
            }
            updated.push_back({i, ni});
        }
        return updated;
    }

   private:
    std::vector<std::set<int>> sets;
    std::vector<int> cls;
};
#line 6 "graph/lex_bfs.hpp"

std::vector<int> lex_bfs(const std::vector<std::vector<int>>& G) {
    const int n = G.size();
    PartitionRefinement pr(n);
    std::vector<int> prv(1, -1), nxt(1, -1);
    std::vector<int> ord;
    int k = 0;
    for (int i = 0; i < n; ++i) {
        while (pr.size(k) == 0) {
            k = nxt[k];
        }
        int x = pr.member(k);
        ord.push_back(x);
        pr.erase(x);
        std::vector<int> pivot;
        std::set<int> neighbor;
        for (int y : G[x]) {
            if (pr.contains(y)) {
                pivot.push_back(y);
                neighbor.insert(y);
            }
        }
        for (auto [s, t] : pr.refine(pivot)) {
            if ((int)prv.size() <= t) {
                prv.resize(t + 1, -1);
                nxt.resize(t + 1, -1);
            }
            if (neighbor.contains(pr.member(s))) {
                if (nxt[s] >= 0) prv[nxt[s]] = t;
                nxt[t] = nxt[s];
                prv[t] = s;
                nxt[s] = t;
            } else {
                if (prv[s] >= 0) nxt[prv[s]] = t;
                prv[t] = prv[s];
                prv[s] = t;
                nxt[t] = s;
            }
        }
        if (prv[k] != -1) k = prv[k];
    }
    return ord;
}

Lexicographic BFS (graph/lex_bfs.hpp)