Tree Isomorphism
(tree/tree_isomorphism.hpp)

• View this file on GitHub
• Last update: 2024-01-07 23:25:49+09:00
• Include: #include "tree/tree_isomorphism.hpp"

Description

同型な木に同一のラベルを付与するアルゴリズム．

Operations

• TreeHasher
  • 確率的だが高速．ハッシュを用いている．
  • long long hash_all(vector<vector<int>> G, int root)
    • 木 $G$ の隣接リストが与えられたとき，$G$ のハッシュを計算する．root が与えられた場合はそれを根とする．そうでない場合は，直径の中心を根とする．直径の中心が複数ある場合は，ハッシュ値が小さくなる方を返す
    • 時間計算量: $O(n)$
  • vector<long long> hash_subtrees(vector<vector<int>> G, int root)
    • 木 $G$ の隣接リストが与えられたとき，$G$ の各部分木のハッシュを計算する．
    • 時間計算量: $O(n)$
• TreeEncoder
  • 決定的だが低速．AHU algorithm を用いている．
  • vector<int> encode(vector<vector<int>> G, int root)
    • 木 $G$ の隣接リストが与えられたとき，$G$ の各部分木のラベルを計算する．
    • 時間計算量: $O(n\log n)$

Reference

• Tree Isomorphism - My Algorithm
• 根付き木のハッシュ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
• Tree isomorphism

Depends on

• Diameter of a Tree (tree/tree_diameter.hpp)

Verified with

• test/yosupo/rooted_tree_isomorphism_classification.ahu.test.cpp
• test/yosupo/rooted_tree_isomorphism_classification.hash.test.cpp

Code

#pragma once
#include <algorithm>
#include <map>
#include <random>
#include <utility>
#include <vector>

#include "tree_diameter.hpp"

class TreeHasher {
   public:
    TreeHasher() : rng(rd()), rand(1, mod - 1) {}

    long long hash_all(const std::vector<std::vector<int>>& G, int root = -1) {
        long long res;
        if (root == -1) {
            auto [d, path] = tree_diameter(G);
            res = dfs_all(G, path[d / 2], -1).first;
            if (d % 2 == 1) {
                res = std::min(res, dfs_all(G, path[d / 2 + 1], -1).first);
            }
        } else {
            res = dfs_all(G, root, -1).first;
        }
        return res;
    }

    std::vector<long long> hash_subtrees(const std::vector<std::vector<int>>& G,
                                         int root) {
        std::vector<long long> hash(G.size());
        dfs_subtrees(G, hash, root, -1);
        return hash;
    }

   private:
    static constexpr long long mod = (1LL << 61) - 1;

    static inline long long add(long long a, long long b) {
        if ((a += b) >= mod) a -= mod;
        return a;
    }

    static inline long long mul(long long a, long long b) {
        __int128_t c = (__int128_t)a * b;
        return add(c >> 61, c & mod);
    }

    std::random_device rd;
    std::mt19937_64 rng;
    std::uniform_int_distribution<long long> rand;
    std::vector<long long> R;

    std::pair<long long, int> dfs_all(const std::vector<std::vector<int>>& G,
                                      int v, int p) {
        int maxd = 0;
        std::vector<long long> hash;
        for (int c : G[v]) {
            if (c != p) {
                auto [h, d] = dfs_all(G, c, v);
                maxd = std::max(maxd, d + 1);
                hash.push_back(h);
            }
        }
        if ((int)R.size() == maxd) {
            R.push_back(rand(rng));
        }
        long long res = 1;
        for (auto h : hash) {
            res = mul(res, add(R[maxd], h));
        }
        return {res, maxd};
    }

    int dfs_subtrees(const std::vector<std::vector<int>>& G,
                     std::vector<long long>& hash, int v, int p) {
        int maxd = 0;
        for (int c : G[v]) {
            if (c != p) {
                maxd = std::max(maxd, dfs_subtrees(G, hash, c, v) + 1);
            }
        }
        if ((int)R.size() == maxd) {
            R.push_back(rand(rng));
        }
        long long res = 1;
        for (int c : G[v]) {
            if (c != p) {
                res = mul(res, add(R[maxd], hash[c]));
            }
        }
        hash[v] = res;
        return maxd;
    }
};

class TreeEncoder {
   public:
    TreeEncoder() { mp[{}] = 0; }

    std::vector<int> encode(const std::vector<std::vector<int>>& G, int root) {
        std::vector<int> val(G.size());
        dfs(G, val, root, -1);
        return val;
    }

   private:
    std::map<std::vector<int>, int> mp;
    std::vector<long long> R;

    void dfs(const std::vector<std::vector<int>>& G, std::vector<int>& val,
             int v, int p) {
        std::vector<int> ch;
        for (int c : G[v]) {
            if (c != p) {
                dfs(G, val, c, v);
                ch.push_back(val[c]);
            }
        }
        std::ranges::sort(ch);
        if (!mp.contains(ch)) {
            mp[ch] = mp.size();
        }
        val[v] = mp[ch];
    }
};

#line 2 "tree/tree_isomorphism.hpp"
#include <algorithm>
#include <map>
#include <random>
#include <utility>
#include <vector>

