Génération de données arborescentes avec une profondeur donnée

Bonjur,

Je viens vers vous pour un petit problème d’ordre algorithmique que je cherche à implémenter en Python.

Pour une suite de tests, je chercher à générer une structure arborescente de N éléments, et que ces éléments soient répartis sur D niveaux (quand cela est possible). Par « répartis » j’entends que l’arbre soit équilibré. Pour un N et un D donnés, tous les parents devront avoir le même nombre d’enfants à un près (hors nœuds du dernier niveau qui n’auront pas d’enfant, et à l’exception du « dernier » nœud créé). Pas de nœud avec 4 enfants si plusieurs autres dans l’arbre n’en ont que 2.

Un élément est simplement identifié par un identifiant/index et un parent, ou plus simplement par un chemin.

L’idée est par exemple d’avoir, pour N=10 et D=4 la structure suivante :

       0
      / \
     1   8
   /   \  \
  2     5  9
 / \   / \
3   4 6   7

pour N=20 et D=4 :

            0 _
          /    \
    ___ 1        8
   /    | \    /   \
  2     5  J  9     C
 /|\   /|\   /|\   /|\
3 4 F 6 7 G A B H D E I

L’ordre de création des nœuds dans l’arbre importe peu au final. Ici j’ai juste utilisé un algorithme qui récupère comme parent le nœud avec le moins d’enfants, qui est le plus bas dans l’arbre et le plus à gauche.

Le seul point important est d’avoir la structure suivante pour N=4 et D=4 :

0
|
1
|
2
|
3

C’est-à-dire de toujours avoir le nombre de niveaux de profondeur demandé. Dans la mesure du possible bien sûr ($N \geq D$).

Actuellement j’utilise l’algorithme suivant, implémenté en Python.

class Node:
    def __init__(self, n, code, parent=None):
        self.code = code
        self.parent = parent
        self.nb_children = 0

        if parent is None:
            self.depth = 0
            self.left = 0
        else:
            self.depth = parent.depth + 1
            self.left = parent.left * n + parent.nb_children
            parent.nb_children += 1

    @property
    def path(self):
        if self.parent is None:
            return (self.code,)
        else:
            return self.parent.path + (self.code,)


def generate_tree(nb_nodes, depth):
    root = Node(nb_nodes, 0)
    yield root.path

    parents = {root}

    def key(node):
        return node.nb_children, -node.depth, node.left

    for i in range(1, nb_nodes):
        parent = min(parents, key=key)
        node = Node(nb_nodes, i, parent)
        yield node.path
        if node.depth < depth - 1:
            parents.add(node)

Ça fonctionne bien, pas de soucis avec ça, mais ce qui me gêne c’est l’empreinte mémoire et la recherche du parent. J’aurais bien aimé pouvoir calculer l’index du parent juste à partir de l’index du nœud courant, avec une formule type heapq, sans avoir besoin de stocker les parents et de les parcourir pour trouver le bon.

J’ai pensé à une formule qui me donnerait le nombre maximum d’enfants par nœud en fonction de N et D. Je sais avec D=4 que ça va être 1 enfant pour N jusque 4, puis 2 enfants jusque 15, 3 enfants jusque 40, etc.
Et que plus généralement pour N et D on cherche à avoir x enfants par nœud avec x tel que $\sum_{i=0}^{D-1} x^i < N \leq \sum_{i=0}^{D-1} x^i$

Il semble que $\sum_{i=0}^{D-1} x^i = \left\lceil\frac{x^{D}}{x-1}\right\rceil - 1$

Mais je ne sais pas si je peux en faire grand chose.

Enfin voilà, j’aurais voulu savoir si vous aviez des pistes pour résoudre mon problème de façon optimale.
Merci.

Salut,

Une fois que tu as trouvé $x$, le nombre d’enfants par noeud nécessaire, tu peux peut-être stocker les éléments dans un tableau. Si tu es à l’élément d’indice $i$, alors ses enfants sont aux indices $xi + 1, \ldots, xi + x$, et son père est à l’indice $\left \lfloor i/x \right \rfloor$.

EDIT : on a sûrement un truc du genre $D = \lfloor \log_x ( (x - 1) N) \rfloor$, ce qui permet de trouver $x$ en passant à l’exponentielle. Je n’en suis pas certain et je ne suis pas sur mobile, donx je ne détaille pas ; on va dire que c’est laissé en exercice au lecteur.

