# Visual Analytics Course

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

#la fonction principale
def highlightBFS(graph):
#recuperation du sommet selectionne
startingNode = 0
for node in graph.getNodes():
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
#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
highlightBFS(graph)