Discussion :

[Surfoo]

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 php :

Sélectionner tout - Visualiser dans une fenêtre à part

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 php :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !

[Spartacusply]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

[Surfoo]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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"
                }
            }
        }
    }
}]

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
// On retourne l'arbre
return array_values($tree);

[Surfoo]

OK merci, ça fonctionne.

J'ai également fait

Code php :

Sélectionner tout - Visualiser dans une fenêtre à part

array_shift(buildTree($subtree));

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