python find sub tree minimum and maximum value

Question

I have a tree with nodes, in each node I have id, name, nodes, roles, parent_id and type. I need to write a function that check in each nodes, if the nodes has roles, then find the minimum and maximum duration or the roles into the the roles. after that I need to compare it with his parent(if it's not none), if the parent have maximum duration bigger then it so the children will get the maximum duration of parent/grandparent.. I'll add some examples and what I expected to get

 # example 1
roles_1 = [{id: 'r1', 'duration': 4}]
roles_2 = [{id: 'r2', 'duration': 5}, {id: 'r3', 'duration': 8}]

input_tree1 = {
    'nodes': [
        {
            'id': '1',
            'name': 'org1',
            'parent_id': None,
            'type': 'organization',
            'nodes': [
                {
                    'id': '2',
                    'name': 'o_folder_1',
                    'org_id': '1',
                    'parent_id': '1',
                    'type': 'folder',
                    'roles': roles_1,

                    'nodes': [
                        {
                            'id': '3',
                            'name': 'o1_f1_project_1',
                            'nodes': [],
                            'org_id': '1',
                            'parent_id': '2',
                            'type': 'project',
                            'roles': roles_2,
                        }
                    ],
                }
            ],
        }
    ]
}

I have a list of roles, each list of roles contains object of role. each role has id and duration. in this example, I have parent org1 with one child o_folder_1 and one grandchild o1_f1_project_1, what I need to do is tho check the grandchild if he has roles, if yes, I calculate the min and max duration of the sub tree, here is 8, then go level up calculate the roles if the node have , here is 4.. 4 is less than 8 so I need to add a update a new field of maximum_duration and minimum duration as you can see in expected tree:

  expected_tree1 = {'nodes': [
    {
        'id': '1',
        'name': 'org1',
        'parent_id': None,
        'type': 'organization',
        'nodes': [
            {
                'id': '2',
                'name': 'o_folder_1',
                'org_id': '1',
                'parent_id': '1',
                'type': 'folder',
                'roles': roles_1,
                'min_duration': 4,
                'max_duration': 4,
                'nodes': [
                    {
                        'id': '3',
                        'name': 'o1_f1_project_1',
                        'nodes': [],
                        'org_id': '1',
                        'parent_id': '2',
                        'type': 'project',
                        'roles': roles_2,
                        'min_duration': 4,
                        'max_duration': 8
                    }
                ],

            }
        ],
    }
]
}

as you can see here, I added new field of min_duration and maximum_duration for each node with the right value. example 2:

  # example 2
roles_1 = [{id: 'r1', 'duration': 12}]
roles_2 = [{id: 'r2', 'duration': 4}, {id: 'r3', 'duration': 2}]
roles_3 = [{id: 'r4', 'duration': 5}]
roles_4 = [{id: 'r5', 'duration': 9}]

input_tree2 = {'nodes':
    [
        {
            'id': '1',
            'name': 'org1',
            'parent_id': None,
            'type': 'organization',
            'nodes':
                [
                    {
                        'id': '2',
                        'name': 'o1_folder_1',
                        'org_id': '1',
                        'parent_id': '1',
                        'type': 'folder',
                        'roles': roles_1,
                        'min_duration': 12,
                        'max_duration': 12
                        'nodes': [
                            {
                                'id': '3',
                                'name': 'o1_f1_project_1',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '2',
                                'type': 'project',
                                'roles': roles_2,

                            },
                            {
                                'id': '4',
                                'name': 'o1_f1_project_2',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '2',
                                'type': 'project',
                                'roles': roles_3,

                            },

                        ],
                    },

                    {
                        'id': '4',
                        'name': 'o1_folder_2',
                        'org_id': '1',
                        'parent_id': '1',
                        'type': 'folder',
                        'roles': roles_4,
                        'nodes': [
                            {
                                'id': '3',
                                'name': 'o1_f2_project1',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '4',
                                'type': 'project',
                                'roles': roles_3,
                            }
                        ],
                    },

                ],
        }]}

expected tree 2

  expected_tree2 = {'nodes':
    [
        {
            'id': '1',
            'name': 'org1',
            'parent_id': None,
            'type': 'organization',
            'nodes':
                [
                    {
                        'id': '2',
                        'name': 'o1_folder_1',
                        'org_id': '1',
                        'parent_id': '1',
                        'type': 'folder',
                        'roles': roles_1,
                        'min_duration': 12,
                        'max_duration': 12
                        'nodes': [
                            {
                                'id': '3',
                                'name': 'o1_f1_project_1',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '2',
                                'type': 'project',
                                'roles': roles_2,
                                'min_duration': 2,
                                'max_duration': 12
                            },
                            {
                                'id': '4',
                                'name': 'o1_f1_project_2',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '2',
                                'type': 'project',
                                'roles': roles_2,
                                'min_duration': 5,
                                'max_duration': 12
                            },
                        ],
                    },

                    {
                        'id': '4',
                        'name': 'o1_folder_2',
                        'org_id': '1',
                        'parent_id': '1',
                        'type': 'folder',
                        'roles': roles_4,
                        'min_duration': 9,
                        'max_duration': 9
                        'nodes': [
                            {
                                'id': '3',
                                'name': 'o1_f2_project1',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '4',
                                'type': 'project',
                                'roles': roles_3,
                                'min_duration': 5,
                                'max_duration': 9
                            }
                        ],
                    },

                ],
        }]}

example 3

 roles_1 = [{id: 'r1', 'duration': 18}]
roles_2 = [{id: 'r2', 'duration': 4}, {id: 'r3', 'duration': 2}]
roles_3 = [{id: 'r4', 'duration': 5}]
roles_4 = [{id: 'r5', 'duration': 9}, {id: 'r5', 'duration': 12}]
roles_5 = [{id: 'r6', 'duration': 20}]
input_tree3 = {'nodes':
    [
        {
            'id': '1',
            'name': 'org1',
            'parent_id': None,
            'type': 'organization',
            'roles': roles_1,
            'nodes':
                [
                    {
                        'id': '2',
                        'name': 'o1_folder_1',
                        'org_id': '1',
                        'parent_id': '1',
                        'type': 'folder',
                        'roles': roles_3,
                        'min_duration': 12,
                        'max_duration': 12,
                        'nodes': [
                            {
                                'id': '3',
                                'name': 'o1_f1_project_1',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '2',
                                'type': 'project',
                                'roles': roles_2,

                            },
                            {
                                'id': '4',
                                'name': 'o1_f1_project_2',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '2',
                                'type': 'project',
                                'roles': roles_2,

                            },

                        ],

                    },

                    {
                        'id': '4',
                        'name': 'o1_folder_2',
                        'org_id': '1',
                        'parent_id': '1',
                        'type': 'folder',
                        'roles': roles_5,
                        'nodes': [
                            {
                                'id': '3',
                                'name': 'o1_f2_project1',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '2',
                                'type': 'project',
                                'roles': roles_4,

                            }
                        ],

                    },

                ],
        }]}

expected tree 3

 expected_tree3 = {'nodes':
    [
        {
            'id': '1',
            'name': 'org1',
            'parent_id': None,
            'type': 'organization',
            'roles': roles_1,
            'min_duration': 18,
            'max_duration': 18,
            'nodes':
                [
                    {
                        'id': '2',
                        'name': 'o1_folder_1',
                        'org_id': '1',
                        'parent_id': '1',
                        'type': 'folder',
                        'roles': roles_3,
                        'min_duration': 5,
                        'max_duration': 18,
                        'nodes': [
                            {
                                'id': '3',
                                'name': 'o1_f1_project_1',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '2',
                                'type': 'project',
                                'roles': roles_2,
                                'min_duration': 2,
                                'max_duration': 18

                            },
                            {
                                'id': '4',
                                'name': 'o1_f1_project_2',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '2',
                                'type': 'project',
                                'roles': roles_2,
                                'min_duration': 2,
                                'max_duration': 18

                            },
                        ],

                    },

                    {
                        'id': '4',
                        'name': 'o1_folder_2',
                        'org_id': '1',
                        'parent_id': '1',
                        'type': 'folder',
                        'roles': roles_5,
                        'min_duration': 18,
                        'max_duration': 20,
                        'nodes': [
                            {
                                'id': '3',
                                'name': 'o1_f2_project1',
                                'nodes': [],
                                'org_id': '1',
                                'parent_id': '4',
                                'type': 'project',
                                'roles': roles_4,
                                'min_duration': 9,
                                'max_duration': 20

                            }
                        ],
                    },

                ],

        }]}

as you can see in the examples, each time I check in the last child if he has roles, if he has so it calculate the max duration, then compare with his parent if he has, if the parent has maximum duration it will get it.. but if not, the child only the child remain with the maximum duration, his parent will not effect by id and will not get the child duration..

assumptions:

when parent_id is None is the root
it can be with many levels (root->child->grandchild->....)
if the root doesn't have roles so to check his children.
root can be some children (not always binary tree)

actually what I'm tried to do it

def add_min_max_duration(tree:Dict):

for node in tree["nodes"]:
    if "roles" in node.keys():
        node["min_duration"] = 25
        node["max_duration"] = 0
        for role in node["roles"]:
            node["min_duration"] = min(node["min_duration"], role.duration)
            node["max_duration"] = max(node["max_duration"], role.duration)
    add_min_max_duration(node)

but it's not good because it's not compare with his parent/grandparent..

user_633183 · Answer

data abstraction

Start with a min_max data type with a + operation for combining two min_max instances -

mm1 = min_max(2,5)
mm2 = min_max(3,9)
mm3 = mm1 + mm2    # (2, 9)

We could write it something like this -

from math import inf

class min_max:
  def __init__(self, min = +inf, max = -inf):
    self.min = min
    self.max = max
  def __add__(self, other):
    return min_max(min(self.min, other.min), max(self.max, other.max))

role_min_max

We can compute the min_max of a role by writing role_min_max -

def role_min_max(role):
  return iter_min_max(x["duration"] for x in role)
  
def iter_min_max(iterable):
  r = min_max()
  for value in iterable:
    r = r + min_max(value, value)
  return r

tree_min_max

Finally tree_min_max starts with a default min_max of (-Infinity, Infinity) and we + it to the role_min_max of the tree["roles"] value, if present. For all node of the children tree["nodes"], we call tree_min_max(node, mm) with the updated min_max, mm -

def tree_min_max(tree, mm = min_max()):
  if "roles" in tree:
    mm = mm + role_min_max(tree["roles"])
  return {
    "duration_min": mm.min,
    "duration_max": mm.max,
    **tree,
    "nodes": list(tree_min_max(node, mm) for node in tree["nodes"])
  }

demo

We will use json to pretty print the newly created tree -

import json
print(json.dumps(tree_min_max(input_tree3), indent=2))

{
  "duration_min": Infinity,
  "duration_max": -Infinity,
  "nodes": [
    {
      "duration_min": 18,
      "duration_max": 18,
      "id": "1",
      "name": "org1",
      "parent_id": null,
      "type": "organization",
      "roles": [
        {
          "id": "r1",
          "duration": 18
        }
      ],
      "nodes": [
        {
          "duration_min": 5,
          "duration_max": 18,
          "id": "2",
          "name": "o1_folder_1",
          "org_id": "1",
          "parent_id": "1",
          "type": "folder",
          "roles": [
            {
              "id": "r4",
              "duration": 5
            }
          ],
          "nodes": [
            {
              "duration_min": 2,
              "duration_max": 18,
              "id": "3",
              "name": "o1_f1_project_1",
              "nodes": [],
              "org_id": "1",
              "parent_id": "2",
              "type": "project",
              "roles": [
                {
                  "id": "r2",
                  "duration": 4
                },
                {
                  "id": "r3",
                  "duration": 2
                }
              ]
            },
            {
              "duration_min": 2,
              "duration_max": 18,
              "id": "4",
              "name": "o1_f1_project_2",
              "nodes": [],
              "org_id": "1",
              "parent_id": "2",
              "type": "project",
              "roles": [
                {
                  "id": "r2",
                  "duration": 4
                },
                {
                  "id": "r3",
                  "duration": 2
                }
              ]
            }
          ]
        },
        {
          "duration_min": 18,
          "duration_max": 20,
          "id": "4",
          "name": "o1_folder_2",
          "org_id": "1",
          "parent_id": "1",
          "type": "folder",
          "roles": [
            {
              "id": "r6",
              "duration": 20
            }
          ],
          "nodes": [
            {
              "duration_min": 9,
              "duration_max": 20,
              "id": "3",
              "name": "o1_f2_project1",
              "nodes": [],
              "org_id": "1",
              "parent_id": "2",
              "type": "project",
              "roles": [
                {
                  "id": "r5",
                  "duration": 9
                },
                {
                  "id": "r5",
                  "duration": 12
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

Note, your role_* data should put id in quotes, otherwise the key for the dictionary is actually the id function, not the string "id" like you are probably intending.

Also note there was a hard-code "min_duration" and "max_duration" in the input provided which I removed here in this post.

To remove the duration_min and duration_max from the root note, we can add a special case for when "roles" is not present in the node -

def tree_min_max(tree, mm = min_max()):
  if "roles" in tree:
    mm = mm + role_min_max(tree["roles"])
    return {
      "duration_min": mm.min,
      "duration_max": mm.max,
      **tree,
      "nodes": list(tree_min_max(node, mm) for node in tree["nodes"])
    }
  else:
    return {
      **tree,
      "nodes": list(tree_min_max(node, mm) for node in tree["nodes"])
    }

without the min_max class

We could write min_max as a simple function which takes two tuples and outputs a tuple of the combined minimums and maximums -

def min_max(a, b):
  (amin, amax) = a
  (bmin, bmax) = b
  return min(amin, bmin), max(amax, bmax)

Then we update iter_min_max -

def iter_min_max(iterable):
  r = (+inf, -inf)
  for value in iterable:
    r = min_max(r, (value, value))
  return r

In tree_min_max we need to initialize mm to the default min-max and if "roles" is present, update mm with the computed role_min_max. Notice because mm is no longer a class, we cannot access the subfields, mm.min and mm.max. Instead mm is a tuple and the fields are mm[0] and mm[1] -

def tree_min_max(tree, mm = (+inf, -inf)):
  if "roles" in tree:
    mm = min_max(mm, role_min_max(tree["roles"]))
  return {
    "duration_min": mm[0],
    "duration_max": mm[1],
    **tree,
    "nodes": list(tree_min_max(node, mm) for node in tree["nodes"])
  }

This is more cognitive load on the programmer and they need to be careful to initialize a min-max with (+inf, -inf) manually. Using the class avoids this burden and makes it less likely for a mistake to occur.

python find sub tree minimum and maximum value

1 Answers