User Tools

Site Tools


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

B.P. : Votre code fournit le résultat attendu (même si l'arbre n'est pas complet) mais sans animation. Vous n'avez fournit aucun commentaire en dehors ou dans votre code (mais il y a quand même un rappel du sujet).

  • Algo H-tree : Je n'ai pas réussi a animer les modifications sur le graphe.

Le script a l'air de fonctionner sur les arbres générés par l'algo “Complete Tree”. Il ne vérifie pas qu'on a bien un arbre binaire en entrée. Pas testé sur des abres pas compets.

MakeBB(..) creer récursivement les bounding box. Pour rajouter les animations, on peut modifier la fonction redraw(graph, node)

# 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 *
 
# 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): 
	Circular__search_cyclefalse_viewLayout =  graph.getLayoutProperty("Circular - 'search cycle'=false (viewLayout)")
	Random_layout__3D_layoutfalse_viewLayout =  graph.getLayoutProperty("Random layout - '3D layout'=false (viewLayout)")
	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")
	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")
 
	#create property "visited"
	visited = graph.getBooleanProperty("Visited")
 
	#set bounding box properties
	North = graph.getDoubleProperty("North")
	East = graph.getDoubleProperty("East")
	South = graph.getDoubleProperty("South")
	West = graph.getDoubleProperty("West")
 
	# Parent Location : N E S W
	dp = graph.getIntegerProperty("Dp")
 
	North.setAllNodeValue(0)
	East.setAllNodeValue(0)
	South.setAllNodeValue(0)
	West.setAllNodeValue(0)
 
	#Delta : min distance
	delta = graph.getDoubleProperty("Delta")
	delta.setAllNodeValue(10)
 
#	for n in graph.getNodes():
#		viewLabel.setNodeValue(n,str(n.id))
 
        #call Htree on the current graph
	Htree(graph)
 
 
def Htree(graph):
 
	#finding the right edge to start the H-tree
	midEdge = getMidEdge(graph)
	n1 = graph.source(midEdge)
	n2 = graph.target(midEdge)
 
	#init algo
	graph["Visited"].setAllNodeValue(False)
	graph["Visited"].setNodeValue(n1,True)
	graph["Visited"].setNodeValue(n2,True)
 
	#make the bounding box for the 2 nodes in midEdge
	makeBB(graph,n1,1)
	makeBB(graph,n2,1)
 
	#set the 1st node at (0,0)
	graph["viewLayout"][n1] = tlp.Coord(0,0, 0)
	x = graph["viewLayout"][n1][0]+(graph["West"].getNodeValue(n2) + graph["Delta"].getNodeDefaultValue())
	y = graph["viewLayout"][n1][1]
	graph["viewLayout"][n2] = tlp.Coord(x,y, 0)
 
	graph["Visited"].setAllNodeValue(False)
	graph["Visited"].setNodeValue(n1,True)
	#draw the graph
	redraw(graph,n1);
 
 
def redraw(graph,node):
	graph.push();
	for n in graph.getInOutNodes(node):
		if not graph["Visited"].getNodeValue(n):
			dp = graph["Dp"].getNodeValue(n)
			if dp == 0:
				x = graph["viewLayout"][node][0]
				y = graph["viewLayout"][node][1]-(graph["North"].getNodeValue(n) + graph["Delta"].getNodeDefaultValue())
			elif dp == 1:
				x = graph["viewLayout"][node][0]-(graph["East"].getNodeValue(n) + graph["Delta"].getNodeDefaultValue())
				y = graph["viewLayout"][node][1]
			elif dp == 2:
				x = graph["viewLayout"][node][0]
				y = graph["viewLayout"][node][1]+(graph["South"].getNodeValue(n) + graph["Delta"].getNodeDefaultValue())
			else :
				x = graph["viewLayout"][node][0]+(graph["West"].getNodeValue(n) + graph["Delta"].getNodeDefaultValue())
				y = graph["viewLayout"][node][1]
			graph["viewLayout"][n] = tlp.Coord(x,y, 0)
			graph["Visited"].setNodeValue(n,True)
			redraw(graph,n)
 
def makeBB(graph,node,dp):
	graph["Dp"].setNodeValue(node,dp)
	n1 = None
	n2 = None
	for n in graph.getInOutNodes(node):
		if not graph["Visited"].getNodeValue(n):
			if n1 == None:
				n1 = n
			else:
				n2 = n
	if not n1 == None and not n2 == None:
		graph["Visited"].setNodeValue(n1,True)
		graph["Visited"].setNodeValue(n2,True)
		makeBB(graph,n1,(dp+1)%4)
		makeBB(graph,n2,(dp+3)%4)
		BB2(graph,node,n1,n2,dp)
	elif not n1 == None:
		graph["Visited"].setNodeValue(n1,True)
		makeBB(graph,n1,(dp+2)%4)
		BB1(graph,node,n1,dp)
	#else leaf
 
 
 
