Код 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

Поскольку вы хотите получить 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)

Answer 2

Может быть проще представить ваши графики просто как соединение ребер (узлы можно поддерживать постоянными).

Начните с 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)

После того, как вы подготовите свой список возможных ребер, вы должны легко расположить ребра в соответствии с перестановками.