User Tools

Site Tools


dimitri_ranc:solution_homework1

Solution to Homework 1 - Tree drawing algorithm implementation


Voici le code du travail à rendre pour le 20 oct 2014. Je n'ai pas trouvé de binôme du coup j'ai fait ça seul.


J'ai choisi d'implémenter l'algorithme de visualisation de type Onion Tree. Le code est directement commenté. Il fonctionne sur Linux et Windows mais l'animation n'est visible que sur Linux (l'écran freeze sur Windows pendant le temps de l’exécution et reprend ensuite).

Le code est téléchargeable ici https://drive.google.com/open?id=0Bzj5VMXFP5OlckVybFZUbUU5azA&authuser=0.

Voici deux jeux d'images permettant de voir le résultat sur 2 arbres différents :

1. arbre de départ : https://drive.google.com/open?id=0Bzj5VMXFP5OldzZMNmwyWGRwZ2s&authuser=0 résultat : https://drive.google.com/open?id=0Bzj5VMXFP5OlM0RvM1dCNjR1RGs&authuser=0

2. arbre de départ : https://drive.google.com/open?id=0Bzj5VMXFP5OlN0djbWxBU1lEOE0&authuser=0 résultat : https://drive.google.com/open?id=0Bzj5VMXFP5OlQUdScGlSUUxBMjA&authuser=0

# 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.

import time

from tulip import *
from tulipogl import *
from tulipgui import *
from math import pow

# 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

# permet de dessiner un noeau sous forme de carre a une position donnee
# d'une taille donnee et d'une couleur donnee
def drawNode(graph, node, size, x, y, color):
	viewShape =  graph.getIntegerProperty("viewShape")
	viewSize =  graph.getSizeProperty("viewSize")
	viewColor =  graph.getColorProperty("viewColor")
	viewBorderColor =  graph.getColorProperty("viewBorderColor")
	viewBorderWidth =  graph.getDoubleProperty("viewBorderWidth")
	viewLayout =  graph.getLayoutProperty("viewLayout")
	
	viewShape[node] = tlp.NodeShape.Square	
	viewSize[node] = tlp.Size(size, size, 1)
	viewColor[node] = color	
	viewBorderColor[node] = tlp.Color.Black
	viewBorderWidth[node] = 1
	viewLayout[node] = tlp.Coord(x, y)
	
	# permet de voir les dessins un par un, ces deux lignes ne fonctionnent 
	# pas sous windows mais marche sur Linux	
	time.sleep(0.1)
	updateVisualization()

# permet de recuperer le root de l'arbre, en fait le seul noeud qui n'a pas de parent
def getRoot(graph):
	for n in graph.getNodes():
		nodes = list(graph.getInNodes(n))
		if(len(nodes) == 0): # si pas de noeud entrant
			return n # c'est notre noeud (le noeud 0 dans notre cas mais on ne sais jamais

# permet de calculer en combien sera le cote du carre
# on travaille sur des carres donc on veut que les enfants soient bien repartis
# dans les peres.
def getMinSide(n):
	res = 1
	while (res*res) < n:
		res = res+1
	return res

# afin de travailler sur de grands arbres, on essaie d'adapter la taille du premier noeud (vu que les autres seront dedans)
# a la profondeur du graph (mais je n'ai pas trouve de fonction qui fait la profondeur direct donc j'utilise le degre)
def getSuperFatherSize(graph):
	return pow(2, tlp.maxDegree(graph)*2)

# on dessine le noeud puis on rappelle la meme methode pour tous les noeuds
# qui sortent du noeud courant en les repartissant equitablement
# dans le noeud courant
def drawOutNodes(graph, node, fatherSize, fatherX, fatherY, color, num, side):
	# on reparti equitablement l'espace entre tous les enfants	
	size = fatherSize/side
	
	# on calcule les nouveaux coordonnees des enfants pour qu'ils se repartissent dans cet ordre
	# [ 0 1 ]
	# [ 2 3 ]
	# pour ca on a side qui est la taille du cote (ici 2) et num qui est le numero du noeud dans
	# le pere ici, successivement 1, 2, 3, 4 ...
	x = fatherX - fatherSize/2 + size/2 + size*(num%side)
	y = fatherY + fatherSize/2 - size/2 - size*(int(num/ side))

	# on dessine le noeud
	drawNode(graph, node, size, x, y, color)	
		
	# on calcule le degrade
	color = tlp.Color(
		int(color.getR()*pas), 
		int(color.getG()*pas), 
		int(color.getB()*pas))
	
	# on va ensuite par recurcivite dessine les fils du noeud courant qu'on va numerote
	
	# on calcule comment vont etre repartis les fils dans le noeud
	side = getMinSide(len(list(graph.getOutNodes(node))))	
	cpt = 0
	for n in graph.getOutNodes(node):
		drawOutNodes(graph, n, size, x, y, color, cpt, side)
		# on incremente le compteur
		cpt = cpt + 1

# couleur de depart
startColor = tlp.Color.RedViolet
# coeficient de degrade
pas = 0.9

# dans le main , on a juste a dessiner le root qui s'occupe tout seul de dessiner ses enfants et ect ...
def main(graph):
	# on affiche le root puis tous ses fils puis tous leurs fils ...
	drawOutNodes(graph, getRoot(graph), getSuperFatherSize(graph), 0, 0, startColor, 0, 1)
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/dimitri_ranc/solution_homework1.txt · Last modified: 2014/10/20 08:46 by ranc