木のハッシュ (木の同型判定)
(Graph/Tree/treehash.py)

• View this file on GitHub
• Last update: 2021-05-05 16:08:04+09:00

概要

木のハッシュを求めるアルゴリズム。

使い方

treehash(tree: Sequence[Iterable[int]], root: Union[int, None] = None) -> Tuple[int]
木 tree のハッシュ値を返す。ハッシュ値は、木の中心の数と同じサイズのタプルとなる。root を指定すると根付き木に対するハッシュとなる。計算量 $O(V \log V)$

参考

• https://logic.pdmi.ras.ru/~smal/files/smal_jass08_slides.pdf
• https://logic.pdmi.ras.ru/~smal/files/smal_jass08.pdf
• 木の同型性判定のお話 - kazu0x17’s diary

Depends on

• 木の重心 (Graph/Tree/centroid.py)
• 木上のトポロジカルソート (Graph/Tree/topological_sorted.py)

Verified with

• TestCase/AOJ/2821.test.py

Code

from Graph.Tree.centroid import centroid
from Graph.Tree.topological_sorted import topological_sorted


MAX = 0
HASHMAP = {}


def treehash(tree, root=None):
    global MAX
    n = len(tree)
    if root is None:
        hs = centroid(tree)
    else:
        hs = [root]
    res = []
    for rt in hs:
        tp_order, _ = topological_sorted(tree, rt)
        visited = [-1] * n
        for v in tp_order[::-1]:
            tmp = []
            for nxt_v in tree[v]:
                if visited[nxt_v] == -1:
                    continue
                else:
                    tmp.append(visited[nxt_v])
            tmp = tuple(sorted(tmp))
            if tmp not in HASHMAP:
                HASHMAP[tmp] = MAX
                MAX += 1
            visited[v] = HASHMAP[tmp]
        res.append(visited[rt])
    res = tuple(sorted(res))
    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page