[Résolu]Dessiner un arbre

Cirdo · février 2015

Bonjour à tous,

Il y a quelque temps, j'ai vu ma famille et je ne savais pas la situé dans l'arbre généalogique familiale. Donc je me suis mis en tête de faire un logiciel qui gère les arbres généalogique.

J'ai commencé un semblant de cahier des charges. Et je me heurte à une question de performance : comment dessiner l'arbre avec ses branches correctement. Je m'explique.

La class Person contient une liste qui représente les enfants, et les enfants sont désignés aussi par la class Person (donc les enfants peuvent avoir des enfants eux aussi). J'ai une variable qui pointe aussi sur la class Person, elle représente le parent du coté de la famille (soit du coté de la mère, soit du coté paternel).

Voici un l'exemple pour un arbre :

AliGator · février 2015

Comment faire pour ajouter les view personview (dans le bonne ordre) en fonction des parents et enfants sans trop se casser la tête ?

Sans trop ce casser la tête, c'est impossible.

La théorie des graphes, et les méthodes pour dessiner un graphe de façon optimale, avec surtout la question de placer les noeuds de l'arbre (les PersonView) au bon endroit pour qu'ils ne se superposent pas, mais que les arcs reliant les noeuds (les traits entre tes personnes) ne se croisent pas non plus dans tous les sens, etc... fait partie d'un sujet à part entière, avec des algos qui ont déjà été étudiés (et que je ne connais pas par coeur) qui ne sont pas forcément des plus simples à inventer soi-même !

En effet, si par exemple une famille a 5 enfants, quand ces 5 enfants sont célibataires, tu les mets côte à côte et ça va, mais si certains sont mariés, il faut décaler les autres enfants pour laisser la place pour la case pour le conjoint. Or, où t'arrêtes-tu dans la généalogie ? Est-ce que tu fais apparaà®tre les parents du conjoins aussi sur l'arbre, par exemple pour que l'enfant A puisse voir sur l'arbre à la fois ses grands parents paternels et maternels ? Si oui, tu mets où les parents du conjoints dans ton arbre, y'a plus trop la place !

Bref ça fait intervenir des calculs qu'il est difficile de mettre au point soi-même, il y a déjà des gens qui ont réfléchi au problème et se sont rendu compte que c'était très loin d'être simple, donc il faut se baser sur leurs travaux. J'ai pas de lien sous la main, mais je te laisse chercher sur le net, en tout cas essaye pas d'imaginer la solution toi-même je pense, car ça devient vite très complexe.

Cirdo · février 2015

Merci de ta réponse

