给定一个节点集,枚举其上的图
Given a node set, enumerate graphs on it
我有一个节点集
N=[1,2,....n]
我可以在这个节点集上定义 2^(nC2) 个图。我想根据边数以非递减顺序枚举它们中的每一个。在 python networkx 中有有效的方法吗?假设无向图,通过枚举图,我基本上是指枚举邻接矩阵。
这可以使用以下代码实现。基本上,我们使用 itertools 来生成表示所有可能图的列表,根据它们包含的边数对它们进行排序,生成表示该图的列表字典,然后 return 与这些列表字典相对应的 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:
我有一个节点集
N=[1,2,....n]
我可以在这个节点集上定义 2^(nC2) 个图。我想根据边数以非递减顺序枚举它们中的每一个。在 python networkx 中有有效的方法吗?假设无向图,通过枚举图,我基本上是指枚举邻接矩阵。
这可以使用以下代码实现。基本上,我们使用 itertools 来生成表示所有可能图的列表,根据它们包含的边数对它们进行排序,生成表示该图的列表字典,然后 return 与这些列表字典相对应的 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: