Conversion de la liste des arbres à la hiérarchie dict

Question

J'ai une liste d'éléments avec attrs: parent, niveau, is_leaf_node, is_root_node, is_child_node

.

Je veux convertir cette liste à dict hiérarchie. Exemple de sortie dict:

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

Je ne sais pas l'algorithme. Comment faire?

Answer 1

Voici une version moins sophistiquée récursif comme chmod 700 décrit. Complètement non testé bien sûr:

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

Tout sans parent est votre plus haut niveau, alors assurez-vous ces dicts premier. Ensuite, faites une deuxième passe à travers votre réseau pour trouver tout avec un parent à ce haut niveau, etc ... Il peut être écrit comme une boucle ou une fonction récursive. Vous avez vraiment pas besoin d'aucune des informations fournis en plus « parent ».

Answer 3

On dirait que ce que vous êtes désireux essentiellement à faire est une variante de topologique tri . L'algorithme le plus courante est l'algorithme de suppression source. Le pseudocode ressemblerait à quelque chose comme ceci:

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

Ceci est évidemment cassé en deux endroits (au moins sous forme de code Python réel). Cependant, je l'espère qui vous donnera une idée de la façon dont l'algorithme fonctionne. Notez que cela ne fonctionne pas horriblement s'il y a un cycle dans les articles que vous avez (dire point a a point b en tant que parent alors que le point b a un élément en tant que parent). Mais ce serait sans doute impossible de représenter dans le format que vous êtes désireux de faire de toute façon.

Answer 4

Quelque chose de simple comme cela pourrait fonctionner:

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

d'une manière récursive agréable de le faire:

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