CODEWITHSUNDEEP
pythongraphtree
Ahmad Othman
Ahmad Othman

Reputation: 187

Generate a random tree graph from known verticies for each generation

I have a list, for example [2, 5, 9]. Each index represents how many verticies are in each generation. For example in generation 0 there are 2 nodes. Those 2 nodes combined have 5 children, those 5 children have 9 children combined etc. From this I want to be able to generate a tree graph, but where the children have random parents. I also want a set maximum amount of children one node can have. So for example generation 1 can not exceed 6 nodes as there are 2 parents to that generation, and every parent can have only 3 children.

I have attempted doing this by using nested lists where the trees are represented by a list inside a list etc. representing a tree. For example:

enter image description here

While doing this I have noticed that it might not be the best solution to use nested lists as they are hard to work with. I however don't know another way of efficiently storing a tree graph.

I have first tried doing this a little bit hardcodey to understand it better and then possibly be able to do it with a recursive function.

levels = [2, 5, 9]
arr = [[] for i in range(levels[0])]
for i in range(1, len(levels)-1):
    level = levels[i]
    while(level > 0):
        j = random.randint(0, levels[i-1]-1)
        arr[j].append([])
        level -= 1

Which prints these lists (at random)

[[[]], [[], [], [], []]]
[[[], [], []], [[], []]]
[[[], []], [[], [], []]]

This is eventually what I want, but this is the correct solution for [2, 5] not [2, 5, 9]. I don't know how to go forward to the next generation from here. I've been stuck at this for some time and I've tried using a recursive function but to little success (usually list index out of range errors).

I would like to ask if there is a better method to generate such a tree from that start generation list [2, 5, 9], and if there's a better way to represent trees in general.. Preferably without using a tree class. Thanks for the help.

Upvotes: 0

Views: 486

Answers (1)

Alex Hall
Alex Hall

Reputation: 36033

It's easier to just think of one level at a time. There's no need to traverse the tree from the root each time you add a node. Then you can create the tree bottom up or top down.

import random
import json

max_children_per_parent = 3


def assign_parents(trees, parents):
    if len(trees) > len(parents) * max_children_per_parent:
        raise ValueError

    for tree in trees:
        while True:
            parent = random.choice(parents)
            if len(parent) < max_children_per_parent:
                parent.append(tree)
                break


def generate_tree_bottom_up(levels):
    bottom = [[] for _ in range(levels[-1])]
    for level in reversed(levels[:-1]):
        parents = [[] for _ in range(level)]
        assign_parents(bottom, parents)
        bottom = parents
    return bottom


def generate_tree_top_down(levels):
    root = top = [[] for _ in range(levels[0])]
    for level in levels[1:]:
        children = [[] for _ in range(level)]
        assign_parents(children, top)
        top = children
    return root


def main():
    for method in [generate_tree_bottom_up, generate_tree_top_down]:
        print(json.dumps(method([2, 5, 9]), indent=4))


if __name__ == '__main__':
    main()

Output:

[
    [
        [
            [],
            []
        ],
        [
            [],
            [],
            []
        ]
    ],
    [
        [
            [],
            []
        ],
        [
            []
        ],
        [
            []
        ]
    ]
]
[
    [
        [
            []
        ],
        [
            [],
            [],
            []
        ]
    ],
    [
        [
            [],
            []
        ],
        [
            [],
            [],
            []
        ],
        []
    ]
]

A list is the natural way to represent a variable number of objects, including children, so you're not really going to get away from them. If it's not just lists, it'll be some kind of tree class containing lists. But you can find ways to view the representation more helpfully, like json.dumps(..., indent=4).

Upvotes: 2

Related Questions