Comment créer un arbre à partir d'une liste de sous-arbres ?

Question

Considérons que nous avons un tas de sous-contraintes qui ressemblent à ceci :

subtree1 = {
    "id": "root",
    "children": [
        {
            "id": "file",
            "caption": "File",
            "children": []
        },
        {
            "id": "edit",
            "caption": "Edit",
            "children": []
        },
        {
            "id": "tools",
            "caption": "Tools",
            "children": [
                {
                    "id": "packages",
                    "caption": "Packages",
                    "children": []
                }
            ]
        },
        {
            "id": "help",
            "caption": "Help",
            "children": []
        },
    ]
}

subtree2 = {
    "id": "root",
    "children": [
        {
            "id": "file",
            "caption": "File",
            "children": [
                {"caption": "New"},
                {"caption": "Exit"},
            ]        
        }
    ]
}

subtree3 = {
    "id": "root",
    "children": [
        {
            "id": "edit",
            "children": [
                {"caption": "Copy"},
                {"caption": "Cut"},
                {"caption": "Paste"},
            ]
        },
        {
            "id": "help",
            "children": [
                {"caption": "About"},
            ]
        }
    ]
}

subtree4 = {
    "id": "root",
    "children": [
        {
            "id": "edit",
            "children": [
                {
                    "id": "text",
                    "caption": "Text",
                    "children": [
                        { "caption": "Insert line before" },
                        { "caption": "Insert line after" }
                    ]
                }
            ]
        }
    ]
}

J'essaie de comprendre comment coder un merge en procédant par exemple de la manière suivante :

tree0 = merge(subtree1, subtree2)
tree0 = merge(tree0, subtree3)
tree0 = merge(tree0, subtree4)

produira :

tree0 = {
    "id": "root",
    "children": [
        {
            "id": "file",
            "caption": "File",
            "children": [
                {"caption": "New"},
                {"caption": "Exit"},
            ]   
        },
        {
            "id": "edit",
            "caption": "Edit",
            "children": [
                {"caption": "Copy"},
                {"caption": "Cut"},
                {"caption": "Paste"},
                {
                    "id": "text",
                    "caption": "Text",
                    "children": [
                        { "caption": "Insert line before" },
                        { "caption": "Insert line after" }
                    ]
                }
            ]
        },
        {
            "id": "tools",
            "caption": "Tools",
            "children": [
                {
                    "id": "packages",
                    "caption": "Packages",
                    "children": []
                }
            ]
        },
        {
            "id": "help",
            "caption": "Help",
            "children": [
                {"caption": "About"},
            ]
        },
    ]
}

mais en faisant quelque chose comme ça :

tree1 = merge(subtree1, subtree2)
tree1 = merge(tree1, subtree4)
tree1 = merge(tree1, subtree3)

produirait :

tree1 = {
    "id": "root",
    "children": [
        {
            "id": "file",
            "caption": "File",
            "children": [
                {"caption": "New"},
                {"caption": "Exit"},
            ]   
        },
        {
            "id": "edit",
            "caption": "Edit",
            "children": [
                {
                    "id": "text",
                    "caption": "Text",
                    "children": [
                        { "caption": "Insert line before" },
                        { "caption": "Insert line after" }
                    ]
                },
                {"caption": "Copy"},
                {"caption": "Cut"},
                {"caption": "Paste"},
            ]
        },
        {
            "id": "tools",
            "caption": "Tools",
            "children": [
                {
                    "id": "packages",
                    "caption": "Packages",
                    "children": []
                }
            ]
        },
        {
            "id": "help",
            "caption": "Help",
            "children": [
                {"caption": "About"},
            ]
        },
    ]
}

Autrement dit, le chargement des sous-arbres dans le même ordre produira toujours le même arbre, mais si vous utilisez la même liste de sous-arbres dans un ordre différent, vous n'êtes pas assuré de produire le même arbre (car les listes d'enfants peuvent être étendues dans un ordre différent).

J'ai déjà essayé de coder cela, mais je ne sais pas comment faire. merge et c'est là ma question. Quelqu'un pourrait-il fournir le code/pseudocode/explication pour que je puisse le mettre en œuvre ?

PS : Vous trouverez ci-dessous quelques tentatives aléatoires que je pensais pouvoir mener à la victoire.

