Arbre phylogenetique - python

Bonjour,

Lors d'un de mes projets scolaires, il m'est demandé d'implémenter une fonction qui affiche un arbre phylo de manière agréable à lire.

C'est à dire qu'un arbre de ce type :
Pièce jointe 143831

devra être affiché de la sorte :

Pièce jointe 143834

En essayant de passer par une fonction chapeau j'ai écris ca :

Code:

---

1 2 3 4 5 6 7 8 9

def profondeur(monarbre,i): if tree == None : return 0 else: (u,fg,fd) = monarbre print "+" print /"| "*(profondeur(fg,i+1)-1) "|--+ " profondeur(fg,i+1) profondeur (fd,i+1)

---

Je n'arrive pas a debugger mon code. Si jamais je pouvais avoir un tuyau.. Merci!

Salut,

dans la ligne suivante:

Code:

---

print /"| "*(profondeur(fg,i+1)-1) "|--+ " profondeur(fg,i+1)

---

• le "/" est en trop
• il faut concaténer tes chaines de caractères ou mettre une virgule entre 2

les erreurs successives qu'on obtient en essayant de lancer un fichier contenant juste ta fonction fournissent de bons indices:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

File "./arbre.py", line 9 print /"| "*(profondeur(fg,i+1)-1) "|--+ " profondeur(fg,i+1) ^ SyntaxError: invalid syntax ... File "./arbre.py", line 9 print "| "*(profondeur(fg,i+1)-1) "|--+ " profondeur(fg,i+1) ^ SyntaxError: invalid syntax ... File "./arbre.py", line 9 print "| "*(profondeur(fg,i+1)-1) + "|--+ " profondeur(fg,i+1) ^ SyntaxError: invalid syntax

---

Bonjour,

Citation:

---

Envoyé par Tryph

Salut,

dans la ligne suivante:

Code:

---

print /"| "*(profondeur(fg,i+1)-1) "|--+ " profondeur(fg,i+1)

---

• le "/" est en trop
• il faut concaténer tes chaines de caractères ou mettre une virgule entre 2

---

du coup j'ai écrit ca :

Code:

---

1 2 3 4 5 6 7 8 9

def profondeur(monarbre,i): if tree == None: return 0 else: (u,fg,fd) = monarbre print "+ " + str(u) print "| " *(profondeur(fg,i+1)-1) + "|--+ " + str(profondeur(fg,i+1)) profondeur(fd,i+1)

---

et du coup au final quand je veux afficher mon arbre comme demandé :

Code:

---

1 2 3

def prettyprint(monarbre,0) profondeur(monarbre,0)

---

Mais je semble toujours avoir un problème..

Traverser une arborescence est un problème intéressant et tu as déjà compris que tu devais le faire avec une fonction récursive.

Mais il faudrait nous montrer l'arbre en question et aussi le résultat que tu obtiens parce que la simple phrase "Mais je semble toujours avoir un problème" ça ne nous dit rien.

Salut,

c'est déjà bien, la définition de la fonction ne lève plus d'erreur.
le problème c'est que tu ne nous dis pas quel est ton problème et que tu ne nous fourni pas d'exemple d'arbre pour tester.
dans ces conditions c'est difficile de t'aider.

fourni nous un exemple d'arbre à afficher et explique nous quel est le problème que tu constates.

Citation:

---

Envoyé par Tryph

Salut,

c'est déjà bien, la définition de la fonction ne lève plus d'erreur.
le problème c'est que tu ne nous dis pas quel est ton problème et que tu ne nous fourni pas d'exemple d'arbre pour tester.
dans ces conditions c'est difficile de t'aider.

fourni nous un exemple d'arbre à afficher et explique nous quel est le problème que tu constates.

---

Citation:

---

Envoyé par VinsS

Mais il faudrait nous montrer l'arbre en question et aussi le résultat que tu obtiens parce que la simple phrase "Mais je semble toujours avoir un problème" ça ne nous dit rien.

---

Salut,

pour vous répondre, l'arbre que je voudrais testé est le suivant :
Pièce jointe 143972

et je l'ai codé de cette façon :

Code:

---

1 2 3 4 5

monarbre = ( ("A",0), (("B",0.15), (("C",0.22), None, None), (("D",0.12), None, None)), (("E",0.2), (("F",0.18), None, None), (("G",0.22), None, None)))

---

quand je teste juste ma fonction profondeur j'obtiens ceci :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

>>> profondeur(monarbre,0) + ('A', 0) + ('B', 0.15) + ('C', 0.22) |--+ 0 Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 7, in profondeur File "<stdin>", line 7, in profondeur TypeError: unsupported operand type(s) for -: 'NoneType' and 'int'

---