Effectivement c'est compliqué. J'ai pensé à une solution qui est de dessiner les enfants (en haut de l'arbre), ensuite on dessine les enfants du premier enfants, etc. Arrivé en bas de la chaine, on remonte à ses parents, on déjà dessiné ses frères. on dessine les enfants des frères. Puis on remonte.

Je demandais si c'était correct de créé une variable "draw", elle représentera un bool qui dira si on déjà dessiné la Person.

AliGator · février 2015

Alors non la variable "draw" n'est pas une bonne idée.
Il faut plutôt implémenter le pattern Visitor, ou tout simplement utiliser la récursivité pour parcourir ton arbre. Mais ça ne suffira pas de toute façon

Ta méthode de parcours (dessiner les enfants des enfants des enfants, puis remonter et dessiner les frères, etc) correspond à un parcours récursif ce qu'il y a de plus classique : en gros, la méthode draw d'un objet Person va dessiner la personne, puis boucler sur chaque objet Person de sont tableau "enfants" et appeler leur méthode draw tour à tour. Par récursivité, le fait d'appeler le draw sur le premier enfant va en fait dessiner l'enfant... et descendre dessiner les petits-enfants... et c'est seulement arrivé en bas de cette branche qu'on aura fini entièrement tous les enchaà®nements qui ont été déclenchés par le draw du premier enfant de la Person tout en haut et qu'on va du coup commencer le dessin de son frère et ses enfants...

Bref, en algorithme, c'est de la récursivité tout ce qu'il y a de plus standard. Et le problème c'est que justement le concept de dessin d'un graphe (ou plutôt d'un simple arbre dans ton cas, puisque c'en est un, enfin du moins si tu ne commences pas à considérer qu'une personne peut se marier avec un de ses enfants / neveux / nièces et donc qu'on ne peut pas "remonter" dans l'arbre ce qui en ferait devenir un graphe), c'est que pour dessiner un arbre, la récursivité descendante n'est pas une bonne solution.

C'est pour cela que je t'ai conseillé de te renseigner sur les algos existants plutôt que d'essayer de réinventer le tien. Car c'est un sujet très complexe, y'a des mathématiciens qui ont passé vachement de temps sur la question, c'est loin d'être anodin, ça soulève plein de problèmes parfois compliqués, et tu n'arriveras sans doute pas à retrouver les mêmes algos par toi-même.

Par exemple ta solution ne va pas convenir car comment par exemple centrer la case où tu dessines le parent par rapport aux cases représentant ses enfants, alors que tu ne sais pas encore quelle place en largeur vont prendre l'ensemble des cases de ces enfants, car pour le savoir faut justement que tu dessines d'abord les enfants de ces enfants, qui sont peut-être eux aussi mariés (donc il faut prévoir aussi la place pour la case pour le conjoint), etc.

Déroules l'algorithme sur un papier avec un arbre d'exemple tu verras vite le problème. Imagines [A]rnaud et rigitte qui ont eu 3 enfants, [C]édric, [D]idier et [E]lise ; [D]idier s'est marié avec [F]anny et a eu [G]régoire et [H]ector. Avec ton algo, tu vas avoir du mal en commençant par dessiner A et B, car tu ne sauras pas s'il faut les placer plutôt à gauche ou au milieu ou à droite du dessin. Si D ne s'était pas marié, on a un couple de 3 entants, c'est simple, A et B sont dessinés au milieu. Mais là D s'est marié avec F, donc il faut une case à côté de D pour dessiner F, donc en fait sous A et B il y aura 4 cases. Et en plus ces 4 cases si tu continues de descendre tu t'apercevras qu'il ne faut pas qu'elles soient collées côte à côte, car si les enfants G et H de D+F ont eux-même des enfants, il va déjà y avoir un sous-arbre potentiellement conséquent (et large) à dessiner sous D et F, qui va prendre de la place en largeur. Si E se marie elle aussi et a aussi des enfants, faut qu'ils aient la place d'être dessinés sans se chevaucher avec ceux de D+F...

Tu peux partiellement résoudre ce problème en faisant de la récursivité ascendante (dite "bubble up", contrairement à celle que tu proposes qui est bubble-down), en allant d'abord aux tout derniers noeuds (les plus bas) de ton arbre et en remontant progressivement, car tu vas savoir dans le couple qui est le plus bas dans ton arbre de ta branche la plus à gauche combien il y a d'enfants, et donc combien ça va prendre de place en largeur, et donc tu vas savoir combien il faudra de place pour le groupe incluant les parents centrés horizontalement + ses enfants. Et de proche en proche en remontant combien il faudra de place en largeur pour tout le groupe.

Mais là encore ça ne suffit pas et ça pose encore d'autres problèmes, comme le cas où le fils aà®né tout en bas de ton arbre n'a pas d'enfant, mais le fils cadet lui en a, et donc ton arbre ne descend pas aussi bas dans toutes les branches, les branches que tu dessines plus tard pouvant descendre plus bas que celles dessinée avant, et il faut réutiliser l'espace libre en bas du dessin (car sinon ton arbre va faire une taille énorme en largeur avec des grands vides pour rien).

Et j'en passe encore et encore...

Bref, je le redis, le parcours d'arbre et surtout les algos de dessin d'arbres (Tree Layout Algorithms) ont tout un champ qui leur est dédié, avec des gens qui ont passé du temps à réfléchir au problème, à tous les problèmes que ça cause, etc... donc ne va pas t'essayer à inventer ton propre algo, tu risques toujours de tomber sur un cas qui n'ira pas... Ou au mieux qui saura dessiner les cases sans qu'elles se chevauchent mais qui prendra beaucoup + de largeur qu'il n'est nécessaire (bubble-up) avec des grands espaces blancs inutiles, rendant l'arbre illisible car les cases seront trop espacées pour rien.

Je ne vais pas ici tous les algos dispos et les expliquer, c'est un sujet à part qui nécessite pas mal de prérequis, donc je t'invite plutôt à aller lire un bouquin dédié, ou te renseigner sur Google ou Wikipedia et implémenter un algo existant plutôt que d'imaginer des choses qui ne marcheront pas.

Herve · février 2015

Comme ça, sans trop réfléchir, "à l'intuit", ce type de graphique ne me semble pas si compliqué. En somme, sois tu l'inscris dans IB dans une NSScrollView (le plus simple), soit tu crées une fonction mathématique qui mette en verticale ce que tu pensais mettre en horizontale au début. (ou en diagonale)

Les flèches seront faciles à calculer avec NSBezierPath. On comptera facilement l'espace entre deux familles (cad groupes d'enfants).

Plutôt qu'une seule classe "membre", je ferais une classe "famille" faite d'un tableau (NSMutableArray) de "membres" capable d'héberger lui-même une famille. Deux classes plutôt qu'une, de façon à mieux sérialiser le problème. On a peur de boucles sans fin ce faisant. Une classe "Arbre" abritant l'ensemble initialiserait le tout. A voir... Tiens nous au courant, le problème est intéressant.

Cirdo · février 2015

AliGator, tu te compliques la vie pour un rien sur certain point

Pour l'instant, je pense mettre les mariés dans la même view (personview). Par example si Jean se marie avec Ginette, on les mettra dans la view personview, quand on clique sur cette view, on affiche un popover décrivant toutes les informations. Après il faudra faire en sorte de faire comprendre à l'utilisateur qu'ils sont mariés.

Tu as entièrement raison sur le 'bubble-down', il se peut que des views soit affiché sur des view (avec 7 enfants par exemple) avec cette méthode.

Pour remédier à ce problème, on peut essayé de dessiner ligne par ligne : je dessine moi, ma soeur et mes cousins. Pour ça il faut un id ou nombre de positionnement par rapport aux lignes : mon grand-père et ma grand-mère leur id vaut 0, ma mère et ses frères et soeurs leurs id est de 2, les cousins germain et mes frères et soeur ansi que moi, l'id sera 3. L'avantage de cette méthode est qu'on peut gérer l'ajout des personview sans que ça déborde sur la view d'accoté. Un autre problème survient, c'est comment avoir les id et ne pas se mélanger les pinceaux. Enfin un autre problème, c'est comment relier (grâce à bezierPath) les parents à leurs enfants.

Est-ce que tu penses qu'avoir une variable dans la class Person qui pointe sur sa personview en question peut être faisable ?

Il faut plutôt implémenter le pattern Visitor, ou tout simplement utiliser la récursivité pour parcourir ton arbre. Mais ça ne suffira pas de toute façon

Je connaissais pas ce pattern. j'ai lu l'article sur Wikipédia j'ai pas tout bien compris. Je me pencherai sur ce pattern quand j'aurais le temps

Alors non la variable "draw" n'est pas une bonne idée.

C'est bon à savoir.

Merci

Cirdo · février 2015

Tiens nous au courant, le problème est intéressant.

Pas de problème

AliGator · février 2015

Le fait d'avoir la PersonView en propriété dans la classe Person n'est pas non plus une bonne approche, car tu mélanges alors la partie Vue et la partie Model de MVC, avec ton modèle qui a besoin de connaà®tre la vue et vice-versa, donc c'est un anti-pattern.

Sur le même principe, ton idée de la variable draw dans ton modèle mélange M/V du MVC encore une fois.

Et même si tu voulais mettre cette variable "draw" dans ta PersonView pour éviter le mélange M/V, ça reste un mauvais pattern car tu rajoutes un état à ton objet alors que cette propriété n'est utile que pendant le parcours de l'arbre, tu mélanges donc le principe d'état (State) et de parcours. La variable draw restera présente et accessible alors qu'elle n'est utile que dans le contexte / pendant le temps où tu dessines ton arbre (qui n'est qu'une action éphémère). Une fois que ta méthode drawTree() sera finie tu auras une variable (état) inutile et hors contexte.
Au niveau architecture, ce n'est pas une bonne pratique non plus donc. Et en plus je ne vois pas en quoi tu en aurais besoin puisqu'un parcours d'arbre, qu'il soit bubble-up ou bubble-down et fait par Visitor ou autrement, est récursif dans tous les cas (contrairement à un Graphe, où là tu as le problème) donc tu vas forcément parcourir tous tes éléments et une seule fois chacun (et si tu en avais besoin mieux vaut un NSSet de visite géré par la méthode de dessin d'arbre localement).

Cirdo · février 2015

Le fait d'avoir la PersonView en propriété dans la classe Person n'est pas non plus une bonne approche, car tu mélanges alors la partie Vue et la partie Model de MVC, avec ton modèle qui a besoin de connaà®tre la vue et vice-versa, donc c'est un anti-pattern.

Donc, ce n'est pas une bonne idée du tout.

Merci encore pour tes réponses

Cirdo · février 2015

Pour trouver cet id, la solution est assez simple. A la place de parcourir tout l'arbre en bubble-down, on peut le trouver grâce aux button 'ajouter'. Je m'ajoute moi, je sais l'id de mon père grâce à la variable parent qui pointe sur class Person. Ensuite id du parent plus 1 donne mon id.

Si on stock l'id dans la class Person, on mélange modèle et contrôler (qu'on m'arrête si je me trompe ) et c'est de l'anti-pattern. On peut le stocker dans un dictionnaire, l'id est la clé, puis la valeur un array des personne comportant le même id.

Est-ce que c'est une bonne idée ?

Cirdo · février 2015

Voici un code pour afficher l'arbre (pour l'instant sans afficher les branches) :



- (void)awakeFromNib{

_idPerson = [NSMutableDictionary dictionary];

_person = [[GTPerson alloc] init];

_person.name = @Cirdo;

_currentPerson = _person;

[_idPerson setObject:[NSMutableArray arrayWithObject:_person] forKey:@"0"];











}

- (void)addPerson:(GTPerson *)person{

[_currentPerson addEnfants:person]; //On update la variable currentPerson

[_idPerson enumerateKeysAndObjectsUsingBlock:^(NSString *key, id obj, BOOL *stop) {

for (GTPerson *p in obj){

if ([p.name isEqualToString:_currentPerson.name]){//On retrouve la personne dans le dico

NSInteger idPerson =key.integerValue;

idPerson ++;

if (![_idPerson objectForKey:[NSString stringWithFormat:@%ld,(long)idPerson]]){ //Si l'object n'existe pas, donc pas de array en value

[_idPerson setObject:@[;person] forKey:[NSString stringWithFormat:@%ld,(long)idPerson]];



}else{

NSMutableArray *array = [NSMutableArray arrayWithArray:[_idPerson objectForKey:[NSString stringWithFormat:@%ld,(long)idPerson]]];

[array addObject:person];

[_idPerson setObject:array forKey:[NSString stringWithFormat:@%ld,(long)idPerson]];

}

}



}

}];

[self setNeedsDisplay:YES];

}





- (void)drawRect:(NSRect)dirtyRect {

[self setSubviews:@[;]];

/*

On draw la première personne

*/

if (!_viewPersonn){

_viewPersonn = [[GTViewPersonController alloc] init];

}

NSRect bounds = self.bounds;

NSRect boundsView = _viewPersonn.view.bounds;

NSPoint center = NSMakePoint((bounds.size.width/2)-(boundsView.size.width/2), (bounds.size.height - boundsView.size.height));

_viewPersonn.view.frame = NSMakeRect(center.x, center.y, NSWidth(_viewPersonn.view.bounds), NSHeight(_viewPersonn.view.bounds));

_viewPersonn.image.image = _person.portrait;

_viewPersonn.label.stringValue = _person.name;

_viewPersonn.delegate = self;

[self addSubview:_viewPersonn.view];



NSSize totalSize;

NSPoint currentPointEnfant;



NSSize sizeView = _viewPersonn.view.bounds.size;





for (NSString *key in [_idPerson allKeys]){

if ([key isEqualToString:@"0"]){

continue;

}



NSArray *arrayEnfant = [NSArray arrayWithArray:[_idPerson objectForKey:key]];

NSInteger nbEnfant = [arrayEnfant count];

//On calcule la taille total de tous les enfants



totalSize = NSMakeSize((nbEnfant * sizeView.width),  sizeView.height);

NSInteger keyInt = key.integerValue;

keyInt++;

currentPointEnfant = NSMakePoint((bounds.size.width/2)-(totalSize.width/2), bounds.size.height - (sizeView.height * keyInt));



for (GTPerson *person in arrayEnfant){

GTViewPersonController *viewPersonnEnfant =  [[GTViewPersonController alloc] init];



viewPersonnEnfant.view.frame = NSMakeRect(currentPointEnfant.x, currentPointEnfant.y, NSWidth(viewPersonnEnfant.view.bounds), NSHeight(viewPersonnEnfant.view.bounds));

viewPersonnEnfant.image.image = person.portrait;

viewPersonnEnfant.label.stringValue = person.name;

[self addSubview:viewPersonnEnfant.view];

viewPersonnEnfant.delegate = self;



//Pour le prochain on décale

currentPointEnfant = NSMakePoint((currentPointEnfant.x +sizeView.width), currentPointEnfant.y);



}

currentPointEnfant.y += sizeView.height;



}









// Drawing code here.

[[NSColor whiteColor] set];

NSRectFill(dirtyRect);









}







- (void)changeCurrentPersonView:(GTViewPersonController *)viewController{

//On accède à  sa sa view



_currentPerson = nil;



[_idPerson enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {

for (GTPerson *person in obj){

if ([person.name isEqualToString:viewController.label.stringValue]){

_currentPerson = person;

}

}

}];







}

S'il y a des remarques, je suis preneur

AliGator · février 2015

Oh là là ...!!! Au niveau architecture et bonnes pratiques il y a beaucoup à redire !!

Variable d'état (_currentPerson) accessible à l'extérieur du process de parcours. Comme déjà expliqué plus haut, ça n'est pas une bonne pratique. Si tu veux faire de la dépendance ou récursivité ainsi, il faut passer la currentPerson en paramètre quand tu l'appelles depuis ta boucle de parcours, de sorte de ne pas avoir besoin d'un variable d'instance ou propriété qui ne sert que pendant le parcours et n'a aucun sens en dehors. Sinon ça peut vite mener à des états incohérents de ton app au gré des évolutions du code.
Pourquoi comparer les personnes par leur nom et pas leur identité ?? Une personne n'a pas le droit de porter le même nom qu'un autre, comme certains donnent à un enfant le prénom de son grand-père pour rendre hommage ou je ne sais quoi ? Pourquoi diable faire des isEqual sur les name pour savoir si c'est la même personne ? Pourquoi ne pas faire un test identitaire directement sur l'objet GTPerson ([p isEqual:_currentPerson]) mais passer plutôt par le nom pour la comparaison ?! Drôle d'approche...
Pourquoi passer par des clés sous forme de NSString si c'est pour récupérer leur integerValue partout ? Pourquoi ne pas passer par des NSNumber et utiliser @0 plutôt que @"0" ? En plus tu fais des opérations entières dessus ensuite... tout ça pour le retransformer en NSString ensuite une fois que tu as fait idPerson++... Vraiment, c'est pas du tout adapté... bizarre de vouloir utiliser une NSString pour stocker un nombre plutôt que de stocker le nombre directement...
Et d'ailleurs, pourquoi ces clés bizarres ? Pourquoi donner des id incrémentaux obligatoirement à tes noeuds de ton arbre ? Si jamais un jour tatie Jacqueline et oncle Bob ont un autre enfant, que tu dois donc insérer en plein milieu de ton arbre (car ce ne sont pas les derniers noeuds), tu fais comment ? Tu renumérotes tous tes GTPerson un par un ? Et de toute façon je ne vois pas trop l'intérêt de cette clé contre un parcours itératif...
Allocation d'un GTViewPersonController dans le drawRect ? Sérieusement ? Depuis quand on alloue des ViewControllers dans la méthode drawRect, dont le rôle est de dessiner du CoreGraphics, et non de dessiner des vues ? Si tu veux rajouter des vues et des ViewControllers pour construire ton arbre, c'est layoutSubviews qu'il faut utiliser, certainement pas drawRect qui est pour le dessin "à la main" !!
Le reste du code, j'ai un peu sauté plus loin (ça me donnait déjà un peu la nausée...), je vois pas trop comment tu positionnes tes enfants en fonction de leur vue représentant les parents... (enfin si je vois, mais ça ne marche que pour un seul niveau, dès que tu vas y mettre de la récursivité pour avoir + de profondeur dans ton arbre ça ne va plus marcher... et encore moins avec des arbres non réguliers, où chaque noeud/personne n'a pas le même nombre d'enfants et donc la largeur des sous-arbre ne dépend pas que des enfants immédiats mais de tout le sous-arbre lui-même (d'où la nécessité de récursivité bubble-up)...
Et pour terminer (parce que j'ai vite sauté à la fin au bout d'un moment...)... Faire un test sur la partie Vue du MVC pour sélectionner un élément du Modèle... (dans ton changeCurrentPersonView, comparer si person.name est égal au label.stringValue...)... ça m'a achevé... il va falloir sérieusement réviser les bases de MVC !

