有向无环图的散列值

Question

如何将有向无环图转换成散列值，使任意两个同构图散列为同一个值？这是可以接受的，但不希望两个同构图散列到不同的值，这就是我在下面的代码中所做的。我们可以假设图中的顶点数最多为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))

Answer 1

Graph isomorphism for directed acyclic graphs is still GI-complete.因此，目前还没有已知的（最坏情况下的次指数）解决方案来保证两个同构的有向无环图将产生相同的散列。只有当不同图之间的映射已知时（例如，如果所有顶点都有唯一的标签），才能有效地保证匹配哈希。在

好吧，让我们对少数顶点强制执行。我们必须找到一个独立于输入顶点顺序的图的表示，从而保证同构图产生相同的表示。此外，这种表示必须确保没有两个非同构图产生相同的表示。在

最简单的解决方案是构造所有n的邻接矩阵！顶点的置换，并将邻接矩阵解释为n²位整数。然后我们可以选择这些数字中最小的或最大的作为规范表示。这个数完全编码了图，因此确保没有两个非同构图产生相同的数-可以考虑这个函数aperfect hash function。由于我们在所有可能的顶点置换下选择最小或最大的编码数，我们进一步确保同构图产生相同的表示。在

在11个顶点的情况下，这是好是坏？好吧，这个表示将有121位。我们可以减少11位，因为在一个无环图中，代表循环的对角线都是零，只剩下110位。理论上这个数字可以进一步减少；并不是所有2个¹¹⁰剩余的图都是无环的，每个图可能最多有11个！-大约有2²⁵-同构表示，但实际上这可能很难做到。有人知道如何计算有n个顶点的有向无环图的个数吗？在

找到这个代表需要多长时间？天真的11！或39916800次迭代。这不是什么都没有，可能已经不切实际，但我没有实现和测试它。但我们可以加快一点。如果我们通过从上到下从左到右的顺序将相邻矩阵解释为整数，我们希望在第一行的左边有许多个1（零），以获得一个大（小）数。因此，我们选择最大（最小）阶数（取决于表示形式的索引度或出度）的顶点（或其中一个顶点）作为第一个顶点，在随后的位置上选择与该顶点连接（未连接）的顶点，以将一（零）移到左侧。在

有可能有更多的可能性来删减搜索空间，但我不确定是否有足够的方法使这成为一个切实可行的解决方案。也许有，或者至少有人可以在这个想法的基础上建立一些东西。在

Answer 2

为了有效地测试图同构，您需要使用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;

Answer 3

杂烩要有多好？我假设您希望对图进行完全序列化。哈希很少保证没有第二个（但不同的）元素（图）计算出相同的哈希值。如果同构图（在不同的表示法中）具有相同的散列值对您非常重要，那么只使用在表示形式改变下不变的值。E、 g.：

• 节点总数
• （定向）连接的总数
• 对于(i,j)到(max(indegree), max(outdegree))的任何元组，具有(indegree, outdegree) = (i,j)的节点总数（或限制在某些固定值(m,n)的元组）

所有这些信息都可以收集到O（#节点）[假设图形存储正确]。将它们串联起来，就得到了一个散列。如果您愿意，可以对这些连接的信息使用一些众所周知的哈希算法，如sha。没有额外的散列，它是一个连续散列（它允许找到相似的图），如果附加的散列算法具有这些属性，则它是一致的，并且大小是固定的。在

实际上，它已经足够好注册任何添加或删除的连接。但它可能会丢失已更改的连接（a -> c而不是a -> b）。在

---

这种方法是模块化的，可以根据需要进行扩展。包含的任何附加属性都会减少冲突的数量，但会增加获取哈希值所需的工作量。还有一些想法：

• 同上，但有二级进出度。也就是说，node->child->child链可以达到的节点数（=二阶出度），或者分别是分两步到达给定节点的节点数。在
• 或更一般的n阶进出度（可以用O（（平均连接数）^（n-1）*\nodes）计算）
• 具有eccentricity=x的节点数（同样适用于任何x）
• 如果节点存储任何信息（而不是它们的邻居），则使用所有节点内容的任何类型的散列的xor。由于xor，添加到哈希的节点的特定顺序无关紧要。在

---

你要求“一个唯一的哈希值”，显然我不能给你一个。但我认为术语“散列”和“每个图唯一”是相互排斥的（当然不完全正确），于是决定回答“散列”部分，而不是“唯一”部分。“唯一散列”（perfect hash）基本上需要是图的完全序列化（因为散列中存储的信息量必须反映出图中的信息总量）。如果这确实是您想要的，只需定义一些唯一的节点顺序（例如，按自己的outdegree排序，然后按indegree排序，然后再按子节点的outdegree排序，直到顺序明确为止），并以任何方式序列化图（使用公式中的位置作为节点的索引）。在

当然，这要复杂得多。在