memory-management - 在 Sage 中使用 nauty_geng 时出现内存错误

Question

我试图让 Sage 生成所有具有 11 个顶点、30 条边和 4 号团的图。我输入了以下内容:

 g11=[g for g in graphs.nauty_geng('11 30') if g.clique_number()==4]

一段时间后，我看到以下消息:

MemoryError                               Traceback (most recent call last)
<ipython-input-6-1ec9660b8e07> in <module>()
----> 1 g11=[g for g in graphs.nauty_geng('11 30') if g.clique_number()==Integer(4)]

/opt/sagemath-8.6/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in clique_number(self, algorithm, cliques, solver, verbose)
   6072         self._scream_if_not_simple(allow_loops=False)
   6073         if algorithm == "Cliquer":
-> 6074             from sage.graphs.cliquer import clique_number
   6075             return clique_number(self)
   6076         elif algorithm == "networkx":

我的 RAM 中似乎没有足够的内存让 Sage 为我做这件事。有没有办法让 Sage 将此信息存储在别处？ Sage 是否只需要使用 RAM 内存？我有 1 TB 的可用存储空间。

如果这不可能，那么我该如何解决这个问题？提前致谢!

Answer 1

上市前计数

有时在列表中存储感兴趣的数学对象是过于雄心勃勃，因为那样会占用太多内存。

第一步可能是计算有多少这样的图，以及在尝试之前迭代它们需要多长时间存储它们。

下面的时间是在一台特定的机器上；他们可能不同在其他机器上。

计算具有 30 条边的 11 个顶点的图形，派系数为 4花了大约两个小时。

sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: %time nb_g_11_30_c4 = sum(1 for g in g_11_30_c4)
CPU times: user 2h 12min 9s, sys: 1min 9s, total: 2h 13min 18s
Wall time: 2h 13min 18s
sage: nb_cg_11_30_c4
58211868

仅计算连接的花费了大致相同的时间。

sage: cg_11_30 = graphs.nauty_geng('11 30:30 -c')
sage: cg_11_30_c4 = (g for g in cg_11_30 if g.clique_number() == 4)
sage: %time nb_cg_11_30_c4 = sum(1 for g in cg_11_30_c4)
CPU times: user 2h 13min 27s, sys: 1min 11s, total: 2h 14min 38s
Wall time: 2h 14min 39s
sage: nb_cg_11_30_c4
58182054

我们看到在 11 个顶点和 30 条边上有大约 5820 万个图和 4 号集团，他们中的大多数人都有联系——只有 29814 人没有联系。如果我们只关心未连接的那些，那就大不一样了!

迭代而不是列表

如果存储这些图不可行，我们知道我们可以遍历它们每次我们想了解有关它们的信息时，只需两个小时。

了解迭代与列表的一个好方法是运行 SageMath tutorial on comprehensions .

例如，取集合中的第一个图并检查其边及其 graph6 string( more on the graph6 format ):

sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: g = next(g_11_30_c4)
sage: print(g.edges(labels=False))
[(0, 7), (0, 8), (0, 9), (0, 10), (1, 7), (1, 8), (1, 9), (1, 10),
(2, 7), (2, 8), (2, 9), (2, 10), (3, 7), (3, 8), (3, 9), (3, 10),
(4, 8), (4, 9), (4, 10), (5, 8), (5, 9), (5, 10), (6, 8), (6, 9),
(6, 10), (7, 9), (7, 10), (8, 9), (8, 10), (9, 10)]
sage: g.graph6_string()
'J???Fb}~~~_'

第二个:

sage: g = next(g_11_30_c4)
sage: print(g.edges(labels=False))
[(0, 7), (0, 8), (0, 9), (0, 10), (1, 7), (1, 8), (1, 9), (1, 10),
(2, 7), (2, 8), (2, 9), (2, 10), (3, 7), (3, 8), (3, 9), (3, 10),
(4, 8), (4, 9), (4, 10), (5, 8), (5, 9), (5, 10), (6, 8), (6, 9),
(6, 10), (7, 8), (7, 9), (7, 10), (8, 10), (9, 10)]
sage: g.graph6_string()
'J???Fb~~v~_'

等等。

存储较小的等效数据

如果图表本身太多而无法存储在列表中，也许我们可以使用这些图的更紧凑的表示，这将占用更少的内存。例如，边列表让我们很容易重建图表；非常紧凑的“graph6 字符串”也是如此。

为了给我们一个想法，让我们比较文件大小作为 Sage 对象的前一万张图的列表，他们的图边列表列表作为 Sage 对象，并将它们的 graph6 字符串作为文本文件:

sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: graphs = [next(g_11_30_c4) for _ in range(10^4)]
sage: save(graphs, "g_11_30_c4_1e4_graph_bare")

sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: edges = [next(g_11_30_c4).edges(labels=False) for _ in range(10^4)]
sage: save(edges, "g_11_30_c4_1e4_graph_edges")

sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: s = '\n'.join(next(g_11_30_c4).graph6_string() for _ in range(10^4))
sage: with open('g_11_30_c4_graph_graph6.txt', 'w') as f:
....:     f.write(s)
....:
119999

比较相应的文件大小:

• g_11_30_c4_1e4_graph_bare.sobj:971K
• g_11_30_c4_1e4_graph_edges.sobj:775K
• g_11_30_c4_1e4_graph_graph6.txt:117K

显然 graph6 格式获胜，存储了所有 5820 万张图在这种格式的文本文件中，大约需要 5820 * 117K，即 680M。

我们也可以将其存储在编号为0到99的100个文件中，如下所示:

sage: n = 100
sage: for k in range(N):
....:     gk = graphs.nauty_geng('11 30:30 {}/{}'.format(k, n))
....:     ggk = (g for g in gk if g.clique_number() == 4)
....:     s = '\n'.join(g.graph6_string() for g in ggk)
....:     with open('g_11_30_c4_graph_graph6_file_{}_of_{}.txt'
....:               .format(k, n - 1), 'w') as f:
....:         f.write(s)

这将使我们可以在多个 session 中研究这些图表，而无需每次淘气工作两个小时。

推荐阅读，具体取决于您的 Sage 基于的 Python 版本:

• Reading and writing files in Python 3
• Reading and writing files in Python 2