给定一定数量的节点，如何获得所有树图?网络x [英] How can I get all the tree graphs given a certain numbers of nodes? Networkx

问题描述

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

I was wondering is there a way to obtain all the different trees using Networkx? It's a known fact that the number of trees with n nodes is n^(n-2) (using Cayley's Formula) so if there is 3 nodes, then it has 3 tree graphs, if it has 4 nodes then it has 16 trees and so on. What I want is to code all the trees using the prufer sequence, I know that Networkx has a function to create random trees, but there is a chance I can get duplicates, all I can think of is use Numpy so I can find all the unique elements in a list, here is my code:

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. 有什么方法可以更有效地做到这一点?谢谢！

The problem here it's that I generated 10 random trees, but in the end I only want 3 but when I want to find all the trees using 4 nodes I don't want to generate 50 if I'm only going to use 16. Is there a way I can do this more efficiently? Thank you!

推荐答案

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

This might be a bit bruteforcy, and there might be built-in functionality or a more elegant approach that I am missing, but it certainly is better than randomly generating the trees: You can use itertools to generate pairwise combinations and filter out duplicates and self-pointing loops:

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)

all 4 node trees:

trees = make_all_trees(4)

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

这篇关于给定一定数量的节点，如何获得所有树图?网络x的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！