User Tools

Site Tools


maxime_savaro:solution_homework1

Implémentation de l’algorithme « H-tree »

Utilisation et fonctionnement du code

Généralités

Le code qui suit doit être utilisé sur un arbre de degré maximal 3. Du fait de l’animation, il devient excessivement lent pour des arbres de quelques centaines de nœuds. Je conseille de choisir des arbres de 20 à 50 nœuds.

Il commence par appliquer un algorithme-plugin de positionnement des nœuds, sans quoi la progression est tout-à-fait illisible.

Les nœuds changent de couleur lors du premier parcours en profondeur de l’arbre, qui détermine la direction du nœud, affichée sous forme d’une étiquette parmi ←, ↓, →, ↑, et la taille des sous-arbres, affichée sous forme d’une boîte autour du nœud considéré. La direction de la racine est toujours « ← », mais n’est pas pertinente (et pas toujours cohérente).

Dans un deuxième temps, les nœuds se déplacent avec leur boîtes vers leur position finale, et on comprend le principe de l’algorithme à la façon dont les boîtes… s’emboîtent.

La complexité de l’algorithme est linéaire en la taille de l’arbre (on effectue deux parcours).

Paramètres modifiables dans le code

En décommentant un bloc de code à la fin de la fonction rect, on modifie l’apparence des boîtes en sorte de lier explicitement chaque boîte avec le nœud correspondant. Néanmoins, ce n’est pas toujours plus lisible en pratique.

On peut accélérer le fonctionnement du programme et désactiver les animations en commentant les occurences d’appel des fonctions rect, rerect, updateVisualisation (sauf la dernière occurence), time.sleep, viewColor et viewLabelColor, et en décommentant la ligne #n=0 dans la fonction animate. Dans ce cas, des arbres à muelques milliers de nœuds peuvent être traités rapidement.

On peut modifier la vitesse d’animation des nœuds en modifiant le dénominateur de l’expression n=24*(dd××(0.5))/1000 dans la fonction animate. Un dénominateur plus élevé donne une animation plus rapide.

Remarques moins importantes

Conformément à mes habitudes de programmation, les noms de variables sont mal choisis.

Il semblerait que python n’apprécie pas les caractères non ASCII, et peut renvoyer un message d’erreur du fait de la présence de tels caractères dans les commentaires et dans les chaînes de caractères (étiquette des nœuds). Mais ceci n’entrave pas le fonctionnement du code.

Code source

# Powered by Python 2.7
 
# To cancel the modifications performed by the script
# on the current graph, click on the undo button.
 
# Some useful keyboards shortcuts : 
#   * Ctrl + D : comment selected lines.
#   * Ctrl + Shift + D  : uncomment selected lines.
#   * Ctrl + I : indent selected lines.
#   * Ctrl + Shift + I  : unindent selected lines.
#   * Ctrl + Return  : run script.
#   * Ctrl + F  : find selected text.
#   * Ctrl + R  : replace selected text.
#   * Ctrl + Space  : show auto-completion dialog.
 
from tulip import *
 
import time
import math
 
# the updateVisualization(centerViews = True) function can be called
# during script execution to update the opened views
 
# the pauseScript() function can be called to pause the script execution.
# To resume the script execution, you will have to click on the "Run script " button.
 
# the runGraphScript(scriptFile, graph) function can be called to launch another edited script on a tlp.Graph object.
# The scriptFile parameter defines the script name to call (in the form [a-zA-Z0-9_]+.py)
 
