有向无环图的哈希值

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

散列必须有多好？我假设您不希望图形的完全序列化。散列很少保证没有第二个（但不同的）元素（图）计算为相同的散列。如果同构图（在不同的表示中）具有相同的散列，这对您非常重要，那么只使用在表示变化下不变的值。例如。：

• 节点总数
• （定向）连接的总数
• 对于任何元组 （i，j） 到 （max（indegree）， max（outdegree）） 的节点总数 （indegree， outdegree） = （i，j） （或对于不超过某个固定值 （m，n）的元组，则限制为

所有这些信息都可以在O（#nodes）中收集[假设图形存储正确]。将它们连接起来，就得到了一个散列。如果您愿意，可以对这些级联信息使用一些众所周知的哈希算法，如＜code＞sha＜/code＞。没有额外的散列，它是一个连续的散列（它允许找到相似的图），如果选择的散列算法具有这些属性，则通过额外的散乱，它是统一的，大小是固定的。

事实上，注册任何添加或删除的连接已经足够好了。它可能会错过已更改的连接(< code>a -

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

• 与上述相同，但具有二阶入度和出度。即＜code＞节点可到达的节点数-

您要求“唯一的哈希值”，显然我无法为您提供一个。但我认为术语“哈希”和“每个图形都是唯一的”是相互排斥的（当然不完全正确），并决定回答“哈希”部分而不是“唯一”部分。“唯一哈希”（完美哈希）基本上需要是图形的完整序列化（因为哈希中存储的信息量必须反映图形中的信息总量）。如果这真的是你想要的，只需定义一些节点的唯一顺序（例如，按自己的出度排序，然后是入度，然后是子级的出度，依此类推，直到顺序明确），并以任何方式序列化图形（使用上述排序中的位置作为节点的索引）。

当然，这要复杂得多。

Answer 2

有向无环图的同构仍然是GI-完全的。因此，目前没有已知的(最坏情况下的子指数)解决方案来保证两个同构的有向无环图将产生相同的散列。只有当不同图之间的映射是已知的时——例如，如果所有的顶点都有唯一的标签——才能有效地保证匹配的散列。

好的，让我们对少量顶点进行暴力处理。我们必须找到一个与输入中顶点的顺序无关的图的表示，从而保证同构图产生相同的表示。此外，这种表示必须确保没有两个非同构图产生相同的表示。

最简单的解决方法是为所有的n构造邻接矩阵！顶点的排列，并将邻接矩阵解释为n²位整数。然后我们可以选择最小或最大的数作为规范表示。这个数完全编码了图，因此确保了没有两个非同构的图产生相同的数——可以认为这个函数是完美的散列函数。因为我们在所有可能的顶点排列下选择最小或最大的数字来编码图，我们进一步确保同构的图产生相同的表示。

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

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

可能有更多的可能性来削减搜索空间，但我不确定是否有足够的可能性来实现这一点。也许有，或者也许其他人至少可以在这个想法的基础上建立一些东西。

Answer 3

为了有效地测试图同构，您将需要使用nauty。具体到Python，有包装器pynauty，但我不能证明它的质量(为了正确编译它，我必须对它的< code>setup.py做一些简单的修补)。如果这个包装器做的一切都是正确的，那么它为您感兴趣的用途简化了nauty很多，这只是一个散列< code > pynauty . certificate(some graph)的问题，对于同构图来说，这将是相同的值。

一些快速测试表明，pynty为每个图（具有相同数量的顶点）提供相同的证书。但这只是因为将图形转换为n的格式时包装器中的一个小问题。修复此问题后，它对我有用（我也使用了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;