任意の 2 つの同型グラフが同じ値にハッシュされるように、有向非巡回グラフをハッシュ値に変換するにはどうすればよいですか? 2 つの同形グラフが異なる値にハッシュされることは許容されますが、望ましくありません。これは、以下のコードで実行したことです。グラフの頂点の数は最大で 11 であると想定できます。
特に Python コードに興味があります。
これが私がしたことです。self.ltがノードから子孫 (子ではない!) へのマッピングである場合、変更されたトポロジカル ソートに従ってノードのラベルを変更します (可能であれば、より多くの子孫を持つ要素を最初に並べることを好みます)。次に、ソートされた辞書をハッシュします。一部の同形グラフは、特にノード数が増えると、異なる値にハッシュされます。
ユースケースを動機付けるために、すべてのコードを含めました。7 つの数値の中央値を見つけるために必要な比較の回数を計算しています。同形グラフが同じ値にハッシュされるほど、やり直す必要のある作業は少なくなります。最初に大きな接続コンポーネントを配置することを検討しましたが、それをすばやく行う方法がわかりませんでした。
from tools.decorator import memoized # A standard memoization decorator
class Graph:
def __init__(self, n):
self.lt = {i: set() for i in range(n)}
def compared(self, i, j):
return j in self.lt[i] or i in self.lt[j]
def withedge(self, i, j):
retval = Graph(len(self.lt))
implied_lt = self.lt[j] | set([j])
for (s, lt_s), (k, lt_k) in zip(self.lt.items(),
retval.lt.items()):
lt_k |= lt_s
if i in lt_k or k == i:
lt_k |= implied_lt
return retval.toposort()
def toposort(self):
mapping = {}
while len(mapping) < len(self.lt):
for i, lt_i in self.lt.items():
if i in mapping:
continue
if any(i in lt_j or len(lt_i) < len(lt_j)
for j, lt_j in self.lt.items()
if j not in mapping):
continue
mapping[i] = len(mapping)
retval = Graph(0)
for i, lt_i in self.lt.items():
retval.lt[mapping[i]] = {mapping[j]
for j in lt_i}
return retval
def median_known(self):
n = len(self.lt)
for i, lt_i in self.lt.items():
if len(lt_i) != n // 2:
continue
if sum(1
for j, lt_j in self.lt.items()
if i in lt_j) == n // 2:
return True
return False
def __repr__(self):
return("[{}]".format(", ".join("{}: {{{}}}".format(
i,
", ".join(str(x) for x in lt_i))
for i, lt_i in self.lt.items())))
def hashkey(self):
return tuple(sorted({k: tuple(sorted(v))
for k, v in self.lt.items()}.items()))
def __hash__(self):
return hash(self.hashkey())
def __eq__(self, other):
return self.hashkey() == other.hashkey()
@memoized
def mincomps(g):
print("Calculating:", g)
if g.median_known():
return 0
nodes = g.lt.keys()
return 1 + min(max(mincomps(g.withedge(i, j)),
mincomps(g.withedge(j, i)))
for i in nodes
for j in nodes
if j > i and not g.compared(i, j))
g = Graph(7)
print(mincomps(g))