User Tools

Site Tools


lauliac:solution_homework1_exercise2
Critères Commentaire(s) Points attribués
(2) Algo (justesse) BFS / file 2
(2) Code (structure) Bonne str de données, clair, gestion exception (!) 2
(2) Code (lisibilité) Excellent 2
(1) Paramétrage (choix sommet départ) Choix sommet départ 1
(1) Mise à disposition Il m'a fallu copier coller depuis le wiki … pas de fichier joint. 0
(8) Total 7
  • Algo et code: coloration des arêtes bonne idée pour “visualiser” l'arbre implicitement calculé par l'algo.
  • Lisibilité: vous laissez traîner des portions de code inutile dans le main().

Guy Melançon 2012/03/14 15:49


Implementation of BFS

One must disable edge color-interpolation to see the graph coloring using this algorithm.

from tulip import *
from collections import deque
 
def main(graph) : 
	viewColor =  graph.getColorProperty("viewColor")
	viewSelection =  graph.getBooleanProperty("viewSelection")
 
	for edge in graph.getEdges():
		viewColor.setEdgeValue(edge, tlp.Color(0, 0, 255));
 
	try:
		startNode = viewSelection.getNodesEqualTo(True).next()
	except Exception:
		startNode = graph.getOneNode()
 
	Marked = set()
	Q = deque()
	Q.append(startNode)
 
	while len(Q) > 0:
		node = Q.popleft()
		edges = graph.getInOutEdges(node)
 
		for edge in edges:
			n = graph.target(edge)
			if n.id == node.id:
				n = graph.source(edge)
 
			if n.id not in Marked:
				viewColor.setEdgeValue(edge, tlp.Color(255, 0, 0))
				Marked.add(n.id)
				Q.append(n)
 
		# uncomment to see colors spreading
		updateVisualization()
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/lauliac/solution_homework1_exercise2.txt · Last modified: 2012/03/14 15:51 by melancon