给定一定数量的节点，我怎样才能得到所有的树图？网络x

Question

我想知道有没有办法使用 Networkx 获取所有不同的树？众所周知，具有 n 个节点的树的数量是 n^(n-2)（使用 Cayley 公式），因此如果有 3 个节点，则它有 3 个树图，如果它有 4 个节点，则它有 16 个树木等。我想要的是使用 prufer 序列对所有树进行编码，我知道 Networkx 具有创建随机树的功能，但我有机会获得重复项，我能想到的就是使用 Numpy 这样我就可以找到所有列表中的唯一元素，这是我的代码：

import numpy as np
import networkx as nx

n = 3  #Number of nodes
aux = []
prufer = []

for i in range(10):
    aux.append(nx.random_tree(n))    

for j in aux:
    prufer.append(nx.to_prufer_sequence(j))

arr = np.array(prufer)
newarr = np.unique(arr, axis = 0)

这里的问题是我生成了 10 棵随机树，但最后我只想要 3 棵但是当我想使用 4 个节点找到所有树时我不想生成 50 棵如果我只是去使用 16. 有没有办法更有效地做到这一点？谢谢！

Answer 1

这可能有点暴力，并且可能有内置功能或我缺少的更优雅的方法，但它肯定比随机生成树更好：您可以使用 itertools 生成成对组合和过滤掉重复项和自指向循环：

import itertools

def make_all_trees(nodes):
    # generate all pairwise combinations of nodes
    edges =  [a for a in itertools.product(range(nodes), range(nodes))]

    # use sets to lose..
    # ..symmetric edges: (0,1), (1,0) => keep only (0,1) 
    edges = list(set([tuple(set(e)) for e in edges]))
    # ..and self-loops: (0,0)
    edges = [e for e in edges if len(e)>1]

    trees = []
    # generate all graphs that have nodes-1 edges
    for o in itertools.combinations(edges, nodes-1):
        #make sure that all nodes are in the edgelist:
        flattened = [item for sublist in o for item in sublist]

        if len(set(flattened)) == nodes:
            G = nx.Graph()
            G.add_edges_from(o)
            # make sure all nodes are connected
            if len(list(nx.connected_components(G)))==1:
                trees.append(G)

    return trees

测试用例：

 len(make_all_trees(3)): 3
 len(make_all_trees(4)): 16
 len(make_all_trees(5)): 125

所有 4 个节点树：

树 = make_all_trees(4)

for p, tree in enumerate(trees):
    plt.subplot(4,4,p+1)
    nx.draw_networkx(tree)
plt.show()

Answer 2

如果有人对使用更大的 n 进行缩放的更有效的方法感兴趣，那么您可以使用称为 Prüfer 序列的图论方法：

from sympy.combinatorics.prufer import Prufer
n = 8

max_trees = Prufer.unrank(0,n).size
trees = []
for i in range(max_trees):
    trees.append(Prufer.unrank(i,n).tree_repr)

print(len(trees))
#correctly returns n^(n-2) trees

给定一定数量的节点，我怎样才能得到所有的树图？网络x

How can I get all the tree graphs given a certain numbers of nodes? Networkx

python

networkx

测试用例：

所有 4 个节点树：