Résoudre le problème de manière récursive me semble être la solution la plus simple. Vu que tu veux atteindre la profondeur demandé si possible, il faut essayer d’aller le plus profond possible directement et ensuite ajouter d’autres nœuds si besoin.

Pour éviter les cas particuliers, il faut aussi corriger la profondeur demandé si elle est trop faible pour que l’arbre contienne assez de nœuds. Vu que l’on peut avoir $\frac{(D+1)(D+2)}{2}$ nœuds dans un arbre de profondeur D (en utilisant $D=0$ lorsque la racine est seule), si $N > \frac{(D+1)(D+2)}{2}$, alors il faut augmenter $D$ pour avoir $D = \left\lceil\frac{\sqrt{8n + 1} - 3}{2}\right\rceil$.

Globalement, voici l’idée:

def generate_tree(nb_nodes, depth):
  if nb_nodes < 1:
    return None

  if nb_nodes > (depth + 1) * (depth + 2) / 2:
    depth = ceil((sqrt(8 * n + 1) - 3) / 2)
  
  return generate_tree_inner(nb_nodes, 0, depth)

// nb_nodes needs to be > 1.
// It should be possible to fit nb_nodes nodes into a tree of depth max_depth
def generate_tree_inner(nb_nodes, current_depth, max_depth):
  root = Node(0, current_depth)
  if max_depth == current_depth:
    return root
  nb_nodes -= 1
  if nb_nodes == 0:
    return root
  left = generate_tree_inner(nb_nodes, current_depth + 1)
  left.parent = root
  root.left = left
  root.nb_children += left.nb_children + 1
  nb_nodes -= left.nb_children - 1
  if nb_nodes == 0:
    return root
  right = generate_tree_inner(nb_nodes, current_deputh + 1)
  right.parent = root
  root.right = right
  root.nb_children += right.nb_children + 1
  return root

Le code est vraiment pas génial et il y a probablement des bugs, mais ça devrait t’indiquer la direction.

Je comprends pas pourquoi vos algos sont aussi compliqués. Sans aucune condition supplémentaire, j’ai le droit de mettre une branche à gauche et de relier tous les autres noeuds à la racine, non ?

Ajouter la racine 0
pour i de 1 à D-1: Ajouter le noeud i de père i-1
pour i de D à N-1: Ajouter le noeud i de père 0

Voilà, j’ai un arbre à N noeuds de hauteur D !? Si il y a en plus une condition d’équilibrage, il faut préciser exactement ce qu’on veut (équilibrer les niveaux ? seulement les premiers ? le degré des noeuds ? etc.)

Je comprends pas non plus pourquoi « l’empreinte mémoire » (qui est linéaire ici) est un problème si important. Si on fait des représentations en i/2 pour les tas, c’est parce que ça simplifie un peu le code, mais si tes arbres ne sont plus complets, c’est pas une optimisation rentable (à moins que tu travailles avec des données gigantesques, mais j’en doute fort vu le choix très peu optimal de représenter un noeud dans l’arbre par son chemin à la racine).

Une question sans doute plus difficile : comment générer uniformément aléatoirement un arbre à N noeuds de hauteur D en minimisant le nombre de bits aléatoires utilisés ?

Pour éviter les cas particuliers, il faut aussi corriger la profondeur demandé si elle est trop faible pour que l’arbre contienne assez de nœuds. Vu que l’on peut avoir $\frac{(D+1)(D+2)}{2}$ nœuds dans un arbre de profondeur D

?

En effet, je vais voir ce que je peux en tirer, merci. Une fois ce x obtenu je pense pouvoir me débrouiller pour la suite, oui.

Merci pour l’idée, j’essaierai ça aussi.

Par contre je ne comprends pas pourquoi il y aurait une limite sur le nombre de nœuds dans l’arbre (hors cas où D = 1 volontairement exclus). Le nombre d’enfants par nœud n’est pas limité.

