How Can I Get All The Tree Graphs Given A Certain Numbers Of Nodes? Networkx

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

Solution 1:

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

defmake_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 iflen(e)>1]

    trees = []
    # generate all graphs that have nodes-1 edgesfor 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]

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

    return trees

testcases:

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

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()