Учитывая набор узлов, перечислять графы на нем

Question

У меня есть набор узлов

N = [1,2, .... n]

Я могу определить 2 ^ (nC2) графиков на этом набор узлов. Я хочу перечислить каждый из них в неубывающем порядке по количеству ребер. Есть ли эффективный способ сделать это в python networkx? Предположим, что неориентированные графы, и, перечисляя графы, я в основном имею в виду перечисление матриц смежности.

Answer 1

Это может быть достигнуто с помощью приведенного ниже кода. По сути, мы используем itertools для генерации списков, представляющих все возможные графы, сортируем их по количеству ребер, которые они содержат, генерируем словарь списков, представляющих этот граф, а затем возвращаем список графов networkx, соответствующих этим диктам списков.

Код:

from math import factorial as f
import networkx as nx
import itertools

def nCr(n,r):
    return f(n) // f(r) // f(n-r)

def get_all_graphs(n):
    rows = sorted(itertools.product(range(2), repeat=nCr(n,2)), key= lambda x: sum(x))

    indices = [sum(range(n-1, n-i-1, -1)) for i in range(n)] + [sum(range(n))]

    graphs = [{node: [j+node+1 for j, edge in enumerate(row[indices[node] : indices[node+1]]) if edge == 1] for node in range(n)} for row in rows]

    return [nx.from_dict_of_lists(x) for x in graphs]

Пример:

import matplotlib.pyplot as plt

fig, ax = plt.subplots(nrows=2, ncols=4)

graphs = get_all_graphs(3)

for i, row in enumerate(ax):
    for j, col in enumerate(row):

        nx.draw(graphs[i*4+j], with_labels=True, ax=col)

plt.tight_layout()
plt.show()

Выход:

Или с приведенным выше примером, адаптированным для n = 4: