Tree with multiple nods for counting (Python)-CodePudding

I hope you can help me, I am quite stuck with my assignment.

For it I have the data in JSON format with multiple entries of which components are needed for the next one. They are presented in the format:

{‘id’ : 123, ‘ needed’ 1, ‘need_id’: None},
{‘id’ : 100, ‘ needed’ 2, ‘need_id’: 123},
{‘id’ : 101, ‘ needed’ 3, ‘need_id’: 123},
{‘id’ : 105, ‘ needed’ 3, ‘need_id’: 123},
{‘id’ : 210, ‘needed’ 5, ‘need_id’: 101},
{‘id’ : 999, ‘needed’ 2, ‘need_id’: 210},

So starting from id that doesn't require any another id, they split to 'nods' where each would have more components down the line.

That would look like

ID:123   (1 component)
|             |      |
|             |      |
ID:100     ID:101   ID:105
(2 com)    (3 com)  (3 com)
             |
             |
           ID:210
           (15 components total)
             |
             |
           ID:999
           (30 components total)

So ID 210 would have 15 components, because 5 is needed by each ID 101. Respectively, ID 999 would need 30 components.

In reality, this tree would be much wider, with many components needed to create component from upper branch.

I am unsure which algorithm would be the fastest to iterate through entire list (100 JSON rows) then count need for each of the components.

I was thinking to store each as an object in the list of child nodes with value of components needed, but that might require too many iterations. Any language can be helpful, python is sufficient but not limited to python.

Any output really appreciated!

CodePudding user response：

In case you are still looking for a solution:

I'm assuming that you're actually dealing with a tree (or a forest) and that your data are organized in the following form:

data = [
    {'id': 123, 'needed': 1, 'need_id': None},
    {'id': 100, 'needed': 2, 'need_id': 123},
    {'id': 101, 'needed': 3, 'need_id': 123},
    {'id': 105, 'needed': 3, 'need_id': 123},
    {'id': 210, 'needed': 5, 'need_id': 101},
    {'id': 999, 'needed': 2, 'need_id': 210},
]

The first step is preprocessing: Organizing the tree in a dictionary tree, thereby adding a childs-view to the nodes (the input has only a parents-view), and collecting the roots in a set roots:

tree = {}
for node in data:
    i, needed, parent = node.values()
    tree[i] = {"needed": needed, "parent": parent, "childs": []}
roots = set()
for i, d in tree.items():
    parent = d["parent"]
    if parent is not None:
        tree[parent]["childs"].append(i)
    else:
        roots.add(i)

Now you can traverse the tree (here in a depth-first manner) and update the needed components accordingly:

for root in roots:
    stack = [root]
    while stack:
        node = stack.pop()
        needed = tree[node]["needed"]
        for child in tree[node]["childs"]:
            tree[child]["needed"] *= needed
            if tree[child]["childs"]:
                stack.append(child)

Result for the sample data:

{100: {'childs': [], 'needed': 2, 'parent': 123},
 101: {'childs': [210], 'needed': 3, 'parent': 123},
 105: {'childs': [], 'needed': 3, 'parent': 123},
 123: {'childs': [100, 101, 105], 'needed': 1, 'parent': None},
 210: {'childs': [999], 'needed': 15, 'parent': 101},
 999: {'childs': [], 'needed': 30, 'parent': 210}}

I'm sure this can be optimized, but my focus here was on transparency.