User Tools

Site Tools


cdjemiel:solution_homework2
Critères & points attribués (/10)
Rappel du contexte 4
Résultats 4
Qualité du code (commentaires, structures utilisées, …) 7
Animation du dessin 0
Explication en dehors du code 4
Total (/50) 19

Vous ne rappelez pas le travail à faire. Vos commentaires sont insufissants. Le résultat obtenu n'est pas correct. Aucune mention du travail demandé sur l'animation des changements dans le graphe.

Je dois implémenter un algorithme permettant de modifier la position des différents noeuds d'un arbre binaire suivant le modèle H-tree.

Je suis partie d'un arbre ayant au maximum 6 noeuds afin de pouvoir facilement voir mes erreurs.

J'ai créé deux fonctions :

* une me permettant de déplacer les noeuds (deplacementNoeud()).

* l'autre me permettant de calculer les nouvelles coordonnées pour former un H (parseNoeud()).

La première fonction deplacementNoeud() prend en paramètre le noeud en cours de traitement et ses nouvelles coordonnées. Je récupère dans un premier temps ses coordonnées actuelles puis je les remplace.

La seconde fonction parseNoeud() prend en paramètre le noeud en cours de traitement. Je récupère les coordonnées du noeud et de son père afin de pouvoir calculer les nouvelles coordonnées du noeud. J'ai implémenté deux cas de figure : si le père est la racine et s'il ne l'est pas.

Dans le cas le père est racine, j'indique que les noeuds gauche et/ou droite gardent leurs coordonnées X et prennent en coordonnée Y celle du père. Ce qui a pour conséquence de mettre à l'horizontal les trois noeuds.

Dans les autres cas, si le noeud est situé à gauche du père alors sa coordonnée X est égal à celle du père et sa coordonnée Y est égal à sa coordonnéeY plus une “distance” permettant de faire un angle droit avec son père. Si le noeud est situé à droite du père alors sa coordonnée X est égal à celle du père et sa coordonnée Y est égal à sa coordonnéeY permettant de faire un autre angle droit avec son père.

L'algorithme fonctionne à peu près bien lorsqu'il sagit d'un arbre binaire avec peu de noeuds mais lorsque j'augmente la taille de l'arbre j'ai des arrêtes qui se superposent les unes sur les autres. Je pense que c'est au problème du calcul de la “distance” pour déplacer le noeud vers le “haut” ou vers le “bas”.

En conclusion, malgrès beaucoup de difficultés pour réorganiser un arbre binaire en un H-tree je suis arrivé à obtenir un H-tree pour un arbre à 6 noeuds.

devoir_htree_djemiel_christophe.py
import math
from tulip import *
 
def deplacementNoeud(noeud,x,y):
 
	noeudX=float(graph.getProperty('viewLayout').getNodeStringValue(noeud).replace('(',''.replace(')','')).split(',')[0])
	noeudY=float(graph.getProperty('viewLayout').getNodeStringValue(noeud).replace('(',''.replace(')','')).split(',')[1])
 
	noeudX=x
	noeudY=y
 
	#remplace les coordonnees du noeud traitre 
	graph.getProperty('viewLayout').setNodeStringValue(noeud,"("+str(noeudX)+","+str(noeudY)+",0)")
	updateVisualization(centerViews = True)
 
def parseNoeud(noeud):
 
	#recupere le pere du noeud en cours de traitement
	#Returns the ith predecessor of a node. 
	pere=graph.getInNode(noeud,1)
 
	#position des coordonnees du pere du noeud en cours de traitement
	coordPereX= float(graph.getLayoutProperty("viewLayout").getNodeStringValue(pere).replace('(','').replace(')','').split(',')[0])
	coordPereY= float(graph.getLayoutProperty("viewLayout").getNodeStringValue(pere).replace('(','').replace(')','').split(',')[1])
 
	#position du coordonnees du noeud en cours de traitement
	coordNoeudX= float(graph.getLayoutProperty("viewLayout").getNodeStringValue(noeud).replace('(','').replace(')','').split(',')[0])
	coordNoeudY= float(graph.getLayoutProperty("viewLayout").getNodeStringValue(noeud).replace('(','').replace(')','').split(',')[1])
 
	#calcul de la distance entre la position du pere et du fils
	distance=math.sqrt((coordNoeudX-coordPereX)*(coordNoeudX-coordPereX)+(coordNoeudY-coordPereY)*(coordNoeudY-coordPereY))
 
	#affectation des nouvelles coordonnees au noeud
	coordRootX=20.0
	coordRootY=20.0
	#traitement particulier si le pere est la racine de l abre
	if coordPereX==coordRootX and coordPereY==coordRootY:
		x=coordNoeudX
		y=coordPereY
	#traitement pour tous les autres noeuds
	else:
		#noeud situe a gauche du pere
		if coordPereX>=coordNoeudX:
			x=coordPereX
			y=coordNoeudY+distance*2
		#noeud situe a droite du pere
		else:
			x=coordPereX
			y=coordNoeudY
 
	#appelle a la fonction deplacement pour attribuer les nouvelles coordonnees
	deplacementNoeud(noeud,x,y)
 
	#pour traiter l ensemble des fils
	for fils in graph.getOutNodes(noeud):
		parseNoeud(fils)
 
 
 
 
def main(graph): 
 
	viewBorderColor =  graph.getColorProperty("viewBorderColor")
	viewBorderWidth =  graph.getDoubleProperty("viewBorderWidth")
	viewColor =  graph.getColorProperty("viewColor")
	viewFont =  graph.getStringProperty("viewFont")
	viewFontSize =  graph.getIntegerProperty("viewFontSize")
	viewLabel =  graph.getStringProperty("viewLabel")
	viewLabelColor =  graph.getColorProperty("viewLabelColor")
	viewLabelPosition =  graph.getIntegerProperty("viewLabelPosition")
	viewLayout =  graph.getLayoutProperty("viewLayout")
	viewMetaGraph =  graph.getGraphProperty("viewMetaGraph")
	viewRotation =  graph.getDoubleProperty("viewRotation")
	viewSelection =  graph.getBooleanProperty("viewSelection")
	viewShape =  graph.getIntegerProperty("viewShape")
	viewSize =  graph.getSizeProperty("viewSize")
	viewSrcAnchorShape =  graph.getIntegerProperty("viewSrcAnchorShape")
	viewSrcAnchorSize =  graph.getSizeProperty("viewSrcAnchorSize")
	viewTexture =  graph.getStringProperty("viewTexture")
	viewTgtAnchorShape =  graph.getIntegerProperty("viewTgtAnchorShape")
	viewTgtAnchorSize =  graph.getSizeProperty("viewTgtAnchorSize")
 
 
	root=0
	#Returns a string conversion of the value registered for the given node.	
	for n in graph.getNodes():
		#Returns an iterator on the incoming edges of a node. tant que le bool est vrai
		if not graph.getInEdges(n).hasNext():
			root=n
 
	#placement de la racine
	deplacementNoeud(root,20,20)
 
	#Returns an iterator on the successors of a node.
	for n in graph.getOutNodes(root):
		parseNoeud(n)
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/cdjemiel/solution_homework2.txt · Last modified: 2012/10/22 12:29 by bpinaud