User Tools

Site Tools


sion:solution_homework1_exercise2

DFS (suivi d'un Dijkstra en bonus)

Critères Commentaire(s) Points attribués
(2) Algo (justesse) DFS récursif, pas d'animation 1.5
(2) Code (structure) Variables globales même à la fonction main … :-( 1.5
(2) Code (lisibilité) Aucun commentaire dans le code 1.5
(1) Paramétrage (choix sommet départ) Sélection d'un sommet 1
(1) Mise à disposition Il m'a fallu copier coller depuis le wiki … pas de fichier joint. 0
(8) Total 5.5
  • Algo et code: coloration des arêtes bonne idée pour “visualiser” l'arbre implicitement calculé par l'algo. L'absence d'animation empêche d'apprécier l'évolution du parcours DFS.
  • Lisibilité: vous laissez traîner des portions de code inutile dans le main().

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


# Powered by Python 2.7

# To cancel the modifications performed by the script # on the current graph, click on the undo button.

# Some useful keyboards shortcuts : # * Ctrl + D : comment selected lines. # * Ctrl + Shift + D : uncomment selected lines. # * Ctrl + Space : run script. # * Ctrl + F : find selected text. # * Ctrl + R : replace selected text.

from tulip import * from time import time, sleep

# the updateVisualization(centerViews = True) function can be called # during script execution to update the opened views

# the pauseScript() function can also be called to pause the script execution. # To resume the script execution, you will have to click on the “Run script ” button.

# the main(graph) function must be defined # to run the script on the current graph

nbr = 1

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")
for i in graph.getNodes():
	viewShape.setNodeValue(i, 3)
	viewColor.setNodeValue(i, tlp.Color(255,0,0))
	viewLabel.setNodeValue(i, "")
	
for n in graph.getNodes():
	if viewSelection.getNodeValue(n) == True:
		break

parcours_prof(n, graph)

for i in graph.getNodes():
	viewSelection.setNodeValue(i, False)

def marque (n, graph):

global nbr
graph.getStringProperty("viewLabel").setNodeValue(n, str(nbr))
graph.getBooleanProperty("viewSelection").setNodeValue(n, True)
graph.getIntegerProperty("viewShape").setNodeValue(n, 2)
graph.getColorProperty("viewColor").setNodeValue(n, tlp.Color(170,170,120))
nbr += 1

def parcours_prof(n, graph):

marque(n, graph)
for k in graph.getInOutNodes(n):
	if graph.getBooleanProperty("viewSelection").getNodeValue(k) == False:
		parcours_prof(k, graph)

DIJKSTRA

# Powered by Python 2.7

# To cancel the modifications performed by the script # on the current graph, click on the undo button.

# Some useful keyboards shortcuts : # * Ctrl + D : comment selected lines. # * Ctrl + Shift + D : uncomment selected lines. # * Ctrl + Space : run script. # * Ctrl + F : find selected text. # * Ctrl + R : replace selected text.

from tulip import * from collections import *

# the updateVisualization(centerViews = True) function can be called # during script execution to update the opened views

# the pauseScript() function can also be called to pause the script execution. # To resume the script execution, you will have to click on the “Run script ” button.

# the main(graph) function must be defined # to run the script on the current graph

DEPART = “Nantes” ARRIVEE = “Marseille”

def main(graph) :

graph.clear
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")

nbr_node =graph.numberOfNodes()
nbr_edge = graph.numberOfEdges()

tab_poids = {}
tab_ant = {}


for n in graph.getNodes():
	n_lab = viewLabel.getNodeValue(n) 
	tab_poids[n_lab] = [-1, False]
	tab_ant[n_lab] = [""]
	viewColor.setNodeValue(n, tlp.Color(255,0,0))
	for m in graph.getInOutEdges(n):
		e_lab = viewLabel.getEdgeValue(m)
		
tab_poids[DEPART][0] = 0
parcours_fils(graph, DEPART, tab_poids, tab_ant)

t = ARRIVEE
pile = []
i = 0
while t != [""]:
	pile.append(t)
	t = tab_ant[t]
	i = i + 1
while i != 0:
	tmp = pile.pop()
	for j in graph.getNodes():
		if tmp == viewLabel.getNodeValue(j):
			viewColor.setNodeValue(j, tlp.Color(0,255,0))
	i = i - 1	
	

def parcours_fils(graph, noeud, tab_poids, tab_ant):

for n in graph.getNodes():
	if graph.getStringProperty("viewLabel").getNodeValue(n) == noeud:
		for fils in graph.getInOutNodes(n):
			name_fils = graph.getStringProperty("viewLabel").getNodeValue(fils)
			if tab_poids[name_fils][1] == False:
				e = graph.existEdge(n,fils)
				if e.isValid() == False:
					e = graph.existEdge(fils,n)
				poids = graph.getIntegerProperty("Poids").getEdgeValue(e)
				if tab_poids[name_fils][0] > poids + tab_poids[noeud][0] or tab_poids[name_fils][0] == -1:
					tab_poids[name_fils][0] = poids + tab_poids[noeud][0]
					tab_ant[name_fils] = noeud
			tab_poids[noeud][1]=True
min = 10000
j=""
for i in tab_poids:
	if tab_poids[i][1] == False and tab_poids[i][0] != -1:
		if tab_poids[i][0] < min:
			min = tab_poids[i][0]
			j = i 
if min != 10000:
	parcours_fils(graph, j , tab_poids, tab_ant)  
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/sion/solution_homework1_exercise2.txt · Last modified: 2012/03/14 03:35 by melancon