#line 5 "tree/tree_diameter.hpp"

std::pair<int, std::vector<int>> tree_diameter(
    const std::vector<std::vector<int>>& G) {
    std::vector<int> to(G.size());

    auto dfs = [&](const auto& dfs, int v, int p) -> std::pair<int, int> {
        std::pair<int, int> ret(0, v);
        for (int c : G[v]) {
            if (c == p) continue;
            auto weight = dfs(dfs, c, v);
            ++weight.first;
            if (ret < weight) {
                ret = weight;
                to[v] = c;
            }
        }
        return ret;
    };

    auto p = dfs(dfs, 0, -1);
    auto q = dfs(dfs, p.second, -1);
    std::vector<int> path;
    int v = p.second;
    while (v != q.second) {
        path.push_back(v);
        v = to[v];
    }
    path.push_back(v);
    return {q.first, path};
}

template <typename T>
std::pair<T, std::vector<int>> tree_diameter(
    const std::vector<std::vector<std::pair<int, T>>>& G) {
    std::vector<int> to(G.size());

    auto dfs = [&](const auto& dfs, int v, int p) -> std::pair<T, int> {
        std::pair<T, int> ret(0, v);
        for (auto& [u, w] : G[v]) {
            if (u == p) continue;
            auto weight = dfs(dfs, u, v);
            weight.first += w;
            if (ret < weight) {
                ret = weight;
                to[v] = u;
            }
        }
        return ret;
    };

    auto p = dfs(dfs, 0, -1);
    auto q = dfs(dfs, p.second, -1);
    std::vector<int> path;
    int v = p.second;
    while (v != q.second) {
        path.push_back(v);
        v = to[v];
    }
    path.push_back(v);
    return {q.first, path};
}
#line 9 "tree/tree_isomorphism.hpp"

class TreeHasher {
   public:
    TreeHasher() : rng(rd()), rand(1, mod - 1) {}

    long long hash_all(const std::vector<std::vector<int>>& G, int root = -1) {
        long long res;
        if (root == -1) {
            auto [d, path] = tree_diameter(G);
            res = dfs_all(G, path[d / 2], -1).first;
            if (d % 2 == 1) {
                res = std::min(res, dfs_all(G, path[d / 2 + 1], -1).first);
            }
        } else {
            res = dfs_all(G, root, -1).first;
        }
        return res;
    }

    std::vector<long long> hash_subtrees(const std::vector<std::vector<int>>& G,
                                         int root) {
        std::vector<long long> hash(G.size());
        dfs_subtrees(G, hash, root, -1);
        return hash;
    }

   private:
    static constexpr long long mod = (1LL << 61) - 1;

    static inline long long add(long long a, long long b) {
        if ((a += b) >= mod) a -= mod;
        return a;
    }

    static inline long long mul(long long a, long long b) {
        __int128_t c = (__int128_t)a * b;
        return add(c >> 61, c & mod);
    }

    std::random_device rd;
    std::mt19937_64 rng;
    std::uniform_int_distribution<long long> rand;
    std::vector<long long> R;

    std::pair<long long, int> dfs_all(const std::vector<std::vector<int>>& G,
                                      int v, int p) {
        int maxd = 0;
        std::vector<long long> hash;
        for (int c : G[v]) {
            if (c != p) {
                auto [h, d] = dfs_all(G, c, v);
                maxd = std::max(maxd, d + 1);
                hash.push_back(h);
            }
        }
        if ((int)R.size() == maxd) {
            R.push_back(rand(rng));
        }
        long long res = 1;
        for (auto h : hash) {
            res = mul(res, add(R[maxd], h));
        }
        return {res, maxd};
    }

    int dfs_subtrees(const std::vector<std::vector<int>>& G,
                     std::vector<long long>& hash, int v, int p) {
        int maxd = 0;
        for (int c : G[v]) {
            if (c != p) {
                maxd = std::max(maxd, dfs_subtrees(G, hash, c, v) + 1);
            }
        }
        if ((int)R.size() == maxd) {
            R.push_back(rand(rng));
        }
        long long res = 1;
        for (int c : G[v]) {
            if (c != p) {
                res = mul(res, add(R[maxd], hash[c]));
            }
        }
        hash[v] = res;
        return maxd;
    }
};

class TreeEncoder {
   public:
    TreeEncoder() { mp[{}] = 0; }

    std::vector<int> encode(const std::vector<std::vector<int>>& G, int root) {
        std::vector<int> val(G.size());
        dfs(G, val, root, -1);
        return val;
    }

   private:
    std::map<std::vector<int>, int> mp;
    std::vector<long long> R;

    void dfs(const std::vector<std::vector<int>>& G, std::vector<int>& val,
             int v, int p) {
        std::vector<int> ch;
        for (int c : G[v]) {
            if (c != p) {
                dfs(G, val, c, v);
                ch.push_back(val[c]);
            }
        }
        std::ranges::sort(ch);
        if (!mp.contains(ch)) {
            mp[ch] = mp.size();
        }
        val[v] = mp[ch];
    }
};

Back to top page