if __name__ == '__main__':
    from collections import defaultdict

    subtree1 = {
        "id": "root",
        "children": [
            {
                "id": "file",
                "caption": "File",
                "children": []
            },
            {
                "id": "edit",
                "caption": "Edit",
                "children": []
            },
            {
                "id": "tools",
                "caption": "Tools",
                "children": [
                    {
                        "id": "packages",
                        "caption": "Packages",
                        "children": []
                    }
                ]
            },
            {
                "id": "help",
                "caption": "Help",
                "children": []
            },
        ]
    }

    subtree2 = {
        "id": "root",
        "children": [
            {
                "id": "file",
                "caption": "File",
                "children": [
                    {"caption": "New"},
                    {"caption": "Exit"},
                ]
            }
        ]
    }

    subtree3 = {
        "id": "root",
        "children": [
            {
                "id": "edit",
                "children": [
                    {"caption": "Copy"},
                    {"caption": "Cut"},
                    {"caption": "Paste"},
                ]
            },
            {
                "id": "help",
                "children": [
                    {"caption": "About"},
                ]
            }
        ]
    }

    subtree4 = {
        "id": "root",
        "children": [
            {
                "id": "edit",
                "children": [
                    {
                        "id": "text",
                        "caption": "Text",
                        "children": [
                            {"caption": "Insert line before"},
                            {"caption": "Insert line after"}
                        ]
                    }
                ]
            }
        ]
    }

    lst = [
        subtree1,
        subtree2,
        subtree3,
        subtree4
    ]

    def traverse(node, path=[]):
        yield node, tuple(path)

        for c in node.get("children", []):
            path.append(c.get("id", None))
            yield from traverse(c)
            path.pop()

    # Levels & Hooks
    dct_levels = defaultdict(list)
    dct_hooks = defaultdict(list)
    for subtree in lst:
        for n, p in traverse(subtree):
            if p not in dct_levels[len(p)]:
                dct_levels[len(p)].append(p)
            dct_hooks[p].append(n)

    print(dct_levels)
    print(dct_hooks[("file",)])

    # Merge should happen here
    tree = {
        "id": "root",
        "children": []
    }

    for level in range(1, max(dct_levels.keys()) + 1):
        print("populating level", level, dct_levels[level])

mais je ne suis pas sûr de créer les bonnes structures / aides car le fonctionnement de l'algorithme n'est pas encore clair... c'est l'objet de cette question.

Answer 1

Testé avec vos exemples sur Python 3.5.

from copy import deepcopy

def merge(x: dict, y: dict) -> dict:
    'Merge subtrees x y, and return the results as a new tree.'
    return merge_inplace(deepcopy(x), y)

def merge_inplace(dest: dict, src: dict) -> dict:
    'Merge subtree src into dest, and return dest.'

    # perform sanity checks to make the code more rock solid
    # feel free to remove those lines if you don't need
    assert dest.get('id'), 'Cannot merge anonymous subtrees!'
    assert dest.get('id') == src.get('id'), 'Identity mismatch!'

    # merge attributes
    dest.update((k, v) for k, v in src.items() if k != 'children')

    # merge children
    if not src.get('children'):  # nothing to do, so just exit
        return dest
    elif not dest.get('children'):  # if the children list didn't exist
        dest['children'] = []  # then create an empty list for it

    named_dest_children = {
        child['id']: child
        for child in dest['children']
        if 'id' in child
    }
    for child in src['children']:
        if 'id' not in child:  # anonymous child, just append it
            dest['children'].append(child)
        elif child['id'] in named_dest_children:  # override a named subtree
            merge_inplace(named_dest_children[child['id']], child)
        else:  # create a new subtree
            dest['children'].append(child)
            named_dest_children[child['id']] = child
    return dest

Answer 2

Vous pouvez utiliser itertools.groupby avec récursivité :

from itertools import groupby
def merge(*args):
   if len(args) < 2 or any('id' not in i for i in args):
      return list(args)
   _d = [(a, list(b)) for a, b in groupby(sorted(args, key=lambda x:x['id']), key=lambda x:x['id'])]
   return [{**{j:k for h in b for j, k in h.items()}, 'id':a, 'children':merge(*[i for c in b for i in c['children']])} for a, b in _d]

---

Via args Cette solution traite chaque dictionnaire transmis comme un membre d'un groupe de dictionnaires. children liste. Cela permet de tenir compte de la possibilité que deux dictionnaires ou plus soient transmis à merge qui ont des id s i.e {'id':'root', 'children':[...]} y {'id':'root2', 'children':[...]} . Ainsi, cette solution renverrait une liste de [{'id':'root', 'children':[...]}, {'id':'root2', 'children':[...]}] , en tant qu'entité distincte id n'offrent pas la possibilité d'un jumelage. Comme les s dict con id 'root' :

import json
tree0 = merge(subtree1, subtree2)[0]
tree0 = merge(tree0, subtree3)[0]
tree0 = merge(tree0, subtree4)[0]
print(json.dumps(tree0, indent=4))

O

{
  "id": "root",
  "children": [
    {
        "id": "edit",
        "caption": "Edit",
        "children": [
            {
                "caption": "Copy"
            },
            {
                "caption": "Cut"
            },
            {
                "caption": "Paste"
            },
            {
                "id": "text",
                "caption": "Text",
                "children": [
                    {
                        "caption": "Insert line before"
                    },
                    {
                        "caption": "Insert line after"
                    }
                ]
            }
        ]
    },
    {
        "id": "file",
        "caption": "File",
        "children": [
            {
                "caption": "New"
            },
            {
                "caption": "Exit"
            }
        ]
    },
    {
        "id": "help",
        "caption": "Help",
        "children": [
            {
                "caption": "About"
            }
        ]
    },
    {
        "id": "tools",
        "caption": "Tools",
        "children": [
            {
                "id": "packages",
                "caption": "Packages",
                "children": []
            }
        ]
      }
   ]
}