alors que je devrai avoir ceci : Pièce jointe 143974

de plus quand j'essaye d'utiliser ma fonction profondeur comme fonction chapeau j'obtiens une erreur :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

def prettyprint(monarbre,0): profondeur(monarbre,0)   >>> def prettyprint(monarbre,0): File "<stdin>", line 1 def prettyprint(monarbre,0): ^ SyntaxError: invalid syntax >>> profondeur(monarbre,0) File "<stdin>", line 1 profondeur(monarbre,0) ^ IndentationError: unexpected indent

---

Merci

Salut,

Citation:

---

Envoyé par chlowecita

Salut,

pour vous répondre, l'arbre que je voudrais testé est le suivant :
Pièce jointe 143972

et je l'ai codé de cette façon :

Code:

---

1 2 3 4 5

monarbre = ( ("A",0), (("B",0.15), (("C",0.22), None, None), (("D",0.12), None, None)), (("E",0.2), (("F",0.18), None, None), (("G",0.22), None, None)))

---

---

A mes yeux, ça n'a pas grand sens, mais on a peut-être des manières de raisonner différentes.
Pourais tu expliquer la logique de ton code comme si on était des gamins de 6 ans ?

Question subsidiaire : On vous a appris à faire créer et utiliser des classes en cours ?

Citation:

---

Envoyé par Petibidon

Salut,

A mes yeux, ça n'a pas grand sens, mais on a peut-être des manières de raisonner différentes.
Pourais tu expliquer la logique de ton code comme si on était des gamins de 6 ans ?

Question subsidiaire : On vous a appris à faire créer et utiliser des classes en cours ?

---

Salut,

Je vais essayer.
Alors à partir de l'arbre encodé tel que :

Code:

---

1 2 3 4

monarbre = ( ("A",0), (("B",0.15), (("C",0.22), None, None), (("D",0.12), None, None)), (("E",0.2), (("F",0.18), None, None), (("G",0.22), None, None)))

---

qui lorsqu'on le "dessine" correspond à Pièce jointe 143977
Je souhaite l'afficher d'une manière plus agréable ce qui permettra tout au long de mon projet une lecture et un debogage facilité.
Donc je veux afficher mon arbre dans l'ordre préfixe ce qui revient à afficher, la racine (ici ('A',0), noté u), puis le fils gauche (n) de ma racine, puis le fils gauche (n+1) de mon fils gauche (n) etc, et ensuite le fils droit de mon fils gauche (n+1) puis le fils droit de mon fils gauche (n) etc.
Ensuite on passe à l'affichage du fils droit (n) de ma racine, puis le fils gauche de mon fils droit etc.

J'espère avoir été plus clair.. :s

Et quant à la question subsidiaire, la réponse est non.

Là tu répètes l'objectif de ton programme, pas la logique de ton code.

Ce que je veux que tu décrive, c'est la structure de ta variable "monarbre" : Selon quelle logique tu l'as implémentée de cette manière. Que représente chaque variable, chaque tuple, etc. Comme si on était des débiles.

Cette manière de décrire les choses te permettra de réfléchir à la manière dont tu as fait les choses, ce que tu comptes faire, et comment tu vas le faire, et peut-être de revoir ta structure pour simplifier la manière d'atteindre l'objectif.

Une vulgarisation de la programmation informatique, c'est expliquer des choses compliquées, avec un langage restreint, à quelqu'un qui ne réfléchit pas, mais qui fait exactement ce qu'on lui demande, ni plus, ni moins. Donc si tu arrives à décrire une manière de faire les choses qu'un enfant de 6 ans pourrait comprendre, tu as déjà une bonne partie de ton programme qui est écrit, y'a plus qu'à le traduire.

Hum je vois

Donc je prends la racine de mon arbre de base c'est de la que tout va commencer. Je la marque : + (A,0) avec A = racine 0 = la distance depuis la racine.
puis je vais à la ligne et je veux appliquer la meme chose au fils gauche de ma racine, donc ce fils gauche devient ma racine +1, et comme par rapport à ma racine initiale on est descendu d'un niveau je dois avoir :
+ ('A',0)
|--+ ('B', 0.15)

je descends encore d'un niveau tel que ('B', 0.15) devient ma nouvelle racine. Je m'occupe alors de son fils gauche. Comme de la racine initiale on est descendu d'encore un niveau je decale d'un espace de façon à avoir :
+ ('A',0) ==> racine initiale
|--+ ('B', 0.15) ==> racine +1
| |--+ (’C’, 0.22) ==> racine +2

ma racine +2 n'ayant pas de fils, je "remonte" à ma racine+1 et je veux afficher son fils droit. Le fils droit de racine+1 étant au meme niveau que racine+2 on y verra le même décalage

