Python 枚举所有具有 5 个节点的无环有向图的代码

Question

所以我最近在学习这门关于概率图形模型的课程，我想尝试一个动手的例子。在示例中，我想遍历所有可能的组合 (29,281) 个无环有向图（或 DAG），看看它们如何拟合数据。

我知道所有可能的图的数量由

给出

from scipy.misc import comb
import numpy as np

def a(n):
    if n == 0:
        return 1
    else:
        sum = 0
        for k in range(1,n+1):
            sum += np.power(-1,k+1)    * \
                   comb(n,k)           * \
                   np.power(2,k*(n-k)) * \
                   a(n-k)
        return sum

这给了我们系列 A003024

但我想找到能够遍历所有这些可能的图而不仅仅是计算它们的算法。

我知道有一些代码可用于无向图，但我无法让它们为我工作。

我对图形的任何形式表示持开放态度，无论是库、自定义函数还是列表列表。

示例 - 当您有两个标签时，有 3 个可能的图形：

[[A:{}], [B:{}]]  # A    B no connection P(A,B) = P(A)P(B)
[[A:{B}], [B:{}]] # A -> B               P(A,B) = P(A)P(B|A)
[[A:{}], [B:{A}]] # A <- B               P(A,B) = P(B)P(A|B)

Answer 1

将图形简单地视为边的连接（节点可以保持不变）可能更容易。

从 numEdges = 0（无连通图）开始，到 numEdges = numNodes - 1（全连通图）。对于每个 numEdges，只需将边放置在每个可能的排列中。

使用全连接图设置可能的边。例如对于五个节点：

AB
AC
AD
AE
BC
BD
BE
CD
CE
DE

注意模式：A（B、C、D、E）、B（C、D、E）、C（D、E）、D（E）

准备好可能的边列表后，根据排列放置下边应该很简单。

Answer 2

因为你想要 29,281 个结果图，标签对你来说一定很重要（IOW，你不是通过同构来修改。）在 networkx 中使用暴力方法：

from itertools import combinations, product
import networkx as nx

def gen_dag(num_nodes):
    all_edges = list(combinations(range(num_nodes), 2))
    for p in product([None, 1, -1], repeat=len(all_edges)):
        G = nx.DiGraph()
        G.add_nodes_from(range(num_nodes))
        edges = [edge[::edge_dir] for edge, edge_dir in zip(all_edges, p) if edge_dir]
        G.add_edges_from(edges)
        if nx.is_directed_acyclic_graph(G):
            yield G

这给出了

In [75]: graphs = list(gen_dag(5))

In [76]: len(graphs)
Out[76]: 29281

和（例如）

In [79]: graphs[1234].edges()
Out[79]: OutEdgeView([(3, 1), (3, 4), (4, 0), (4, 2)])

In [80]: nx.adjacency_matrix(graphs[1234]).todense()
Out[80]: 
matrix([[0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0]], dtype=int64)

Python 枚举所有具有 5 个节点的无环有向图的代码

Python code to enumerate over all acyclic digraphs with 5 nodes

python

algorithm

graph

bayesian