User Tools

Site Tools


garcin:solution_homework2

Table of Contents

  • Note: 3.5/5
  • L'exemple traité est somme toute très petit.
  • Vous ne triez pas les éléments selon la métrique choisi pour les positionner le long de la courbe. ?
  • Votre code est difficile à lire.

Guy Melançon 2012/04/17 16:24

Rappelons le but : représenter des informations venant d'un dataset de BrightKite sous forme de visu orientée pixel

Une section sur la mise en place des données initiales car ce fut coton (on ne l'avait pas fait pendant le cours, on travaillait sur l'algorithme)

Le dataset

Le script fourni en cours n'est qu'une classe et on doit lui ajouter les deux lignes suivantes en plus :

from math import sqrt
from datetime import datetime
 
class BrightKite:
...
    def run(self):
        self.filterCheckins()
        self.filteredEdges()
 
# A la fin, les deux lignes à ajouter afin d'instancier la classe et générer les fichiers csv
br = BrightKite(50)
br.run()

Le devoir

Nous avons travaillé sur un graphe contenant cinquante (50) sommets du dataset de BrightKite.

Cet algo permet d'afficher des points en occupant un maximum d'espace grâce à une forme élémentaire en forme de U qui est rattachée et qui subit une rotation : c'est une courbe fractale. Elle existe en quatre (4) formes : A U C et D

Le principe de l'implémentation de la courbe de Hilbert est l'utilisation de la récursivité : à un niveau N qui dessine la forme élémentaire dans un certain sens et on rappelle en parallèle la fonction sur les autres sommets.

Pour mettre à jour la position d'un sommet, on travaille avec des variables globales (à cause de la récursivité) qui contiennent la position du prochain sommet qui seront modifiées à chaque récursion.

Afin de montrer les différences entre sommets, on travaille sur la propriété numCheckins des sommets et on va normaliser les valeurs afin d'associer une couleur correspondante aux sommets. Chaque sommet aura une nuance de gris correspondante à son nombre de Checkins. Pour normaliser on a récupéré le minimum et le maximum des valeurs au début de l'algorithme

Le code

# Laurent Garcin
# Edwin Planchon
 
from tulip import *
 
#ces deux variables globales permettent de mettre a jour la position du prochain sommet DANS la recursion
globX = 100
globY = 100
 
#les min et max de l'attribut maxCheckins qu'on normalisera apres et qui servira pour le couleur
minCheck = 9999
maxCheck = 0
 
#la distance entre chaque sommet
globDist = 10
 
#faire une boucle dans la recursion sur les sommets ne fonctionnera pas donc on les enfile ici
nodeArray = []
 
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")
 
	#contient les checkins de chaque sommet
	checkingProp = graph.getIntegerProperty("numCheckins")
 
	#met a jour les sommets
	def drawNewNode():
		global globX
		global globY
		global nodeArray
 
		global minCheck
		global maxCheck
 
		#nNode = graph.addNode()
		if len(nodeArray) > 0:
			#on recupere un sommet
			nNode = nodeArray.pop(0)
 
			#mise a jour de la position
			currentNodeLayout = viewLayout.getNodeValue(nNode)
			currentNodeLayout.setX(globX)
			currentNodeLayout.setY(globY)
			viewLayout.setNodeValue(nNode, currentNodeLayout)
 
			#mise a jour de la couleur
			#ici on va normaliser le nombre de checkins pour la couleur du sommet
			currCheck = checkingProp.getNodeValue(nNode)
 
			#le checkin entre 0 et 1
			normValue = (currCheck - minCheck) / (maxCheck - minCheck)
 
			#on change la couleur en fonction de la valeur du checkin
			currColor = viewColor.getNodeValue(nNode)
			currColor.setR(160 * normValue)
			currColor.setG(160 * normValue)
			currColor.setB(160 * normValue)
			viewColor.setNodeValue(nNode, currColor)
 
	#level : le niveau de recursion
	#shape : 0 = U	1 = D		2 = C		3 = A
	def drawHilbertRec(level, shape):
		global globX
		global globY
		global globDist
		tmp = 0
		if level > 0:
			if shape == 0:#partie U
				#--------------------------------------------
				#appel au niveau inferieur en forme de D
				drawHilbertRec(level - 1, 1)
				#modification des coordonnees globales
				tmp = globY
				globY = tmp + globDist
				#dessin de sommet
				drawNewNode()
				#--------------------------------------------
 
				drawHilbertRec(level - 1, 0)
				tmp = globX
				globX = tmp + globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 0)
				tmp = globY
				globY = tmp - globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 2)
			elif shape == 1:#partie D
				drawHilbertRec(level - 1, 0)
				tmp = globX
				globX = tmp + globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 1)
				tmp= globY
				globY = tmp + globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 0)
				tmp = globX
				globX = tmp - globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 3)
			elif shape == 2:#partie C
				drawHilbertRec(level - 1, 3)
				tmp = globX
				globX = tmp - globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 2)
				tmp = globY
				globY = tmp - globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 2)
				tmp = globX
				globX = tmp + globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 0)
			elif shape == 3: #partie A
				drawHilbertRec(level - 1, 2)
				tmp = globY
				globY = tmp - globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 3)
				tmp = globX
				globX = tmp - globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 3)
				tmp = globY
				globY = tmp + globDist
				drawNewNode()
 
				drawHilbertRec(level - 1, 1)
			else:
				print "rien"
 
	def drawHilbert(graph):
		level = 5
		#on commence a dessiner avec une forme en U
		drawHilbertRec(level, 0)
 
	#Afin de pouvoir iterer sur les sommets DANS la recursion, on va les mettre dans une liste
	global nodeArray
 
	#Recuperation des min et max checkins a normaliser
	global minCheck
	global maxCheck
	for node in graph.getNodes():
		currCheck = checkingProp.getNodeValue(node)
		if (currCheck < minCheck):
			minCheck = currCheck
		if (currCheck > maxCheck):
			maxCheck = currCheck
		nodeArray.append(node)
 
	#on lance la procedure de dessin
	drawHilbert(graph)

Ce qui donne un résultat comme ça sur un graphe de 50 sommets :

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/garcin/solution_homework2.txt · Last modified: 2012/04/18 15:45 by melancon