#node counter
def dfs(node,graph,selected):
	cpt=0
	for ed in graph.getInOutEdges(node):
		end = graph.opposite(ed,node)
		if not selected.getNodeValue(end):
			selected.setNodeValue(end,True)
			cpt+=dfs(end,graph,selected)
	return cpt+1
 
def nnode(edge,graph,selected):
	selected.setAllNodeValue(False)
	selected.setAllEdgeValue(False)
	n1 = graph.source(edge)
	n2 = graph.target(edge)
	selected.setNodeValue(n1,True)
	selected.setNodeValue(n2,True)
	dif= dfs(n1,graph,selected) - dfs(n2,graph,selected)
	selected.setAllNodeValue(False)
	selected.setAllEdgeValue(False)
	return dif
 
def getMidEdge(graph):
	redge = graph.getOneEdge()
	selected = graph.getBooleanProperty("viewSelection")
	rmin = nnode(redge,graph,selected)
	for edge in graph.getEdges():
		v = nnode(edge,graph,selected)
		if v<rmin:
			rmin = v
			redge = edge
	return redge
 
###
 
def BB1(graph,node,n,dp):
	if dp == 0:
		#north
		hn = graph["North"].getNodeValue(n)+graph["South"].getNodeValue(n)+graph["Delta"].getNodeDefaultValue()
		graph["North"].setNodeValue(node,0)
		graph["East"].setNodeValue(node,graph["East"].getNodeValue(n))
		graph["South"].setNodeValue(node,hn)
		graph["West"].setNodeValue(node,graph["West"].getNodeValue(n))
	elif dp == 1:
		#east
		wn = graph["East"].getNodeValue(n)+graph["West"].getNodeValue(n)+graph["Delta"].getNodeDefaultValue()
		graph["North"].setNodeValue(node,graph["North"].getNodeValue(n))
		graph["East"].setNodeValue(node,0)
		graph["South"].setNodeValue(node,graph["South"].getNodeValue(n))
		graph["West"].setNodeValue(node,wn)
	elif dp == 2:
		#south
		hn = graph["North"].getNodeValue(n)+graph["South"].getNodeValue(n)+graph["Delta"].getNodeDefaultValue()
		graph["North"].setNodeValue(node,hn)
		graph["East"].setNodeValue(node,graph["East"].getNodeValue(n))
		graph["South"].setNodeValue(node,0)
		graph["West"].setNodeValue(node,graph["West"].getNodeValue(n))
	else:
		#west
		wn = graph["East"].getNodeValue(n)+graph["West"].getNodeValue(n)+graph["Delta"].getNodeDefaultValue()
		graph["North"].setNodeValue(node,graph["North"].getNodeValue(n))
		graph["East"].setNodeValue(node,wn)
		graph["South"].setNodeValue(node,graph["South"].getNodeValue(n))
		graph["West"].setNodeValue(node,0)
 
 
def BB2(graph,node,n1,n2,dp):
	if dp%2 == 0:
		wn1 = graph["East"].getNodeValue(n1)+graph["West"].getNodeValue(n1)+graph["Delta"].getNodeDefaultValue()
		wn2 = graph["East"].getNodeValue(n2)+graph["West"].getNodeValue(n2)+graph["Delta"].getNodeDefaultValue()
		north = max (graph["North"].getNodeValue(n1),graph["North"].getNodeValue(n2))
		south = max (graph["South"].getNodeValue(n1),graph["South"].getNodeValue(n2))
		##set bounding box
		graph["North"].setNodeValue(node,north)
		graph["East"].setNodeValue(node,wn2)
		graph["South"].setNodeValue(node,south)
		graph["West"].setNodeValue(node,wn1)
	else:
		hn1 = graph["North"].getNodeValue(n1)+graph["South"].getNodeValue(n1)+graph["Delta"].getNodeDefaultValue()
		hn2 = graph["North"].getNodeValue(n2)+graph["South"].getNodeValue(n2)+graph["Delta"].getNodeDefaultValue()
		east = max(graph["East"].getNodeValue(n1),graph["East"].getNodeValue(n2))
		west = max(graph["West"].getNodeValue(n1),graph["West"].getNodeValue(n2))
		##set bounding box
		graph["North"].setNodeValue(node,hn1)
		graph["East"].setNodeValue(node,east)
		graph["South"].setNodeValue(node,hn2)
		graph["West"].setNodeValue(node,west)
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/frandriamanana/solution_homework2.txt · Last modified: 2012/10/23 14:38 by bpinaud