Algorithmie et récursivité

Version imprimable

Bonsoir !

Voilà j'ai un petit problème d'algorithmie et de récursivité et je ne sais pas trop comment m'en sortir..

Je veux dessiner ce graphe : http://bl.ocks.org/mbostock/raw/4063550/ et le json correspondant est celui ci : http://bl.ocks.org/mbostock/raw/4063550/flare.json
Seul "name" et "children" m'intéressent, pas "size".
Je reçois de ma base de données un nom et la profondeur associé dans l'arbre, le tout est ordonnée correctement :

Voilà un exemple de donnée que je reçois, traduit en un tableau PHP :
j'ai bougé volontairement la valeur de "name", pour qu'on voit bien l'arbre se dessiner.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
$subtree = [
  ['name' => 'ELECTRONICS',             'depth' => 0],
  ['name' =>    'TELEVISIONS',          'depth' => 1],
  ['name' =>        'TUBE',             'depth' => 2],
  ['name' =>        'LCD',              'depth' => 2],
  ['name' =>        'PLASMA',           'depth' => 2],
  ['name' =>    'PORTABLE ELECTRONICS', 'depth' => 1],
  ['name' =>        'MP3 PLAYERS',      'depth' => 2],
  ['name' =>            'FLASH',        'depth' => 3],
  ['name' =>        'CD PLAYERS',       'depth' => 2],
  ['name' =>        '2 WAY RADIOS',     'depth' => 2]
];

J'avais donc commencé un bout de code comme ça, mais ça ne fonctionne pas comme je veux bien sur...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
function buildTree($data) {
    $tree    = [];
    $current = 0;
 
    foreach ($data as $key => $child) {
        // Root
        if ($key == $current) {
            $tree['name'] = $child['name'];
            $lastLevel    = $child['depth'];
            $lastKey      = $key;
        // Child
        } elseif(($lastKey + 1) == $key && $child['depth'] == ($lastLevel + 1)) {
            //echo $key." -> " . $child['name'].": ".$child['depth']." == ".($lastLevel + 1)."\n";
            if (!isset($tree['children'])) {
                $tree['children'] = [];
            }
            $tree['children'][] = buildTree(array_slice($data, $key));
            $current++;
        }
    }
 
    return $tree;
}
 
$tree = buildTree($subtree);
 
print_r($tree);
 
//json_encode après..

Ce n'est sûrement pas un bon début de solution, alors s'il quelqu'un est fort en algo, un petit coup de pouce ne serait pas de refus..

Merci !

Salut, voici un algo qui pourrait te convenir (le code est documenté pour expliquer ce qui se passe) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function buildTree($datas) {
    //Utilisation d'array_values pour être sûr que l'on ai des clefs numériques et successives
    $datas = array_values($datas);
 
    //Initialisation de l'arbre vide
    $tree = [];
 
    //On parcours l'ensemble du tableau (pas avec foreach car on va modifier ce tableau dans la boucle)
    while (list($key, $data) = each($datas)) {
        //On ajoute l'élément courant dans l'arbre
        $tree[$key]['name'] = $data['name'];
 
        //S'il y a un suivant et que c'est un fils
        if (isset($datas[$key + 1]['depth']) AND $datas[$key + 1]['depth'] > $data['depth']) {
            //On récupère tous les éléments se situant après celui-ci (éléments susceptibles d'être fils)
            $elsAfter = array_slice($datas, 1, NULL, true);
 
            // On initialise les fils
            $childrens = [];
            //On parcours les éléments se situant après dans le tableau
            foreach ($elsAfter as $k => $elAfter) {
                // Si le "depth" est inférieur ou égal à l'élément actuel, c'est que ce n'est pas un fils de l'élément courant :
                // Du coup, forcément les autres éléments qui se situent après non plus, donc on sort de la boucle
                // On est sur que ce ne sera pas le cas au premier tour car on a fait le test dans le if du dessus
                if ($elAfter['depth'] <= $data['depth']) {
                    break;
                }
                // On rajoute l'élément en tant que fils
                $childrens[] = $elAfter;
                //En on l'enlève des datas car justement c'est un fils
                unset($datas[$k]);
            }
            // On construit l'arbre des fils
            $tree[$key]['children'] = buildTree($childrens);
        }
 
        // L'élément courant a été tiré, on le supprime des datas
        unset($datas[$key]);
    }
 
    // On retourne l'arbre
    return $tree;
}

Oh super Spartacusply, c'est exactement ça ! Et en plus c'est très clair avec tes commentaires, merci !

Par contre, rien à voir du sujet initial maintenant, mais quand je fais le json_encode j'obiens les données avec les index du tableau et le tout est contenu est dans un tableau, et forcément d3js m'envoie bouler.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
[{
    "name": "ELECTRONICS",
    "children": {
        "0": {
            "name": "TELEVISIONS",
            "children": [{
                "name": "TUBE"
            }, {
                "name": "LCD"
            }, {
                "name": "PLASMA"
            }]
        },
        "4": {
            "name": "PORTABLE ELECTRONICS",
            "children": {
                "0": {
                    "name": "MP3 PLAYERS",
                    "children": [{
                        "name": "FLASH"
                    }]
                },
                "2": {
                    "name": "CD PLAYERS"
                },
                "3": {
                    "name": "2 WAY RADIOS"
                }
            }
        }
    }
}]

30/09/2014, 13h22
Spartacusply
Ah oui en effet, c'est du parce que les index sur le premier niveau ne sont pas forcément successifs. Pour corriger ça, il te suffit de le réindexer (avec "array_values") en le retournant :
Code:

1 2 // On retourne l'arbre return array_values($tree);
30/09/2014, 14h17
Surfoo

OK merci, ça fonctionne.

J'ai également fait

Code:

array_shift(buildTree($subtree));

pour retourner le premier index du tableau et faire le json_encode sur ce contenu.