+ ('A',0) ==> racine initiale
|--+ ('B', 0.15) ==> racine +1
| |--+ ('C', 0.22) ==> racine +2
| |--+ ('D', 0.12)

Hors avec mon code je n'arrive à afficher que jusqu'au niveau racine+2 , sans l'affichage de ('D',0.12) et SANS les décalages.


Concernant la variable monarbre, elle nous à été donné tel quel par le prof. Mais de ce que je n'en ai compris : on a monarbre(u,fg,fd) avec u : racine fg : fils gauche, fd : fils droit.
mais chaque noeud de mon arbre est représenté par un tuple ('A',0) = A : noeud, 0 = distance du noeud A, à la racine de l'arbre.

dans ton script y a une ligne qui fait un peu mal à la tête, c'est celle-ci:

Code:

---

print "| " *(profondeur(fg,i+1)-1) + "|--+ " + str(profondeur(fg,i+1))

---

cette ligne est inutilement compliquée, elle ne fait pas ce que tu souhaite qu'elle fasse à mon avis et en plus elle finit par provoquer une erreur.

à mon avis, tu devrais la remplacer par un simple:

Code:

---

profondeur(fg,i+1)

---

tu verras que ça ne plante plus et que le résultat est pas si éloignée de ce que tu souhaite au final.
à partir de cette base incomplète mais saine, je pense que tu y verras plus clair. et sinon, il sera toujours temps de réclamer plus d'aide.

et une autre chose aussi, pense à remplacer cette variable "tree" dans le test de ton "if", ça marchera mieux aussi ;)

Citation:

---

pour vous répondre, l'arbre que je voudrais testé est le suivant :
Pièce jointe 143972

et je l'ai codé de cette façon :

Code:

---

1 2 3 4 5

monarbre = ( ("A",0), (("B",0.15), (("C",0.22), None, None), (("D",0.12), None, None)), (("E",0.2), (("F",0.18), None, None), (("G",0.22), None, None)))

---

---

Désolé mais ton arbre est inexact.

Soit le schéma initial soit les tuples imbriqués.

Le résultat que tu obtiens avec prettyprint correspond bien aux tuples mais ce n'est pas le schéma donné.

Si c'est ce schéma que tu dois définir, avec les valeurs numériques, les tuples ne sont pas adaptés tu dois utiliser un dictionnaire.

Ceci représente ton schéma:

Code:

---

1 2 3 4 5 6 7 8 9 10

tree = {"A": (0, {"B": (0.15, {"C": 0.22,}, {"D": 0.12,})}, {"E": (0.2, {"F": 0.18,}, {"G": 0.22,}) }) }

---

Si tu dois préserver les valeurs None, ça peut se faire.

Si l'arbre est fourni par son prof, y'a pas d'autre choix que de faire avec.
Il est exact, mais vraiment pas clair en fait.

Les fonctions déjà codées par chlowecita s'approchent de la solution mais nécessitent des corrections.

En les reprenant en expliquant de manière détaillée ce que doit faire chaque ligne, elle devrait arriver à avoir un algo correct qu'il y aura plus qu'à traduire.

Citation:

---

Envoyé par Petibidon

Si l'arbre est fourni par son prof, y'a pas d'autre choix que de faire avec.
Il est exact, mais vraiment pas clair en fait.

---

Non, il n'est pas exact.

je vois pas ce qu'il y a d'inexact dans cet arbre...
les données ne sont pas tout à fait dans le même ordre que sur l'image...?
si c'est ça, c'est juste un "problème" d'affichage, ça change rien à l'(in)exactitude des données.

après, discuter sur l'(in)exactitude de l'arbre, ça n'a aucun intérêt et ça n'aidera certainement pas le demandeur.
ce qu'il veut c'est l'afficher, pas debattre sur l'ordre des éléments qu'il contient.

Si c'est bien le schéma présenté qui doit être traité, alors je le redis, l'arbre est faux et le code ne pourra jamais produire qu'un résultat faux.

Code:

---

1 2 3 4 5

monarbre = ( ("A",0), (("B",0.15), (("C",0.22), None, None), (("D",0.12), None, None)), (("E",0.2), (("F",0.18), None, None), (("G",0.22), None, None)))

---

Cet arbre est ceci:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

|---- ("A", 0) |---- ("B", 0.15) | |---- ("C", 0.22) | | |- None | | |- None | |---- ("D", 0.12) | |- None | |- None |---- ("E",0.2) |---- ("F", 0.18) | |- None | |- None |---- ("G",0.22) |- None |- None

---

où l'on voit que ("A",0) n'est le parent de rien du tout alors que sur le schéma il est parent de ("B", 0.15) et de ("E",0.2)