Merci pour ta réponse. En effet je cherche à ce que l’arbre soit équilibré, qu’on ne commence pas à ajouter de 4^ème enfant si tous les autres nœuds n’en ont pas déjà 3 par exemple (hors nœuds du D^ème niveau qui n’auront jamais d’enfants).
Mais il n’y aurait pas d’ordre particulier sur quels nœuds équilibrer en premier.

Il faudrait juste que pour N=15, D=4 on ait un arbre de 4 niveaux où chaque parent a 2 enfants, pour N=40, D=4 la même chose avec 3 enfants par parent, etc.
Entre N=16 et N=39 (compris), on aurait des parents avec 2 enfants et d’autres avec 3, peu importe lesquels, mais jamais plus ni moins (et jamais plus de 4 niveaux).

Ce n’est pas une contrainte forte mais ce serait pour moi un plus. J’utilise ici le chemin pour illustrer (et pour le debug parce que c’est plus lisible), mais je n’ai en réalité besoin que de l’identifiant du parent. Identifiant qui peut être numérique et donc ne pas nécessiter d’être stocké dans une liste (simplement recalculé à partir de l’identifiant de l’enfant).

Je ne me suis pas intéressé ici à la génération aléatoire, ce sera peut-être une amélioration future.

Ok c’est plus clair ! Par contre on a toujours le droit de mettre des feuilles à profondeur quelconque ? Si oui, il y a encore une construction simple que tu vas probablement pas trouver satisfaisante : tu pars des noeuds $u_1, \ldots, u_D$ de ta branche de gauche, et tu mets $k$ fils à $u_i$ pour $i\le d_0$ et $k+1$ pour $i>d_0$, et tous les autres sont des feuilles. $k$ et $d_0$ s’expriment en termes de fonctions élémentaires de $D$ et $N$.

Et si c’est pas ce que tu veux, pourquoi dans ton premier exemple 7 n’est pas plutôt un fils de 9 ?

En tout cas, l’algo de ton premier message me paraît maintenant beaucoup plus naturel. Tu devrais le rendre linéaire en temps en stockant une pile pour chaque degré possible (dans la liste des priorités, c’est quand même avant de se débarrasser des pointeurs vers le parent).

Pour l’instant, je vois pas trop ce que tu comptes faire avec ton x (par ailleurs, il n’y a pas de formule directe pour retrouver x, mais l’espace des x intéressants est de taille $N^{1/D}$, donc avec une dichotomie ça prend $\log(N)/D$ de trouver le bon).

J’ai du mal à visualiser ce que ça donnerait. Tu veux dire que seuls les nœuds de la branche de gauche auraient des enfants ? Si c’est le cas je préférerais en effet que le nombre d’enfants par nœud soit plus équitablement réparti sur l’ensemble de l’arbre.

Mon algorithme actuel fonctionne ainsi, il construit l’arbre itérativement, en rajoutant chaque nœud i sur l’arbre généré pour n=i-1. Donc au moment d’ajouter le nœud 7, il n’existe dans l’arbre que ceux de 0 à 6, et 5 est le nœud le plus bas dans l’arbre qui ne possède qu’un enfant, donc il est sélectionné comme parent.

Je me dis qu’en connaissant x je pourrais simplement considérer que chaque nœud i a pour parent $\left\lfloor \frac{i-1}{x} \right\rfloor$ et que ce serait une manière comme une autre d’équilibrer (différente de mon algo actuel mais qui semble satisfaisante).

Edit : En fait en y repensant pas du tout, pour D=4, N=5 ça partirait sur une structure à 2 enfants par nœud et ne me construirait un arbre qui n’aurait que 3 niveaux de profondeur alors que 4 auraient été possibles.
Je vais en effet plutôt voir pour améliorer mon algo existant et éviter de trop me prendre la tête avec ça.

Salut,

Tu peux générer un arbre équilibré et de profondeur fixe en utilisant le nombre de fils maximum qu’un noeud peux avoir (le fameux x) et son corollaire le nombre de noeuds maximum dans un arbre de profondeur D.

J’ai fait un petit programme en Ruby (désolé je ne connais pas assez Python pour le faire de manière rapide). Il gère l’arbre de manière itérative, profondeur par profondeur en utilisant ces 2 variables (children_max et nodes_max dans ce programme).

