如何将有向无环图转换为哈希值，使得任意两个同构图哈希到相同的值？在下面的代码中，默认情况下两个同构图会哈希到不同的值，这是可以接受但不理想的。我们可以假设图中顶点的数量最多为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))
P或NP（假设NP != P），对吧？我不知道有什么比nauty（http://cs.anu.edu.au/~bdm/nauty/）更好的正确方法。我记得几年前有人证明GI属于`P`（作者还包括了一个`O(n^5)`的算法），但这个证明是有缺陷的，我不确定它是否最终被发表了。 - mmgp