Désolé je suis un peu virolent, mais j'avoue que j'ai eu du mal, là ...

AliGator · mars 2015

Et puis encore une fois (enfin 3 maintenant) si tu t'évertues à implémenter ton propres algo, tu vas rencontrer beaucoup de problèmes (que tu ne vois probablement pas encore manifestement) sur lesquels d'autres ont déjà planché et trouvé des solutions, donc je ne vois vraiment pas pourquoi tu veux réinventer la roue en terme d'algorithme pour le dessin de ton graphe...

Tiens par exemple rien que pour dessiner ce simple arbre que j'ai mis en pièce-jointe :

Pyroh · mars 2015

Mais tu as l'air têtu à quand même vouloir réinventer un algo, donc après tout c'est peut-être seulement après les avoir rencontré par toi-même après des heures de recherches que tu vas réaliser la complexité de la chose et que tu gagnerais du temps à simplement prendre un algo existant et te baser sur les travaux déjà faits sur le sujet...

Parfois l'apprentissage est à ce prix...

Par contre tu as 100% raison. Et même si sa vision d'ensemble est "valable" pour un arbre rempli séquentiellement il comprendra l'importance d'un algo plus costaud quand il devra modifier le graphe parce que tata Janine n'avait pas 2 mouflets mais 3 en réalité et qu'on avait oublié le cousin Paulin...