A chaque itération le nombre de noeuds fils nécessaire est calculé en se basant sur le nombre de noeuds restant. Le nombre de groupes de noeuds fils comportant "children_max-1" noeuds et "children_max" noeuds est ensuite calculé, le nombre de noeuds correspondant est ensuite poussé dans l’arbre, représenté par un tableau donnant le parent de chaque noeud.

def push_nodes(groups, children)
        groups.times do
                children.times do
                        @tree.push(@parent_idx)
                end
                @parent_idx += 1
        end
end

def fixed_depth_tree(depth, queued_nodes)

        # Check arguments
        if depth < 1 || depth > queued_nodes || (depth == 1 && queued_nodes > 1)
                return
        end

        # Compute maximum/minimum number of children per parent
        children_max = 1
        nodes_max = depth
        while nodes_max < queued_nodes
                children_max += 1
                nodes_max = 1
                children = children_max
                (depth-1).times do
                        nodes_max += children
                        children *= children_max
                end
        end
        puts "ChildrenMax #{children_max}"
        children_min = children_max-1

        # Generate tree
        @tree = Array.new.push(queued_nodes)
        @parent_idx = 0
        parent_nodes = 1
        queued_nodes -= 1
        nodes_max = (nodes_max-1)/children_max
        (depth-1).times do
                child_nodes = queued_nodes/nodes_max
                if queued_nodes%nodes_max > 0
                        child_nodes += 1
                end
                if child_nodes < parent_nodes*children_min
                        child_nodes = parent_nodes*children_min
                end
                groups_min = parent_nodes*children_max-child_nodes
                groups_max = parent_nodes-groups_min
                puts "GroupsMin #{groups_min} GroupsMax #{groups_max}"
                push_nodes(groups_min, children_min)
                push_nodes(groups_max, children_max)
                parent_nodes = child_nodes
                queued_nodes -= parent_nodes
                nodes_max = (nodes_max-1)/children_max
        end
        puts "Tree #{@tree}"
end

Le résultat est le suivant pour D=4 et N=20

        ---- 0 ----
      /             \
     1           --- 2 -----
   /   \       /     |       \
  3     4     5      6        7
/  \  /  \  /  \  /  |  \  /  |  \
8  9 10 11 12 13 14 15 16 17 18 19

Les arbres générés "pencheront" légèrement vers la droite si tous les groupes de fils ne sont pas au maximum car ces groupes sont rajoutés en dernier. Il n’y a également que les noeuds au niveau le plus bas qui n’ont pas de fils.

En fait ce programme permet de créer une représentation "canonique" de l’arbre, caractérisé par les données suivantes (toujours pour D=4 et N=20)

ChildrenMax 3
GroupsMin 1 GroupsMax 0
GroupsMin 1 GroupsMax 1
GroupsMin 3 GroupsMax 2

Je pense qu’il n’est pas vraiment nécessaire de générer l’arbre complet avec ce programme. On doit pouvoir déterminer le chemin pour accéder à un noeud quelconque en utilisant cette forme canonique, ce sera juste un peu plus compliqué j’essaierai de faire ça si j’ai un peu de temps.

Cela aurait l’avantage de pouvoir générer des arbres très grands facilement, la complexité dépendant alors de D et non plus de N.

EDIT: Le calcul de children_max pourrait être amélioré également, ici je l’incrémente à partir de 1 jusqu’à ce que la bonne valeur soit trouvée (>= N).

Salut,

Désolé pour le délai de réponse, je n’ai pas eu plus de temps que ça à reconsacrer à ce sujet.

@Karnaj, Effectivement il y a une relation de ce genre mais je ne suis pas sûr que ça me permette de trouver le x minimum pour D fixé. Aussi comme dit ensuite, je ne pense finalement pas pouvoir faire quelque chose de ce x pour construire plus facilement mon arbre.

@Berdes, En regardant de plus près la solution que tu proposes je remarque qu’elle s’axe sur des arbres binaires. Dans mon cas il n’y aurait pas nécessairement 2 enfants par nœud, le nombre d’enfant dépendant justement du nombre de nœuds voulu et de la profondeur.

@fromvega, Merci, j’ai adapté le code vite-fait en Python et ça marche bien, bien plus performant que ma solution (environ 2000× plus rapide) ! J’ai encore quelques passes à faire dessus pour bien tout comprendre, mais c’est pile ce que je cherchais.