Conversión de lista de árboles a jerarquía dict

Question

Tengo una lista de elementos con attrs: parent, level, is_leaf_node, is_root_node, is_child_node.

Quiero convertir esta lista en dict jerárquica. Ejemplo de dict de salida:

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

no sé algoritmo. ¿Cómo hacerlo?

Answer 1

Aquí hay una versión menos sofisticada y recursiva como chmod 700 descrita. No está comprobado por supuesto:

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

Todo sin un padre es su nivel superior, así que haga primero esos dicts. Luego haga un segundo pase a través de su matriz para encontrar todo con un padre en ese nivel superior, etc ... Podría escribirse como un bucle o una función recursiva. Realmente no necesita ninguna de la información proporcionada además de "padre".

Answer 3

Parece que lo que básicamente quieres hacer es una variante de topological sorting. El algoritmo más común para esto es el algoritmo de eliminación de fuente. El pseudocódigo sería algo como esto:

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]) 

Esto, obviamente, se rompe en un par de lugares (por lo menos tan código Python real). Sin embargo, con suerte que le dará una idea de cómo funcionará el algoritmo. Tenga en cuenta que esto fallará de forma horrible si hay un ciclo en los elementos que tiene (por ejemplo, el elemento a tiene el elemento b como padre, mientras que el elemento b tiene el elemento a como padre). Pero eso probablemente sería imposible de representar en el formato que quieres hacer de todos modos.

Answer 4

Algo simple como esto podría funcionar:

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

una buena manera recursiva para hacerlo:

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