arbre par représentation intervallaire

[peuf23]

Bonjour à tous,

Voilà de quoi prendre un peu la tête à ceux qui aiment se la prendre.

Je suis en train de mettre en place un module de généalogie sur mon site personel et pour rendre le truc un peu plus fun, j'aimerais mettre en place un peu d'interactivité. Comment? simplement en ajustant l'arbre en fonction du nom sur lequel on clique...

Donc j'ai commencé par créer un table avec les personnes qui composent mon arbre avec des champs pour le père, la mère, les fils (et les frères et soeurs). Si je ne connais pas le père ou la mère de qqun ou si il n'y a pas de fils le champ correspondant est NULL.

Je truncate une table temporaire et je construis ma généalogie dans cette même table qui comporte l'id, la génération, la borne gauche, droite, la coordonnée par rapport à la gauche, la coordonnée par rapport au haut. Je pars donc de moi-même génération 0. Borne gauche=0, facile. Je trouve mon père et ma mère. Et là ca se complique
Pouvez-vous m'aider à trouver un algo qui parcours les parents jusqu'à trouver une valeur NULL et attribuer les bonnes valeurs aux bornes gauches et droites???

Pas facile, hein!! Je vous l'avais dis...

Merci d'avance pour vos réponses...

[Mr N.]

A mon avis ton schéma de départ n'est pas terrible. Pourquoi ne pas gèrer directement ton arborescence ? Ca t'éviterait de créer une table temporaire à chaque fois.
Ensuite ton arbre n'est pas un arbre. Rien n'empeche la consanguinité...
Donc tu as un graphe. Donc la représentation intervallaire n'est pas à l'ordre du jour. Donc tu n'as plus de problèmes.
Enfin... il te reste juste à définir un nouveau modèle

[peuf23]

Tu as une idée de schéma de départ plus approprié??
Je suis d'accord que la représentation intervallaire n'est pas forcement la plus approprié pour les parents, mais pour les enfants c'est une autre histoire, non?
Et comme je veux tout traiter en une fois...

Pourquoi ne pas gèrer directement ton arborescence ? Ca t'éviterait de créer une table temporaire à chaque fois.

Comment vois-tu la chose?????

[Mr N.]

Envoyé par peuf23

Je suis d'accord que la représentation intervallaire n'est pas forcement la plus approprié pour les parents, mais pour les enfants c'est une autre histoire, non?

non

Regarde la figure suivante :

Tu comprendras qu'il est difficile de définir les bornes dans le deuxième cas... Pas d'arbre, pas de représentation intervallaire.

C'est un peu difficile de reflechir à une solution à ton problème, surtout que c'est le week-end ^^ Je dirais cependant que :
1 personne possède au plus une mère et au plus un père. (biologique. je laisse de coté les autre cas)

D?onc je dirais :
PERSONNES(id, nom, prenom, date_naissance, date_deces, mere_id, pere_id)

Je ne sais pas si ton arbre généalogique est conséquent mais je pense que tu peux le charger d'un bloc à chaque fois.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Personne {
   function Personne ($id, $nom, $mere_id, $pere_id) {
      $this->id = $id;
      $this->nom = $nom;
      $this->mere_id = $mere_id;
      $this->pere_id = $pere_id;
      $this->enfants = array();
   }
}
 
$les_personnes = array();
 
$req = mysql_query("SELECT * FROM personnes");
while ($data = mysql_fetch_assoc($req)) {
   $les_personnes[$data['id']] = new Personne($data['id'], ...);
}
 
//On ajoute les enfants
foreach($les_personnes as $personne) {
   if ($personne->mere_id) $les_personnes[$personne->mere_id]->enfants[$personne->id] = $personne->id;
   if ($personne->pere_id) $les_personnes[$personne->pere_id]->enfants[$personne->id] = $personne->id;
}

Ensuite à partir d'un id, on peut avoir ses parents, ses enfants, ses freres.