Junction Tree (Width 2)
(graph/junction_tree.hpp)

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

Description

与えられた木の木幅が $2$ 以下か判定し，そうならば木幅 $2$ の木分解を構築する．

空間計算量: $O(V + E)$

Operations

• JunctionTreeWidth2(vector<vector<int>> G)
  • グラフ $G$ の隣接リストが与えられたとき，$G$ の木幅 $2$ の木分解を求める．
  • 時間計算量: $O(E\log V)$
• bool is_treewidth_2()
  • 木幅が $2$ 以下か判定する
• vector<Node> get_nodes()
  • $G$ の junction tree のノードを返す．Node は bag メンバと ch メンバを持つ． bag はそのノードに含まれる $G$ の頂点， ch は junction tree におけるそのノードの子である．

Reference

• 木幅が2以下のグラフの木分解と動的計画法 - ei1333の日記
• 離散最適化基礎論 (2016年度後学期) グラフの木分解

Depends on

• Union Find (data-structure/unionfind/union_find.hpp)

Verified with

• test/yosupo/tree_decomposition_width_2.test.cpp

Code

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

#include "../data-structure/unionfind/union_find.hpp"

class JunctionTreeWidth2 {
   public:
    struct Node {
        std::vector<int> bag;
        std::vector<int> ch;
    };

    explicit JunctionTreeWidth2(const std::vector<std::vector<int>>& G)
        : nodes(1) {
        const int n = G.size();

        UnionFind uf(n);
        std::vector<int> deg(n);
        std::vector<std::set<int>> G_st(n);
        for (int v = 0; v < n; ++v) {
            for (int u : G[v]) {
                uf.unite(u, v);
                G_st[v].insert(u);
            }
            deg[v] = G_st[v].size();
        }

        // add dummy edges to make G connected
        std::vector<int> leaders;
        for (int v = 0; v < n; ++v) {
            if (uf.find(v) == v) {
                leaders.push_back(v);
            }
        }
        for (int i = 0; i < (int)leaders.size() - 1; ++i) {
            int u = leaders[i];
            int v = leaders[i + 1];
            G_st[u].insert(v);
            G_st[v].insert(u);
            ++deg[u], ++deg[v];
        }

        // construct a tree decomposition of width 2

        // -2: removed and added to the tree
        // -1: not removed
        // >= 0: removed and not yet added to the tree
        std::vector<int> state(n, -1);
        std::stack<int> st;
        for (int v = 0; v < n; ++v) {
            if (deg[v] <= 2) {
                st.push(v);
            }
        }
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            if (state[v] != -1) continue;
            Node node;
            node.bag.push_back(v);
            int x = -1, y = -1;
            for (int u : G_st[v]) {
                if (state[u] == -1) {
                    (x == -1 ? x : y) = u;
                    node.bag.push_back(u);
                } else if (state[u] > 0) {
                    node.ch.push_back(state[u]);
                    state[u] = -2;
                }
            }

            if (x == -1) {
                // last vertex
            } else if (y == -1) {
                --deg[x];
            } else {
                // add new edge
                if (!G_st[x].contains(y)) {
                    G_st[x].insert(y);
                    G_st[y].insert(x);
                } else {
                    --deg[x], --deg[y];
                }
            }
            for (int u : G_st[v]) {
                if (state[u] == -1 && deg[u] <= 2) {
                    st.push(u);
                }
            }

            deg[v] = 0;
            state[v] = nodes.size();
            nodes.push_back(node);
        }

        if (*std::ranges::max_element(deg) > 0) {
            treewidth_is_2 = false;
            return;
        }

        treewidth_is_2 = true;
        nodes[0].ch.push_back(nodes.size() - 1);
    }

    bool is_treewidth_2() const { return treewidth_is_2; }

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

    std::vector<Node> get_nodes() const { return nodes; }

   private:
    bool treewidth_is_2;
    std::vector<Node> nodes;
};

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

#line 2 "data-structure/unionfind/union_find.hpp"
#include <algorithm>
#line 4 "data-structure/unionfind/union_find.hpp"

class UnionFind {
   public:
    UnionFind() = default;
    explicit UnionFind(int n) : data(n, -1) {}

    int find(int x) {
        if (data[x] < 0) return x;
        return data[x] = find(data[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }

    bool same(int x, int y) { return find(x) == find(y); }

    int size(int x) { return -data[find(x)]; }

   private:
    std::vector<int> data;
};
#line 7 "graph/junction_tree.hpp"

class JunctionTreeWidth2 {
   public:
    struct Node {
        std::vector<int> bag;
        std::vector<int> ch;
    };

    explicit JunctionTreeWidth2(const std::vector<std::vector<int>>& G)
        : nodes(1) {
        const int n = G.size();

        UnionFind uf(n);
        std::vector<int> deg(n);
        std::vector<std::set<int>> G_st(n);
        for (int v = 0; v < n; ++v) {
            for (int u : G[v]) {
                uf.unite(u, v);
                G_st[v].insert(u);
            }
            deg[v] = G_st[v].size();
        }

        // add dummy edges to make G connected
        std::vector<int> leaders;
        for (int v = 0; v < n; ++v) {
            if (uf.find(v) == v) {
                leaders.push_back(v);
            }
        }
        for (int i = 0; i < (int)leaders.size() - 1; ++i) {
            int u = leaders[i];
            int v = leaders[i + 1];
            G_st[u].insert(v);
            G_st[v].insert(u);
            ++deg[u], ++deg[v];
        }

        // construct a tree decomposition of width 2

        // -2: removed and added to the tree
        // -1: not removed
        // >= 0: removed and not yet added to the tree
        std::vector<int> state(n, -1);
        std::stack<int> st;
        for (int v = 0; v < n; ++v) {
            if (deg[v] <= 2) {
                st.push(v);
            }
        }
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            if (state[v] != -1) continue;
            Node node;
            node.bag.push_back(v);
            int x = -1, y = -1;
            for (int u : G_st[v]) {
                if (state[u] == -1) {
                    (x == -1 ? x : y) = u;
                    node.bag.push_back(u);
                } else if (state[u] > 0) {
                    node.ch.push_back(state[u]);
                    state[u] = -2;
                }
            }

            if (x == -1) {
                // last vertex
            } else if (y == -1) {
                --deg[x];
            } else {
                // add new edge
                if (!G_st[x].contains(y)) {
                    G_st[x].insert(y);
                    G_st[y].insert(x);
                } else {
                    --deg[x], --deg[y];
                }
            }
            for (int u : G_st[v]) {
                if (state[u] == -1 && deg[u] <= 2) {
                    st.push(u);
                }
            }

            deg[v] = 0;
            state[v] = nodes.size();
            nodes.push_back(node);
        }

        if (*std::ranges::max_element(deg) > 0) {
            treewidth_is_2 = false;
            return;
        }

        treewidth_is_2 = true;
        nodes[0].ch.push_back(nodes.size() - 1);
    }

    bool is_treewidth_2() const { return treewidth_is_2; }

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

    std::vector<Node> get_nodes() const { return nodes; }

   private:
    bool treewidth_is_2;
    std::vector<Node> nodes;
};

Back to top page