3

I have a list of tuples like

list_of_tuples = [(number, name, id, parent_id),
     (number, name, id, parent_id),
    ]

I am trying to sort it into an ordered structure like:

{
    parent: [(id, name), (id, name)],
    parent: {parent: [(id, name)]
{

So, any node could have a parent and/or children I tried with:

tree = defaultdict(lambda: [None, ()])
ancestors = set([item[3] for item in list_of_tuples])

for items in list_of_tuples:
    children_root = {}
    descendants = []
    number, name, id, parent = items
    if parent is None:
        tree[id] = [(id, name)]
    elif parent:
        if parent not in tree.keys():
            node = tree.get(parent)
            node.append((id, name))
        children = (id, name)
        tree[parent].append(children)

But I'm losing deep hierarchy when a node has both a parent and children

How do I make the ordering work correctly?

Garrett Kadillak
  • 1,026
  • 9
  • 18
noise
  • 117
  • 3
  • 14
  • 1
    If you sort the nodes by `parent_id` and start from the leaf nodes up to source nodes, this might simply the problem – Moses Koledoye Sep 14 '16 at 17:01
  • Why not just make a dict with key = id. – stark Sep 14 '16 at 17:11
  • The structure that you're aiming for is a little bit unusual. Usually a tree node has information about the children not the parent. Also what info is relevant for a particular node (as it will be in the tree/ _dict_ )? _id_? _name_? But not _number_? – CristiFati Sep 14 '16 at 17:13
  • id is relevant for every node – noise Sep 14 '16 at 17:14
  • What is the number used for? – gavriel Sep 14 '16 at 17:28
  • the number using for ordering, number is not an important element to be honest – noise Sep 14 '16 at 17:29
  • Do you mean ordering the descendants of a node? If yes, it's kind of important. So (as the simplest example) a node _A_ with 2 descendants _B_ and _C_: can translate int 2 distinct binary trees (pre-order): _ABC_, _ACB_. – CristiFati Sep 14 '16 at 17:38

1 Answers1

3

I propose to represent the tree nodes as tuples ((id, name), dict_of_children).

list_of_tuples = [(1, 'name1', 1, None),
     (2, 'name2', 2, 1),
     (3, 'name3', 3, 1),
     (4, 'name4', 4, 2),
     (5, 'name5', 5, 2),
     (6, 'name5', 6, None),
     (7, 'name5', 7, 6),
    ]

def build_tree(list_of_tuples):
    """
    >>> import pprint
    >>> pprint.pprint(build_tree(list_of_tuples))
    {1: ((1, 'name1'),
         {2: ((2, 'name2'), {4: ((4, 'name4'), {}), 5: ((5, 'name5'), {})}),
          3: ((3, 'name3'), {})}),
     6: ((6, 'name5'), {7: ((7, 'name5'), {})})}
    """
    all_nodes = {n[2]:((n[2], n[1]), {}) for n in list_of_tuples}
    root = {}
    for item in list_of_tuples:
        number, name, id, parent = item
        if parent is not None:
            all_nodes[parent][1][id] = all_nodes[id]
        else:
            root[id] = all_nodes[id]
    return root
gavriel
  • 335
  • 2
  • 10