生成给定大小的所有有向图直至同构

Question

我正在尝试生成具有给定数量节点的所有有向图，直至图同构，以便我可以将它们输入到另一个 Python 程序中。这是一个使用 NetworkX 的简单参考实现，我想加快速度：

from itertools import combinations, product
import networkx as nx

def generate_digraphs(n):
  graphs_so_far = list()
  nodes = list(range(n))
  possible_edges = [(i, j) for i, j in product(nodes, nodes) if i != j]
  for edge_mask in product([True, False], repeat=len(possible_edges)):
    edges = [edge for include, edge in zip(edge_mask, possible_edges) if include]
    g = nx.DiGraph()
    g.add_nodes_from(nodes)
    g.add_edges_from(edges)
    if not any(nx.is_isomorphic(g_before, g) for g_before in graphs_so_far):
      graphs_so_far.append(g)
  return graphs_so_far

assert len(generate_digraphs(1)) == 1
assert len(generate_digraphs(2)) == 3
assert len(generate_digraphs(3)) == 16

此类图的数量似乎增长得相当快，并且由该OEIS 序列给出。我正在寻找一种解决方案，能够在合理的时间内生成最多 7 个节点的所有图表（总共约 10 亿张图表）。

将图表示为 NetworkX 对象并不是很重要；例如，用邻接列表表示图形或使用不同的库对我来说很好。

Answer 1

\xe2\x80\x99s 是我从 Brendan McKay\xe2\x80\x99s 论文\n\xe2\x80\x9c无同构详尽生成 \xe2\x80\x9d 中学到的一个有用的想法\xe2\x80\x9d（尽管我相信它早于\n纸）。

\n

这个想法是，我们可以将同构类组织成一棵树，\n其中具有空图的单例类是根，并且每个\n具有 n > 0 个节点的图的类都有一个父类，其图\n具有 n \xe2\ x88\x92 1 个节点。要枚举具有\n > 0 个节点的图的同构类，请枚举具有 n \xe2\x88\x92 1\n 个节点的图的同构类，并且对于每个这样的类，以所有\n可能的方式将其代表扩展到 n 个节点，并且过滤掉实际上\xe2\x80\x99t\n子项。

\n

下面的 Python 代码通过一个基本但不平凡的图同构子例程实现了这个想法。对于 n =\n6 需要几分钟，对于 n = 7（此处估计）大约需要几天。为了获得额外\n速度，请将其移植到 C++，也许会找到更好的算法来处理\n排列组（也许在TAoCP，虽然大多数图都没有\n对称性，所以\xe2\x80\x99s不清楚好处有多大）。

\n

import cProfile\nimport collections\nimport itertools\nimport random\n\n\n# Returns labels approximating the orbits of graph. Two nodes in the same orbit\n# have the same label, but two nodes in different orbits don't necessarily have\n# different labels.\ndef invariant_labels(graph, n):\n    labels = [1] * n\n    for r in range(2):\n        incoming = [0] * n\n        outgoing = [0] * n\n        for i, j in graph:\n            incoming[j] += labels[i]\n            outgoing[i] += labels[j]\n        for i in range(n):\n            labels[i] = hash((incoming[i], outgoing[i]))\n    return labels\n\n\n# Returns the inverse of perm.\ndef inverse_permutation(perm):\n    n = len(perm)\n    inverse = [None] * n\n    for i in range(n):\n        inverse[perm[i]] = i\n    return inverse\n\n\n# Returns the permutation that sorts by label.\ndef label_sorting_permutation(labels):\n    n = len(labels)\n    return inverse_permutation(sorted(range(n), key=lambda i: labels[i]))\n\n\n# Returns the graph where node i becomes perm[i] .\ndef permuted_graph(perm, graph):\n    perm_graph = [(perm[i], perm[j]) for (i, j) in graph]\n    perm_graph.sort()\n    return perm_graph\n\n\n# Yields each permutation generated by swaps of two consecutive nodes with the\n# same label.\ndef label_stabilizer(labels):\n    n = len(labels)\n    factors = (\n        itertools.permutations(block)\n        for (_, block) in itertools.groupby(range(n), key=lambda i: labels[i])\n    )\n    for subperms in itertools.product(*factors):\n        yield [i for subperm in subperms for i in subperm]\n\n\n# Returns the canonical labeled graph isomorphic to graph.\ndef canonical_graph(graph, n):\n    labels = invariant_labels(graph, n)\n    sorting_perm = label_sorting_permutation(labels)\n    graph = permuted_graph(sorting_perm, graph)\n    labels.sort()\n    return max(\n        (permuted_graph(perm, graph), perm[sorting_perm[n - 1]])\n        for perm in label_stabilizer(labels)\n    )\n\n\n# Returns the list of permutations that stabilize graph.\ndef graph_stabilizer(graph, n):\n    return [\n        perm\n        for perm in label_stabilizer(invariant_labels(graph, n))\n        if permuted_graph(perm, graph) == graph\n    ]\n\n\n# Yields the subsets of range(n) .\ndef power_set(n):\n    for r in range(n + 1):\n        for s in itertools.combinations(range(n), r):\n            yield list(s)\n\n\n# Returns the set where i becomes perm[i] .\ndef permuted_set(perm, s):\n    perm_s = [perm[i] for i in s]\n    perm_s.sort()\n    return perm_s\n\n\n# If s is canonical, returns the list of permutations in group that stabilize s.\n# Otherwise, returns None.\ndef set_stabilizer(s, group):\n    stabilizer = []\n    for perm in group:\n        perm_s = permuted_set(perm, s)\n        if perm_s < s:\n            return None\n        if perm_s == s:\n            stabilizer.append(perm)\n    return stabilizer\n\n\n# Yields one representative of each isomorphism class.\ndef enumerate_graphs(n):\n    assert 0 <= n\n    if 0 == n:\n        yield []\n        return\n    for subgraph in enumerate_graphs(n - 1):\n        sub_stab = graph_stabilizer(subgraph, n - 1)\n        for incoming in power_set(n - 1):\n            in_stab = set_stabilizer(incoming, sub_stab)\n            if not in_stab:\n                continue\n            for outgoing in power_set(n - 1):\n                out_stab = set_stabilizer(outgoing, in_stab)\n                if not out_stab:\n                    continue\n                graph, i_star = canonical_graph(\n                    subgraph\n                    + [(i, n - 1) for i in incoming]\n                    + [(n - 1, j) for j in outgoing],\n                    n,\n                )\n                if i_star == n - 1:\n                    yield graph\n\n\ndef test():\n    print(sum(1 for graph in enumerate_graphs(5)))\n\n\ncProfile.run("test()")\n

\n