Edit: J'ajouterai que ("B", 0.15) et ("E",0.2) ne sont parent de rien du tout non plus.

Sisi, l'arbre est exact.
Si tu regarde bien, chaque niveau est un tuple (info, gauche, droite), où info est lui même un tuple... C'est illisible et capillotracté, mais correct.

je plussoie fermement ce que raconte Petitbidon et j'ajouterai que les None au bout des branches sont justement là pour signifier que c'est la fin de la branche et un code correct ne les affichera pas.
c'est d'ailleurs à ça que sert le "if tree == None:" dans le code de clowecita, à ceci près qu'il faut remplacer "tree" par "monarbre" pour que ça fonctionne.

et d'ailleurs, avec quelques petites corrections sur le code de clowecita, j'obtiens ça:

Code:

---

1 2 3 4 5 6 7

+ ('A', 0) |--+ ('B', 0.15) | |--+ ('C', 0.22) | |--+ ('D', 0.12) |--+ ('E', 0.2) | |--+ ('F', 0.18) | |--+ ('G', 0.22)

---

et il suffit d'inverser 2 lignes pour obtenir ce résultat qui est plus proche de l'image fournie:

Code:

---

1 2 3 4 5 6 7

+ ('A', 0) |--+ ('E', 0.2) | |--+ ('G', 0.22) | |--+ ('F', 0.18) |--+ ('B', 0.15) | |--+ ('D', 0.12) | |--+ ('C', 0.22)

---

Désolé Tryph, mais dans ton résultat ("A", 0) n'est pas le parent de ce qui suit, or c'est ce qui est exigé dans le schéma de base.

J'ai effectivement rajouter les None dans mon arbre pour éviter une vérification de plus, je les ai remplacés par des dictionnaires vides plus exactement.

Soit ceci:

Code:

---

1 2 3 4 5 6 7 8 9

arbre = {("A", 0): ({("B", 0.15): ({("C", 0.22): {}}, {("D", 0.12): {}})}, {("E", 0.2): ({("F", 0.18): {}}, {("G", 0.22): {}})}) }

---

Ce qui produit ceci:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

vincent@tiemoko:~/Bureau$ python printtree.py ('A', 0) | |--('B', 0.15) | | | |--('C', 0.22) | |--('D', 0.12) |--('E', 0.2) | | | |--('F', 0.18) | |--('G', 0.22)

---

Citation:

---

Envoyé par Tryph

dans ton script y a une ligne qui fait un peu mal à la tête, c'est celle-ci:

Code:

---

print "| " *(profondeur(fg,i+1)-1) + "|--+ " + str(profondeur(fg,i+1))

---

cette ligne est inutilement compliquée, elle ne fait pas ce que tu souhaite qu'elle fasse à mon avis et en plus elle finit par provoquer une erreur.

à mon avis, tu devrais la remplacer par un simple:

Code:

---

profondeur(fg,i+1)

---

tu verras que ça ne plante plus et que le résultat est pas si éloignée de ce que tu souhaite au final.
à partir de cette base incomplète mais saine, je pense que tu y verras plus clair. et sinon, il sera toujours temps de réclamer plus d'aide.

et une autre chose aussi, pense à remplacer cette variable "tree" dans le test de ton "if", ça marchera mieux aussi ;)

---

Je ne comprends pas trop la. Remplacer toute ma ligne par

Code:

---

profondeur(fg,i+1)

---

?

En testant j'obtiens

Code:

---

1 2 3 4

>>> profondeur(monarbre,0) + ('A', 0) + ('B', 0.15) + ('C', 0.22)

---

Alors je vois pas en quoi ca résout mon problème.

Concernant l'arbre et son code c'est en effet du copier coller de ce que mon prof m'a fourni.

Citation:

---

Envoyé par Tryph

je plussoie fermement ce que raconte Petitbidon et j'ajouterai que les None au bout des branches sont justement là pour signifier que c'est la fin de la branche et un code correct ne les affichera pas.
c'est d'ailleurs à ça que sert le "if tree == None:" dans le code de clowecita, à ceci près qu'il faut remplacer "tree" par "monarbre" pour que ça fonctionne.

et d'ailleurs, avec quelques petites corrections sur le code de clowecita, j'obtiens ça:

Code:

---

1 2 3 4 5 6 7

+ ('A', 0) |--+ ('B', 0.15) | |--+ ('C', 0.22) | |--+ ('D', 0.12) |--+ ('E', 0.2) | |--+ ('F', 0.18) | |--+ ('G', 0.22)

---

---

C'est en effet la fonction des None selon mon cours. et c'est le code que je dois obtenir mais je ne vois pas comment en faisant la modif
sur

Code:

---

profondeur(fg,i+1)

---

tu as pu obtenir cela.