User Tools

Site Tools


garcin:solution_homework1_exercise2

Visual Analytics Course

Chicoutimi roadmap / Laurent Garcin's corner

Solution to Homework 1 / Exercice 2 - ''python'' code that traverses the graph either using BFS or DFS

Critères Commentaire(s) Points attribués
(2) Algo (justesse) DFS / file 1
(2) Code (structure) Bien 2
(2) Code (lisibilité) Voir commentaires 1.5
(1) Paramétrage (choix sommet départ) Aucun. Utilisation de la fct getOneNode() 0
(1) Mise à disposition Il m'a fallu copier coller depuis le wiki … pas de fichier joint. 0
(8) Total 4.5
  • Algo: incorrect, tous les sommets ne sont pas coloriés …
  • Lisibilité: vous laissez traîner des portions de code inutile dans le main().

Guy Melançon 2012/03/09 22:03


L'algorithme BFS qui modifie les noeuds :

#Created by Laurent Garcin 19/02/2012 for Visual Analytics course
 
from tulip import *
import Queue
 
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")
 
	#permet de savoir si le sommet a deja ete visite
	viewAlreadyVisited = graph.getBooleanProperty("viewAlreadyVisited")
 
	#la fonction principale
	def highlightBFS(graph):
		#recuperation du sommet selectionne		
		startingNode = 0
		for node in graph.getNodes():
			viewAlreadyVisited.setNodeValue(node, False)
			if viewSelection.getNodeValue(node):
				startingNode = node
				break
		if startingNode == 0:
			print "erreur - vous devez selectionner un sommet de depart"
			return
 
		#la file qui va stocker les sommets a traiter
		queue = Queue.Queue(0)
 
		#algo de BFS
		queue.put(startingNode)
		while not queue.empty():
			#currentNode est le noeud actuel que l'on va traiter
			currentNode = queue.get()
 
			#on traite le noeud si et seulement si on ne l'a pas marque avant
			if not viewAlreadyVisited.getNodeValue(currentNode):
				#traitement du sommet - couleur = jaune
				currentNodeColor = viewColor.getNodeValue(currentNode)
				currentNodeColor.setR(230)
				currentNodeColor.setG(220)
				currentNodeColor.setB(0)						
				viewColor.setNodeValue(currentNode, currentNodeColor)
 
				#traitement du sommet - forme = rond
				viewShape.setNodeValue(currentNode, 3)				
 
                                #on enfile les sommets voisins
				for neighborCurrentNode in graph.getInOutNodes(currentNode):
					queue.put(neighborCurrentNode)
 
			#on marque le sommet
			viewAlreadyVisited.setNodeValue(currentNode, True)
 
	highlightBFS(graph)
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/garcin/solution_homework1_exercise2.txt · Last modified: 2012/03/14 15:16 by melancon