I'm interested in recursive generation of trees in Python. For my eventual application, it's important that the trees be represented as a list of nodes (rather than say a dictionary, or an edge list, or some other format). Also, in my eventual application, each node of the tree will have between 0 and hundreds of children. In this skeleton code, the number of children for each node is generated randomly.
The trees generated have a parameter-defined maximum depth, but because even nodes not at the maximum depth might have no children, some leaves will be closer to the root than others.
I wrote this function for the task:
import random def generate_random_tree(nodelist=, idx=0, parent=None, depth=0, max_children=2, max_depth=2): """Build a list of nodes in a random tree up to a maximum depth. :param: nodelist list, the nodes in the tree; each node is a list with elements [idx, parent, depth] :param: idx int, the index of a node :param: parent int, the index of the node's parent :param: depth int, the distance of a node from the root :param: max_children int, the maximum number of children a node can have :param: max_depth int, the maximum distance from the tree to the root""" if depth < max_depth and depth >=0: # add a random number of children n = random.randint(0, max_children) nodelist.extend([[idx+i, parent, depth] for i in xrange(n)]) # for each new child, add new children [generate_random_tree(nodelist, len(nodelist), idx+i, depth+1, max_children, max_depth) for i in xrange(n)] elif depth == max_depth: # add a random number of leaves n = random.randint(0, max_children) nodelist.extend([[idx+i, parent, depth] for i in xrange(n)]) return else: # this should never happen raise ValueError('Algorithm halted because depth > max_depth or depth < 0.') return
The function is used like this:
tree =[[0, None, 0]] # the algorithm starts with a root node which has no parents and depth 0 random.seed(0) generate_random_tree(nodelist=tree, idx=len(tree), parent=0, depth=1, max_children=3, max_depth=3) [0, None, 0] [1, 0, 1] [2, 0, 1] [3, 0, 1] [4, 1, 2] [5, 1, 2] [6, 1, 2] [7, 4, 3] [8, 5, 3] [9, 6, 3] [10, 6, 3] [11, 2, 2] [12, 11, 3] [13, 11, 3] [14, 11, 3] [15, 3, 2] [16, 15, 3]
This function does the task, but I'm eager for feedback on the quality of this implementation. Any feedback is welcome, of course, but particular questions I have include:
Are there any better ways to find appropriate indices for each new node other than calling
Are there simple, recursive Python implementations that
returnvalues rather than relying on list mutability?
(This may be out of scope for se.cr; if so, please ignore) Is there a way to get the enumeration to be depth-first rather than the breadth-first implementation I currently have?
Although this code isn't going to go into a production in environment or be worked on by teams of professional software engineers, high-level comments about readability, best practices, and hidden corner cases would be much appreciated.