Discussion :

[Bownobo]

Bonjour,

J'ai pour objectif d'afficher un arbre (arbre n-aire ou arbre généalogique).

J'utilise PHP pour parcourir de façon récursive l'arbre et récupérer pour chaque éléments chacun de ses fils.
Ensuite j'utilise SVG pour afficher le résultat, l'algorithme est en train d'être peaufiné.
Ma question est d'un point de vue POO comment voyez vous le modèle d'un tel arbre. (Un exemple est donné en fichier joint)

Pour ma part je pense créer une classe Object qui est l'entité noeud de mon arbre et peut être une classe Tree qui représente le graphe en entier.

Merci de m'eclairer car je suis un gros débutant en POO!

[metagoto]

La modélisation typique est d'avoir une classe Node (noeud) qui encapsule un noeud ou une feuille, c'est à dire un noeud sans enfants.

Un noeud a possiblement plusieurs noeuds enfants et un unique parent.
Le noeud racine définit l'arbre tout entier, mais rien ne t'empêche d'avoir une class Tree qui contiendrait ce noeud racine et d'autres membres ou méthodes.

Il y a différentes façons d'implémenter ça. Elles diffèrent selon la complexité (algorithmique) nécessaire pour effectuer diverses opérations (parcours, insertion, coupure, déplacement etc).

Le plus simple, en gros, c'est que chaque Node ait un array de Nodes enfants.
Chaque Node a également un Node parent.

Code :

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

1
2
3
4
5
6
7
 
// membres public pour l'exemple
class Node {
  public $parent;
  public $children = array();
  ...
}

Traverser ce genre de tree revient à parcourir les arrays d'enfants de chaque node de manière recursive.

Une autre technique s'appuie sur des listes, non pas d'enfants, mais de "frères" (siblings). Des listes potentiellement doublement chaînée pour pouvoir faire des parcours efficaces.

Code :

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

1
2
3
4
5
6
7
8
class Node {
  public $parent;
  public $next; // frère suivant
  public $prev; // (previous) si doublement chaîné
  public $firstChild; // reference sur le 1er enfant
  public $lastChild; // (optionel) référence sur le dernier enfant
  ...
}

Parcourir ça revient à parcourir les Nodes de proche en proche (avec $next) et les enfants à l'aide de la référence sur le premier enfant de chaque Node ($firstChild)

[Bownobo]

Merci Metagogo pour ces informations pertinentes.

Votre première solution me convient parfaitement mais j'aimerai avoir plusieurs précisions sur votre modèle:

1. Quand vous dites
   

   Un noeud a possiblement plusieurs noeuds enfants et un unique parent.
   Le noeud racine définit l'arbre tout entier, mais rien ne t'empêche d'avoir une class Tree qui contiendrait ce noeud racine et d'autres membres ou méthodes.

   Est ce que cela sous-entend que chaque Node contient tous ses enfants, c'est à dire les enfants des enfants et pas uniquement ses enfants directs. Dans ce cas comment représenter un tel tableau? Est ce un tableau qui contient autant de dimension qu'il y a de 'générations' d'enfants, ou est ce un tableau comme on en retrouve dans les bases de données de type modèle adjacent?
2. Pourriez vous me donner un aperçu des méthodes que l'on peut rencontrer dans une telle représentation de la classe Node?

Merci pour votre aide

[metagoto]

Dans le cadre de la solution avec un simple array de nodes enfants:
Cet array ne contient que les enfants directs.

Pourriez vous me donner un aperçu des méthodes que l'on peut rencontrer dans une telle représentation de la classe Node?

Ca peut être très simpliste (mais ça ne veut pas dire pour autant mauvais), tout comme ça peut être assez évolué avec l'usage du pattern Visitor par exemple.

Exemple d'implémentation:

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
44
45
46
class Node
{
  private $parent;
  private $children = array();
 
  private $data; // simple string ici
 
  public function __construct($data)
  {
    $this->data = $data;
  }
 
  public function addChild(Node $child)
  {
    $child->parent = $this;
    $this->children[] = $child; 
    return $this;
  }
 
  public function traverse($depth = 0)
  {
    echo str_repeat(' ', $depth++).$this->data."\n";
    foreach ($this->children as $child) {
      $child->traverse($depth);
    }
  }  
}
 
/* Le tree pour l'exemple:
electronics
  televisions
    tube
    lcd
    plasma
  portables
*/
$tele = new Node('television');
$tele->addChild(new Node('tube'))
     ->addChild(new Node('lcd'))
     ->addChild(new Node('plasma'));
 
$elec = new Node('electronics');
$elec->addChild($tele)
     ->addChild(new Node('portables'));
 
$elec->traverse(); // affiche le tree

Je dirais que les méthodes importantes pour la classe Node seront celles qui garantissent la bonne cohérence du tree. Dans l'exemple, ça commence par un constructeur et surtout la méthode addChild() plutôt que d'ajouter "manuellement" les nodes enfants dans le array $children, histoire de garantir que les enfants ont bien leurs parents correctement assignés.

Dans l'exemple, la méthode traverse() qui se contente juste d'afficher le $data de chaque node est définie dans la classe Node. Mais ce n'est pas vraiment une bonne solution car on peut se retrouver avec 50 méthodes du même styles pour faire des choses légèrement différentes. Par exemple afficher le tree ou compter le nombre de descendants etc. C'est plus judicieux de garder une classe Node minimaliste et reporter les opérations de parcours et de manipulations des nodes (par exemple, faire un simple echo du $data) dans d'autres composants. La pattern Visitor peux servir à ça. Exemple:

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
interface Visitor
{
  public function visit(Node $node);
}
 
 
// ce visiteur fait un simple echo du $data des nodes
class EchoVisitor implements Visitor
{
  public function visit(Node $node) {
    echo $node->data."\n";
  }
}
 
 
// base class pour des algos de parcours
abstract class Traverser
{
  protected $visitor;
 
  public function __construct(Visitor $visitor) {
    $this->visitor = $visitor;
  }
  // cette méthode devra être implémentée
  abstract public function traverse(Node $node);
}
 
 
// parcour en Depth First Order
class DFO extends Traverser 
{ 
  public function traverse(Node $node)
  {
    // passe la main au visiteur
    $node->accept($this->visitor);
 
    foreach ($node->children as $child) {
      $this->traverse($child);
    }
  }
}
 
 
class Node
{
  public $parent;
  public $children = array();
 
  public $data;
 
  public function __construct($data)
  {
    $this->data = $data;
  }
 
  public function addChild(Node $child)
  {
    $child->parent = $this;
    $this->children[] = $child; 
    return $this;
  }
 
  // visitor
  public function accept(Visitor $visitor)
  {
    $visitor->visit($this);
  }
}
 
// construction du tree
$tele = new Node('television');
$tele->addChild(new Node('tube'))
     ->addChild(new Node('lcd'))
     ->addChild(new Node('plasma'));
 
$elec = new Node('electronics');
$elec->addChild($tele)
     ->addChild(new Node('portables'));
 
// parcour pour un echo
$dfo = new DFO(new EchoVisitor);
$dfo->traverse($elec);

[Bownobo]

Bonjour Metagogo,

Un grand merci à toi pour ce bout de code, je viens de tester la class Node et affiché un var_dump de l'objet. C'est quand même joli le langage objet. Comme je n'ai jamais vraiment codé en objet ton exemple m'apporte beaucoup au niveau de la modélisation objet.

Je vais jeter un oeil au pattern Visitor que tu m'as conseillé:
http://pcaboche.developpez.com/artic...e/?page=page_5

Merci encore