Conversione lista albero alla gerarchia dict

Question

Ho una lista di elementi con attrs: genitore, livello, is_leaf_node, is_root_node, is_child_node

.

voglio convertire questo elenco alla gerarchia dict. Esempio di dict uscita:

{
        'Technology':
            {
             'Gadgets':{},
             'Gaming':{},
             'Programming':
                {
                    'Python':{},
                    'PHP':{},
                    'Ruby':{},
                    'C++':{}
                },
             'Enterprise':{},
             'Mac':{},
             'Mobile':{},
             'Seo':{},
             'Ui':{},
             'Virtual Worlds':{},
             'Windows':{},
            },
        'News':{
            'Blogging':{},
            'Economics':{},
            'Journalism':{},
            'Politics':{},
            'News':{}
            },}

Non so algoritmo. Come farlo?

Answer 1

Ecco un meno sofisticato, versione ricorsiva come chmod 700 descritto. Completamente testati ovviamente:

def build_tree(nodes):
    # create empty tree to fill
    tree = {}

    # fill in tree starting with roots (those with no parent)
    build_tree_recursive(tree, None, nodes)

    return tree

def build_tree_recursive(tree, parent, nodes):
    # find children
    children  = [n for n in nodes if n.parent == parent]

    # build a subtree for each child
    for child in children:
        # start new subtree
        tree[child.name] = {}

        # call recursively to build a subtree for current node
        build_tree_recursive(tree[child.name], child, nodes)

Answer 2

Il tutto senza un genitore è il vostro livello superiore, in modo da rendere questi dicts prima. Poi fare un secondo passaggio attraverso l'array di trovare tutto con un genitore a quel livello superiore, ecc ... Si potrebbe essere scritto come un loop o una funzione ricorsiva. Davvero non è necessario alcun delle informazioni fornite oltre "genitore".

Answer 3

Sembra che quello che stai fondamentalmente voler fare è una variante del topologica di smistamento . L'algoritmo più comuni per questo è l'algoritmo di allontanamento di tale sorgente. Il pseudocodice sarebbe simile a questa:

import copy
def TopSort(elems): #elems is an unsorted list of elements.
    unsorted = set(elems)
    output_dict = {}
    for item in elems:
        if item.is_root():
            output_dict[item.name] = {}
            unsorted.remove(item)
            FindChildren(unsorted, item.name, output_dict[item.name])
    return output_dict

def FindChildren(unsorted, name, curr_dict):
    for item in unsorted:
        if item.parent == name:
            curr_dict[item.name] = {}
            #NOTE:  the next line won't work in Python.  You
            #can't modify a set while iterating over it.
            unsorted.remove(item)
            FindChildren(unsorted, item.name, curr_dict[item.name])

Questo, ovviamente, è suddiviso in un paio di posti (almeno per quanto codice Python reale). Tuttavia, si spera che vi darà un'idea di come l'algoritmo funziona. Si noti che questo non riuscirà orribilmente se c'è un ciclo negli elementi che si hanno (dire oggetto un oggetto ha b come un genitore mentre la voce b ha prodotto un come un genitore). Ma allora sarebbe probabilmente impossibile per rappresentare nel formato hai intenzione di fare comunque.

Answer 4

Qualcosa di semplice come questo potrebbe funzionare:

def build_tree(category_data):
  top_level_map = {}
  cat_map = {}
  for cat_name, parent, depth in cat_data:
    cat_map.setdefault(parent, {})
    cat_map.setdefault(cat_name, {})
    cat_map[parent][cat_name] = cat_map[cat_name]
    if depth == 0:
      top_level_map[cat_name] = cat_map[cat_name]

  return top_level_map

Answer 5

un modo ricorsivo bello farlo:

def build_tree(elems):
  elem_with_children = {}

  def _build_children_sub_tree(parent):
      cur_dict = {
          'id': parent,
          # put whatever attributes here
      }  
      if parent in elem_with_children.keys():
          cur_dict["children"] = [_build_children_sub_tree(cid) for cid in elem_with_children[parent]]
      return cur_dict

  for item in elems:
      cid = item['id']
      pid = item['parent']
      elem_with_children.setdefault(pid, []).append(cid)

  res = _build_children_sub_tree(-1) # -1 is your root
  return res