Tree Isomorphism
コードについての説明
根つき(無順序)木の同型性判定をハッシュ値の比較によって求めるアルゴリズムである.
この記事の説明にあるとおり深さ $i$ に対応する乱数 $R_i\ (\in [0, mod)$を取った上で,
ある頂点 $v$ でその頂点を根とする部分木の深さが $i$ であるようなものについて $v$ を根とする部分木のハッシュを ($R_i +$ ($v$ の子を根とする部分木のハッシュ値)の積) $\% mod$ で計算すると良い.
根となる頂点には多変数多項式が対応するわけだがここで "$2$ つの木が同型 $\Leftrightarrow$ $2$ つの木の根の多変数多項式が恒等的に等しい" が成り立つ(厳密には一意的に素因数分解が可能であることから従うだろう).
よって結局 Shwartz-Zippel Lemma より乱数を入れて恒等的に等しくないのに等しいと判定する確率は $\mathbb{Z}_p$ 上で $n / p$ 以下であることが言える.
以下の実装では $2$ 種類の mod を用いてハッシュ値を計算している.
兄弟間の順序を区別する順序木の場合は DFS でたどって行きがけに '(', 帰りがけに ')' を配置した括弧列を考えると単射となるのでその文字列比較によって同形性判定を行える.
ちなみにこれは valid な括弧列への全射でもあり,
これから順序木の総数はカタラン数に等しいことも言える.
このような順序木の表現方法は BP 表現と呼ばれていて簡潔データ構造で登場する(他にも DFUDS 表現などがある).
(追記)
hash$(u, p)$: 頂点 $u$ の親が頂点 $p$ であるときの頂点 $u$ を根とする部分木のハッシュ値を取得する構造を 2 つ目のコード(全方位木ハッシュ)として載せた.
(関数)
コンストラクタでは頂点数と計算するハッシュの個数を指定する. 木のハッシュ値はよく衝突するイメージがあるので多くのハッシュ値を計算する方が良さそう.
時間計算量: 木の同型性判定 $\O (n)$ 全方位木ハッシュ 構築 $\O (n \log n)$ クエリ $\O (\log n)$
コード
class tree_hashing {
private:
static vector<vector<unsigned int> > rnum;
static constexpr unsigned int mod = 1000000007;
const int V, RC;
vector<vector<int> > G;
static unsigned int add(const unsigned int x, const unsigned int y){
return (x + y >= mod) ? (x + y - mod) : (x + y);
}
static unsigned int mul(const unsigned int x, const unsigned int y){
return (unsigned long long)x * y % mod;
}
int hash_dfs(const int u, const int p, vector<unsigned int>& res){
int depth = 0;
for(auto v : G[u]){
if(v != p){
vector<unsigned int> vec(RC, 1u);
const int d = hash_dfs(v, u, vec);
depth = max(depth, d + 1);
for(int i = 0; i < RC; ++i) res[i] = mul(res[i], vec[i]);
}
}
for(int i = 0; i < RC; ++i) res[i] = add(res[i], rnum[depth][i]);
return depth;
}
public:
tree_hashing(const int node_size, const int random_count=2)
: V(node_size), RC(random_count), G(V){
mt19937 mt(random_device{}());
uniform_int_distribution<> random(1, mod - 1);
while((int)rnum.size() < V){
vector<unsigned int> vec(RC);
for(int i = 0; i < RC; ++i) vec[i] = random(mt);
rnum.push_back(vec);
}
}
void add_edge(const int a, const int b){
G[a].push_back(b), G[b].push_back(a);
}
vector<unsigned int> hash(const int root=0){
vector<unsigned int> vec(RC, 1u);
return hash_dfs(root, -1, vec), vec;
}
};
vector<vector<unsigned int> > tree_hashing::rnum;
コード(全方位木ハッシュ)
class tree_hashing {
public:
static vector<vector<unsigned int> > rnum;
static constexpr unsigned int mod = 1000000007;
const int V, RC;
vector<vector<int> > G;
vector<vector<vector<unsigned int> > > memo;
vector<vector<pair<int, int> > > table;
static unsigned int add(const unsigned int x, const unsigned int y){
return (x + y >= mod) ? (x + y - mod) : (x + y);
}
static unsigned int mul(const unsigned int x, const unsigned int y){
return (unsigned long long)x * y % mod;
}
pair<int, int> dfs(const int u, const int p, vector<vector<vector<unsigned int> > >& lmul){
const int c = (int)G[u].size();
vector<unsigned int> mult(RC, 1u);
int id = 0;
for(int i = 0; i < c; ++i){
const int v = G[u][i];
if(v != p){
const pair<int, int> val = dfs(v, u, lmul);
if(table[u][0].first < val.first + 1){
swap(table[u][0], table[u][1]);
table[u][0] = {val.first + 1, i};
}else if(table[u][1].first < val.first + 1){
table[u][1] = {val.first + 1, i};
}
for(int j = 0; j < RC; ++j){
mult[j] = mul(mult[j], lmul[u][i + 1][j] = memo[v][val.second][j]);
}
}else{
id = i;
}
}
for(int i = 0; i < RC; ++i) memo[u][id][i] = add(rnum[table[u][0].first][i], mult[i]);
return {table[u][0].first, id};
}
void redfs(const int u, const int p,
vector<vector<vector<unsigned int> > >& lmul, const int d, const int id){
const int c = (int)G[u].size();
vector<vector<unsigned int> > rmul(c + 1, vector<unsigned int>(RC, 1u));
for(int i = 0; i < RC; ++i) lmul[u][0][i] = rmul[c][i] = 1u;
for(int i = c - 1; i >= 0; --i){
if(G[u][i] != p){
for(int j = 0; j < RC; ++j){
rmul[i][j] = mul(rmul[i + 1][j], lmul[u][i + 1][j]);
}
}else{
if(table[u][0].first < d + 1){
swap(table[u][0], table[u][1]);
table[u][0] = {d + 1, i};
}else if(table[u][1].first < d + 1){
table[u][1] = {d + 1, i};
}
for(int j = 0; j < RC; ++j){
rmul[i][j] = mul(rmul[i + 1][j], lmul[u][i + 1][j] = memo[p][id][j]);
}
}
}
for(int i = 0; i < c; ++i){
const int v = G[u][i];
if(v != p){
const int newd = (table[u][0].second == i) ? table[u][1].first : table[u][0].first;
for(int j = 0; j < RC; ++j){
memo[u][i][j] = add(rnum[newd][j], mul(lmul[u][i][j], rmul[i + 1][j]));
}
redfs(v, u, lmul, newd, i);
}
for(int j = 0; j < RC; ++j){
lmul[u][i + 1][j] = mul(lmul[u][i + 1][j], lmul[u][i][j]);
}
}
for(int i = 0; i < RC; ++i){
memo[u][c][i] = add(rnum[table[u][0].first][i], lmul[u][c][i]);
}
}
public:
tree_hashing(const int node_size, const int random_count=4)
: V(node_size), RC(random_count), G(V), memo(V), table(V){
mt19937 mt(random_device{}());
uniform_int_distribution<> random(1, mod - 1);
while((int)rnum.size() < V){
vector<unsigned int> vec(RC);
for(int i = 0; i < RC; ++i) vec[i] = random(mt);
rnum.push_back(vec);
}
for(int i = 0; i < V; ++i){
table[i] = {pair<int, int>(0, -1), pair<int, int>(0, -1)};
}
}
void add_edge(const int a, const int b){
G[a].push_back(b), G[b].push_back(a);
}
void build(){
vector<vector<vector<unsigned int> > > lmul(V);
for(int i = 0; i < V; ++i){
sort(G[i].begin(), G[i].end());
lmul[i] = vector<vector<unsigned int> >(G[i].size() + 1u, vector<unsigned int>(RC));
memo[i] = vector<vector<unsigned int> >(G[i].size() + 1u, vector<unsigned int>(RC));
}
dfs(0, -1, lmul), redfs(0, -1, lmul, 0, 0u);
}
vector<unsigned int> hash(const int u, const int p){
if(p == -1) return memo[u][G[u].size()];
const int id = (int)(lower_bound(G[u].begin(), G[u].end(), p) - G[u].begin());
return memo[u][id];
}
};
vector<vector<unsigned int> > tree_hashing::rnum;
verify 用の問題
CSAcademy : Binary Isomorphism
提出コード
Atcoder : 木、
提出コード(全方位木ハッシュ)