User Tools

Site Tools


nilles:solution_homework1_exercise2
Critères Commentaire(s) Points attribués
(2) Algo (justesse) Voir commentaires 1
(2) Code (structure) 2
(2) Code (lisibilité) Le code est éparpillé partout sur la page du wiki … 1
(1) Paramétrage (choix sommet départ) Sélection d'un sommet 1
(1) Mise à disposition Je n'ai pas pu faire tourner votre code, impossible même de le copier coller depuis le wiki … pas de fichier joint. 0
(8) Total 5
  • Algo et code: vous auriez dû utiliser une propriété pour stocker les booléens (visite). Vous enfilé plusieurs fois le mêem élément dans la file (vous ne vérifiez pas s'il y est déjà). Bon point, vous coloriez les arêtes.
  • Lisibilité: vous laissez traîner des portions de code inutile dans le main().

Guy Melançon 2012/03/14 03:44


Parcours en largeur (BFS) :

#-*-coding:utf-8 *-

from tulip import *

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”) 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”)

rouge = tlp.Color(255, 0, 0) vert = tlp.Color(0, 255, 0)

q = [] # Liste qui va nous servir de file pour le parcours en largeur visite = {} # Liste de noeuds visités (True) ou non (False)

# Au début tous les noeuds ne sont pas encore visités # On marque tous les noeuds/arrêtes en rouge for n in graph.getNodes():

visite[n] = False
viewColor.setNodeValue(n, rouge)

for e in graph.getEdges() :

viewColor.setEdgeValue(e, rouge)

# Parcours des noeuds sélectionnés for n in graph.getNodes() :

if viewSelection.getNodeValue(n) :
	q.append(n)	# Ajout des noeuds initiaux à notre file
	viewColor.setNodeValue(n, vert) # Les noeuds visités passent en vert
	visite[n] = True

while q != []:

n = q.pop(0) # Défile.
for u in graph.getInOutNodes(n) :
	if visite[u] == False : 
		q.append(u) # Enfile.		
	
		e = graph.existEdge(n,u)
		if not e.isValid():
			e = graph.existEdge(u,n)
		viewColor.setEdgeValue(e, vert)
		
	visite[u] = True
	viewColor.setNodeValue(u, vert)
	
	updateVisualization()

Parcours en profondeur (DFS) :

Même chose qu'au dessus mais avec une pile au lieu d'une file

#-*-coding:utf-8 *-

from tulip import *

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”) 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”)

rouge = tlp.Color(255, 0, 0) vert = tlp.Color(0, 255, 0)

q = [] # Liste qui va nous servir de pile pour le parcours en profondeur visite = {} # Liste de noeuds visités (True) ou non (False)

# Au début tous les noeuds ne sont pas encore visités # On marque tous les noeuds/arrêtes en rouge for n in graph.getNodes():

visite[n] = False
viewColor.setNodeValue(n, rouge)

for e in graph.getEdges() :

viewColor.setEdgeValue(e, rouge)

# Parcours des noeuds sélectionnés for n in graph.getNodes() :

if viewSelection.getNodeValue(n) :
	q.append(n)	# Ajout des noeuds initiaux à notre pile
	viewColor.setNodeValue(n, vert) # Les noeuds visités passent en vert
	visite[n] = True

while q != []:

n = q.pop() # Dépile.
for u in graph.getInOutNodes(n) :
	if visite[u] == False : 
		q.append(u) # Enfile.		
	
		e = graph.existEdge(n,u)
		if not e.isValid():
			e = graph.existEdge(u,n)
		viewColor.setEdgeValue(e, vert)
		
	visite[u] = True
	viewColor.setNodeValue(u, vert)
	
	updateVisualization()
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/nilles/solution_homework1_exercise2.txt · Last modified: 2012/03/14 03:55 by melancon