# the main(graph) function must be defined 
# to run the script on the current graph
 
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")
	viewLabelBorderColor =  graph.getColorProperty("viewLabelBorderColor")
	viewLabelBorderWidth =  graph.getDoubleProperty("viewLabelBorderWidth")
	viewLabelColor =  graph.getColorProperty("viewLabelColor")
	viewLabelPosition =  graph.getIntegerProperty("viewLabelPosition")
	viewLayout =  graph.getLayoutProperty("viewLayout")
	viewMetaGraph =  graph.getGraphProperty("viewMetaGraph")
	viewMetric =  graph.getDoubleProperty("viewMetric")
	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")
 
 
	for n in graph.getNodes():
		#I will show the orientation of each node by giving them labels
		viewLabel[n]=""
 
	#It is hard to see the progress of the algorithm if the tree is poorly layouted at the beginning…
	tlp.initTulipLib()
	tlp.loadPlugins()
	graph.applyLayoutAlgorithm("Tree Radial", viewLayout)
	updateVisualization()
 
	#I should use a graph property insead of a dictionnary. This will contain the north, south, east and west width of each subtree, plus the direction of the node
	d={}	
 
	#draw around a node the box that will contain the corresponding subtree
	def rect(node):
		N=d[node]["N"]
		S=d[node]["S"]
		E=d[node]["E"]
		W=d[node]["W"]
		X=viewLayout[node][0]
		Y=viewLayout[node][1]
		rectd[node]["sw"]=graph.addNode()
		d[rectd[node]["sw"]]={}
		d[rectd[node]["sw"]]["dir"]=5
		viewLayout[rectd[node]["sw"]]=tlp.Coord(X-W, Y-S)
		viewColor[rectd[node]["sw"]]=tlp.Color(200,200,200,0)
		rectd[node]["se"]=graph.addNode()
		d[rectd[node]["se"]]={}
		d[rectd[node]["se"]]["dir"]=5
		viewLayout[rectd[node]["se"]]=tlp.Coord(X+E, Y-S)
		viewColor[rectd[node]["se"]]=tlp.Color(200,200,200,0)
		rectd[node]["nw"]=graph.addNode()
		d[rectd[node]["nw"]]={}
		d[rectd[node]["nw"]]["dir"]=5
		viewLayout[rectd[node]["nw"]]=tlp.Coord(X-W, Y+N)
		viewColor[rectd[node]["nw"]]=tlp.Color(200,200,200,0)
		rectd[node]["ne"]=graph.addNode()
		d[rectd[node]["ne"]]={}
		d[rectd[node]["ne"]]["dir"]=5
		viewLayout[rectd[node]["ne"]]=tlp.Coord(X+E, Y+N)
		viewColor[rectd[node]["ne"]]=tlp.Color(200,200,200,0)
		e=graph.addEdge(rectd[node]["sw"], rectd[node]["se"])
		viewColor[e]=tlp.Color(0,0,0,255)
		e=graph.addEdge(rectd[node]["sw"], rectd[node]["nw"])
		viewColor[e]=tlp.Color(0,0,0,255)
		e=graph.addEdge(rectd[node]["ne"], rectd[node]["se"])
		viewColor[e]=tlp.Color(0,0,0,255)
		e=graph.addEdge(rectd[node]["ne"], rectd[node]["nw"])
		viewColor[e]=tlp.Color(0,0,0,255)
		#uncomment to see which box belongs to which vertex… but a little bit uggly
		'''
		e=graph.addEdge(node, rectd[node]["nw"])
		viewColor[e]=tlp.Color(0,0,200,100)
		e=graph.addEdge(node, rectd[node]["ne"])
		viewColor[e]=tlp.Color(0,0,200,100)
		e=graph.addEdge(node, rectd[node]["sw"])
		viewColor[e]=tlp.Color(0,0,200,100)
		e=graph.addEdge(node, rectd[node]["se"])
		viewColor[e]=tlp.Color(0,0,200,100)
		'''
 
	#The same as rect, but only redefining the position of an existing box.
	def rerect(node):
		N=d[node]["N"]
		S=d[node]["S"]
		E=d[node]["E"]
		W=d[node]["W"]
		X=viewLayout[node][0]
		Y=viewLayout[node][1]
		viewLayout[rectd[node]["sw"]]=tlp.Coord(X-W, Y-S)
		viewLayout[rectd[node]["se"]]=tlp.Coord(X+E, Y-S)
		viewLayout[rectd[node]["nw"]]=tlp.Coord(X-W, Y+N)
		viewLayout[rectd[node]["ne"]]=tlp.Coord(X+E, Y+N)
 
	#recursive depth first traversal, to compute the width of the subtrees and the orientation of the nodes
	def rec(node, ddir):
		viewColor[node]=tlp.Color(0, 200, 0, 255)
		viewLabelColor[node]=tlp.Color(0, 200, 0, 255)
		updateVisualization()
		time.sleep(.3)
		dir=ddir
		d[node]={}
		d[node]["dir"]=dir
		#so dir==0 means West, dir==1 means south…
		if dir==0:
			viewLabel[node]="←"
		if dir==1:
			viewLabel[node]="↓"
		if dir==2:
			viewLabel[node]="→"
		if dir==3:
			viewLabel[node]="↑"
		sons=0
		#for node which have at most one son, the direction will not change (and for the root, we don’t care)
		if (graph.deg(node)==3): 
			dir=dir+1
			if (dir==4):
				dir=0			
		for b in graph.getInOutNodes(node):
			if (not d.has_key(b)): #i.e. if it is actually a son, and not the father, according to the choosen root
				rec(b, dir)
				dir=dir+2
				if (dir>3):
					dir=dir-4
				sons=sons+1
		viewColor[node]=tlp.Color(0, 0, 200, 255)
		viewLabelColor[node]=tlp.Color(0, 0, 200, 255)
		updateVisualization()
		time.sleep(.3)
		if (sons==0):
			d[node]["W"]=0
			d[node]["S"]=0
			d[node]["E"]=0
			d[node]["N"]=0
		if (sons==1):
		 	for b in graph.getInOutNodes(node):
		 		if (d[b].has_key("W")):
					if (ddir==0):
						d[node]["W"]=d[b]["W"]+d[b]["E"]+30
						d[node]["S"]=d[b]["S"]
						d[node]["E"]=0
						d[node]["N"]=d[b]["N"]
					if (ddir==1):
						d[node]["W"]=d[b]["W"]
						d[node]["S"]=d[b]["S"]+d[b]["N"]+30
						d[node]["E"]=d[b]["E"]
						d[node]["N"]=0
					if (ddir==2):
		 				d[node]["W"]=0
		 				d[node]["S"]=d[b]["S"]
		 				d[node]["E"]=d[b]["E"]+d[b]["W"]+30
		 				d[node]["N"]=d[b]["N"]
		 			if (ddir==3):
		 				d[node]["W"]=d[b]["W"]
		 				d[node]["S"]=0
		 				d[node]["E"]=d[b]["E"]
		 				d[node]["N"]=d[b]["N"]+d[b]["S"]+30
		if (sons==2):
			if (ddir==0 or ddir==2 and not node==a):
				d[node]["W"]=0
				d[node]["E"]=0
				for b in graph.getInOutNodes(node):
					if (d[b].has_key("W")):
						if (d[b]["W"]>=d[node]["W"]):
								d[node]["W"]=d[b]["W"]
						if (d[b]["E"]>=d[node]["E"]):
							d[node]["E"]=d[b]["E"]
						if d[b]["dir"]==1:
							d[node]["S"]=30+d[b]["N"]+d[b]["S"]
						if d[b]["dir"]==3:
							d[node]["N"]=30+d[b]["N"]+d[b]["S"]
			if (ddir==1 or ddir==3 or node==a):
				d[node]["N"]=0
				d[node]["S"]=0
				for b in graph.getInOutNodes(node):
					if (d[b].has_key("W")):
						if (d[b]["N"]>=d[node]["N"]):
							d[node]["N"]=d[b]["N"]
						if (d[b]["S"]>=d[node]["S"]):
							d[node]["S"]=d[b]["S"]
						if d[b]["dir"]==0:
							d[node]["W"]=30+d[b]["W"]+d[b]["E"]
						if d[b]["dir"]==2:
							d[node]["E"]=30+d[b]["W"]+d[b]["E"]
		rect(node)
		viewColor[node]=tlp.Color(200, 0, 0, 255)
		updateVisualization()
		time.sleep(.3)
 
 
	rectd={}
	for c in graph.getNodes():
		rectd[c]={}
 
	#animate a node (and its box) from its position to (endx, endy)
	def animate(node, endx, endy):
		x=viewLayout[node][0]
		y=viewLayout[node][1]
		dx=endx-x
		dy=endy-y
		dd=dx*dx+dy*dy
		n=24*(dd**(0.5))/1000
		#n=0
		nn=int (math.floor(n))
		for i in range (0, nn):
			viewLayout[node]=tlp.Coord(x+i*dx/n, y+i*dy/n, 0)
			rerect(node)
			updateVisualization()
			time.sleep(0.03)
 
		viewLayout[node]=tlp.Coord(endx, endy, 0)
		rerect(node)
		updateVisualization()
		time.sleep(0.03)
 
	#Traversal to place the nodes according to the computed widths of subtrees
	def hlayout(node):
		d[node]["dir"]=5
		for n in graph.getInOutNodes(node):
			if d[n]["dir"]==0:
				x=viewLayout[node][0]-d[node]["W"]+d[n]["W"]
				y=viewLayout[node][1]
			if d[n]["dir"]==1:
				x=viewLayout[node][0]
				y=viewLayout[node][1]-d[node]["S"]+d[n]["S"]
			if d[n]["dir"]==2:
				x=viewLayout[node][0]+d[node]["E"]-d[n]["E"]
				y=viewLayout[node][1]
			if d[n]["dir"]==3:
				x=viewLayout[node][0]
				y=viewLayout[node][1]+d[node]["N"]-d[n]["N"]
			if d[n]["dir"]!=5:
				animate(n, x, y)
		for n in graph.getInOutNodes(node):
			if d[n]["dir"]!=5:
				hlayout(n)
 
	#We find a root of degree at most 2, and do the job.
	for a in graph.getNodes():
		if (graph.deg(a)!=3):
			rec(a, 0)
			hlayout(a)
			break
 
	#Erasing the boxes.
	for n in graph.getNodes():
		if viewColor[n]==tlp.Color(200,200,200,0):
			graph.delNode(n)
	updateVisualization()

Améliorations possibles

Choix de la racine

Ici, la racine est choisie arbitrairement parmi les sommets de degré au plus deux. On peut chercher à minimiser la profondeur de l’arbre, et donc à choisir comme racine le sommet qui minimise le plus court chemin maximal vers un feuille.

Choix des fils gauche et droit

Cette algorithme détermine les fils gauche et droit de façon arbitraire. Il est certainement possible d’améliorer heuristiquement le rendu, par exemple en plaçant les plus gros sous-arbres vers l’extérieur. Ceci favoriserait les formes en escalier plutôt que les formes en spirale, et donc permetterait une représentation plus compacte, des longueurs d’arêtes plus uniformes, et un positionnement plus cohérent en ce sens que deux nœuds proches dans l’arbre seraient alors plus proches à l’écran, et inversement.

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/maxime_savaro/solution_homework1.txt · Last modified: 2014/10/20 16:56 by savaro