有向无环图的哈希值
我想知道怎么把一个有向无环图（DAG）转变成一个哈希值，这样任何两个同构的图都能得到相同的哈希值。虽然两个同构的图得到不同的哈希值是可以接受的，但我希望它们能得到相同的值，这也是我下面代码中遇到的问题。我们可以假设图中的节点数量最多为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))
10 个回答
哈希值需要有多好呢？我想你应该不想要图的完整序列化。哈希值通常不能保证没有其他不同的元素（图）会得到相同的哈希值。如果你特别希望同构的图（不同表示方式下的图）有相同的哈希值，那就只能使用在表示方式改变时不变的值。例如：
- 节点的总数
- （有向）连接的总数
- 具有
(indegree, outdegree) = (i,j)的节点总数，适用于任何(i,j)的组合，直到(max(indegree), max(outdegree))（或者限制在某个固定值(m,n)的组合）
所有这些信息可以在 O(#nodes) 的时间内收集到（假设图的存储方式是合理的）。把它们连接起来，你就得到了一个哈希值。如果你愿意，可以对这些连接起来的信息使用一些知名的哈希算法，比如 sha。如果不进行额外的哈希处理，这就是一个 连续哈希（它可以找到相似的图），如果进行额外的哈希处理，它就是 均匀的，并且如果所选的哈希算法具有这些特性，大小是固定的。
就这样，它已经足够好，可以记录任何新增或删除的连接。不过，它可能会漏掉一些被更改的连接（比如 a -> c 替代 a -> b）。
这种方法是模块化的，可以根据需要进行扩展。任何额外包含的属性都会减少哈希冲突的数量，但会增加获取哈希值所需的工作量。这里有一些更多的想法：
- 和上面一样，但考虑二阶的入度和出度。也就是说，能够通过
node->child->child链接到的节点数量（= 二阶出度），或者反过来，经过两步到达给定节点的节点数量。 - 或者更一般的 n 阶入度和出度（可以在 O((平均连接数) ^ (n-1) * #nodes) 的时间内计算）
- 具有 离心率 = x 的节点数量（同样适用于任何 x）
- 如果节点存储了任何信息（除了它们的邻居），可以对所有节点内容的哈希值进行
xor操作。由于xor的特性，节点添加到哈希中的具体顺序就不重要了。
你要求的是“一个唯一的哈希值”，而我显然无法提供这样的值。但我认为“哈希”和“每个图唯一”这两个概念是互斥的（当然这并不完全正确），所以我决定只回答“哈希”部分，而不涉及“唯一”部分。一个“唯一的哈希”（完美哈希）基本上需要是图的完整序列化（因为哈希中存储的信息量必须反映图中信息的总量）。如果这真的是你想要的，只需定义一些唯一的节点顺序（例如，按自身出度排序，然后是入度，再然后是子节点的出度，依此类推，直到顺序不再模糊），并以任何方式序列化图（使用上述排序中的位置作为节点的索引）。
当然，这要复杂得多。
有向无环图的图同构问题仍然是GI完全的。 这意味着目前还没有找到一种能在最坏情况下保证两个同构的有向无环图会产生相同哈希值的解决方案。只有在知道不同图之间的映射关系时，比如说所有的顶点都有独特的标签，才能有效地保证哈希值匹配。
好吧，我们来对少量顶点进行暴力破解。我们需要找到一种图的表示方式，这种方式不依赖于输入中顶点的顺序，因此能保证同构的图会产生相同的表示。此外，这种表示还必须确保没有两个不同构的图会产生相同的表示。
最简单的解决方案是为所有n!种顶点排列构建邻接矩阵，然后将邻接矩阵视为一个n2位的整数。接着，我们可以选择这些数字中最小或最大的一个作为标准表示。这个数字完全编码了图，因此确保没有两个不同构的图会产生相同的数字——可以把这个函数看作是一个完美哈希函数。而且因为我们选择的是在所有可能的顶点排列中编码图的最小或最大数字，所以进一步确保了同构的图会产生相同的表示。
那么在11个顶点的情况下，这个方法效果如何呢？表示将会有121位。我们可以减少11位，因为在无环图中，表示环的对角线将全是零，最终剩下110位。理论上，这个数字还可以进一步减少；并不是所有2110个剩余的图都是无环的，并且对于每个图，可能会有多达11!（大约是225）个同构表示，但实际上这可能会相当困难。有没有人知道如何计算n个顶点的不同有向无环图的数量？
找到这个表示需要多长时间呢？简单来说是11!，也就是39,916,800次迭代。这可不是个小数目，可能已经不太实际了，但我并没有实现和测试它。不过我们可能可以稍微加快这个过程。如果我们通过从上到下、从左到右拼接行来将邻接矩阵视为整数，我们希望在第一行的左侧有尽可能多的1（0），以获得一个大的（小的）数字。因此，我们选择第一个顶点为度数最大的（或最小的）顶点，然后在后续位置选择与这个顶点相连（不相连）的顶点，以将1（0）移到左侧。
可能还有更多的方法来缩小搜索空间，但我不确定是否有足够的办法让这个成为一个实际的解决方案。也许有，或者也许其他人可以在这个想法的基础上进一步开发。
要有效地测试图的同构性，你可以使用nauty这个工具。对于Python用户，有一个叫pynauty的封装工具，但我不能保证它的质量（为了正确编译它，我在它的setup.py文件上做了一些简单的修改）。如果这个封装工具一切正常，那么它会大大简化nauty的使用，你只需要对pynauty.certificate(somegraph)进行哈希处理——同构的图会得到相同的值。
一些快速测试显示，pynauty对每个图（具有相同数量的顶点）都给出了相同的证书。但这只是因为在将图转换为nauty格式时，封装工具有一个小问题。修复这个问题后，它对我来说就能正常工作了（我还使用了http://funkybee.narod.ru/graphs.htm上的图进行比较）。以下是简短的补丁，同时也考虑了setup.py中需要的修改：
diff -ur pynauty-0.5-orig/setup.py pynauty-0.5/setup.py
--- pynauty-0.5-orig/setup.py 2011-06-18 20:53:17.000000000 -0300
+++ pynauty-0.5/setup.py 2013-01-28 22:09:07.000000000 -0200
@@ -31,7 +31,9 @@
ext_pynauty = Extension(
name = MODULE + '._pynauty',
- sources = [ pynauty_dir + '/' + 'pynauty.c', ],
+ sources = [ pynauty_dir + '/' + 'pynauty.c',
+ os.path.join(nauty_dir, 'schreier.c'),
+ os.path.join(nauty_dir, 'naurng.c')],
depends = [ pynauty_dir + '/' + 'pynauty.h', ],
extra_compile_args = [ '-O4' ],
extra_objects = [ nauty_dir + '/' + 'nauty.o',
diff -ur pynauty-0.5-orig/src/pynauty.c pynauty-0.5/src/pynauty.c
--- pynauty-0.5-orig/src/pynauty.c 2011-03-03 23:34:15.000000000 -0300
+++ pynauty-0.5/src/pynauty.c 2013-01-29 00:38:36.000000000 -0200
@@ -320,7 +320,7 @@
PyObject *adjlist;
PyObject *p;
- int i,j;
+ Py_ssize_t i, j;
int adjlist_length;
int x, y;