Draken · mars 2015

Sans parler des enfants illégitimes cachés ici et là dans le décor.

Cirdo · mars 2015

Vu la violence de AliGator, je vais réviser mvc et me cacher sur ma planète

Plus sérieusement, j'ai fait mes tests pour ce projet, voir de moi même où je pouvais aller (c'est peut être pour ça que j'ai pas écouté AliGator et j'en suis sincèrement désolé). Je pense que je n'irai pas plus là car AliGator à raison, l'algorithmes est très complexes à réaliser tout seul. Il me faut d'avantage de connaissance et de pratique. Il y a plein de chose que je ne savais pas comme on n'ajoute pas des viewController dans drawRect mais dans layoutSubview.

Mais j'ai commencé à comprendre MVC.

Mais tu as l'air têtu à quand même vouloir réinventer un algo, donc après tout c'est peut-être seulement après les avoir rencontré par toi-même après des heures de recherches que tu vas réaliser la complexité de la chose et que tu gagnerais du temps à simplement prendre un algo existant et te baser sur les travaux déjà faits sur le sujet...

L'apprentissage est plus fort que tout parfois

Par contre tu as 100% raison. Et même si sa vision d'ensemble est "valable" pour un arbre rempli séquentiellement il comprendra l'importance d'un algo plus costaud quand il devra modifier le graphe parce que tata Janine n'avait pas 2 mouflets mais 3 en réalité et qu'on avait oublié le cousin Paulin...

Je pense que j'ai compris mon erreur. La prochaine je réfléchirai plus avant de me lancer dans un projet aussi dur.

samir · mars 2015

@Cidro Aligator ne te dit pas que c'est impossible à faire. Il te dit juste de regarder des algorithmes qui existe sur internet et les implémenter en Objective C ( il se trouve qu'ils existent même en Objective C).

Ou bien tu peux trouver décas une lib qui facilite ce travail.

Je t'encourage à faire des recherches sur le sujet et implémenter une solution .

Cirdo · mars 2015

Bon, je vais pas tenté de corriger le code... J'essayerai reprendre le projet dans quelques années. Je vais me pencher sur mvc.

Je met le poste en résolu.

[Résolu]Dessiner un arbre

Réponses