在 Python w/ networkX 中高效存储和使用大量图表，目的是跨图表进行推理？

Question

目标如下：我有一组节点，大小为 N，我想

生成（作为可迭代的）一组所有可能的有向图（大概使用 networkx.DiGraph() 和 numpy.arange(0,N)）（编辑：澄清——这是一个非常大的数字甚至小 N 的图，因此需要某种可迭代结构，允许在运行中构建集合 )
根据满足某些条件（例如，存在从节点 0 到节点 N-1 的完整路径）过滤这组图
存储与每条边关联的参数值
计算过滤后的图形集的函数，考虑这些函数中与边相关的参数值，而不需要同时将所有图形都存储在内存中（因为如果没有并行化，这真的很费力，并且我还不知道如何处理并行化）

似乎已经有很多关于有效处理具有许多节点和边的图（即，大图）的讨论，但很少讨论如何有效处理许多一次绘制图形（大组个图形 ），其中每个图形都不会使系统负担过重。

编辑：理想情况下，这也适用于 pandas 和 numpy 数组，但我很确定上述任何解决方案也可以用于这些，因为从根本上说 networkX 是在字典上工作词典数量。

Answer 1

您写道，您希望生成具有 N 个节点的所有可能的有向图。不幸的是，即使对于小 N.

这也是不可行的

给定一组 N 个节点，可能的无向边数为 N(N-1)/2。我们可以通过选择这些边的子集来定义图。有 2^(N*(N-1)/2) 个可能的子集，这意味着 N 个节点上有那么多可能的无向图。

假设N=10。这些节点上大约有 3.5 * 10^13 个可能的图形。如果您每秒可以处理一百万张图表，那么您大约需要 10^7 秒来处理所有图表。这是一年的顺序。

那只是无向图。还有更多的有向图。对于 N 个节点，有 2^(N*(N-1)) 个有向图。这里有一个 table 演示了爆炸的速度。 |V|为节点数：

|V|   Number of Digraphs
===   ==================
1     1
2     4
3     64
4     4096
5     1048576
6     1073741824
7     4398046511104
8     72057594037927936
9     4722366482869645213696

如果您真的喜欢这样做，这里有 python 生成器，它们将懒惰地枚举节点集上的图：

from itertools import chain
import networkx as nx

def power_set(iterable):
    """Return an iterator over the power set of the finite iterable."""
    s = list(iterable)
    return chain.from_iterable(combinations(s, n) for n in xrange(len(s) + 1))

def enumerate_graphs(nodes):
    # create a list of possible edges
    possible_edges = list(combinations(nodes, 2))

    # create a graph for each possible set of edges
    for edge_set in power_set(possible_edges):
        g = nx.Graph()
        g.add_nodes_from(nodes)
        g.add_edges_from(edge_set)
        yield g

def enumerate_digraphs(nodes):
    # create a list of possible edges
    possible_edges = list(combinations(nodes, 2))

    # generate each edge set
    for edge_set in power_set(possible_edges):
        # for each set of `M` edges there are `M^2` directed graphs
        for swaps in power_set(xrange(len(edge_set))):
            directed_edge_set = list(edge_set)
            for swap in swaps:
                u,v = directed_edge_set[swap]
                directed_edge_set[swap] = v,u
            g = nx.DiGraph()
            g.add_nodes_from(nodes)
            g.add_edges_from(directed_edge_set)
            yield g

然后我们可以绘制所有的有向图：

nodes = ("apples", "pears", "oranges")

digraphs = list(enumerate_digraphs(nodes))
layout = nx.random_layout(digraphs[0])

plt.figure(figsize=(20,30))
for i,g in enumerate(digraphs):
    plt.subplot(6,5,i+1)
    nx.draw_networkx(g, pos=layout)
    plt.gca().get_xaxis().set_visible(False)
    plt.gca().get_yaxis().set_visible(False)

在 Python w/ networkX 中高效存储和使用大量图表，目的是跨图表进行推理？

Efficient storage and use of large sets of graphs in Python w/ networkX, the aim being inference across the graphs?

python

graph

networkx

inference