User Tools

Site Tools


chicoutimi_2016:algorithme_de_dijkstra

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Last revision Both sides next revision
chicoutimi_2016:algorithme_de_dijkstra [2016/05/26 02:58]
melancon
chicoutimi_2016:algorithme_de_dijkstra [2016/05/26 03:05]
melancon
Line 10: Line 10:
  
 ==== Algorithme de Dijkstra ==== ==== Algorithme de Dijkstra ====
 +---
 +
 +L'​algorithme tel qu'il est formulée traite le cas des arêtes pondérées (il reste à adapter le code pour prendre en compte la propriété qui stocke le poids des arêtes).
 +
 +On propose deux version, objet ou impératif. La version objet facilite le partage de variables entre les méthodes -- c'est l'un des buts.
  
 <file python Disjkstra_objet.py>​ <file python Disjkstra_objet.py>​
Line 39: Line 44:
  
 # the main(graph) function must be defined ​ # the main(graph) function must be defined ​
 +# to run the script on the current graph
 +
 +def min_distanceNode(graph,​ distance_map,​ node_set):
 + min_node = None
 + min_index = 0
 + min_dist = graph.numberOfNodes()
 + for i, n in enumerate(node_set):​
 + if distance_map[n] < min_dist:
 + min_node = n
 + min_index = i
 + min_dist = distance_map[n]
 + return min_index, min_node
 +
 +def main(graph): ​
 + viewColor = graph.getColorProperty("​viewColor"​)
 + viewLabel = graph.getStringProperty("​viewLabel"​)
 + viewLabelColor = graph.getColorProperty("​viewLabelColor"​)
 + viewLayout = graph.getLayoutProperty("​viewLayout"​)
 + viewMetric = graph.getDoubleProperty("​viewMetric"​)
 + viewSelection = graph.getBooleanProperty("​viewSelection"​)
 + viewShape = graph.getIntegerProperty("​viewShape"​)
 + viewSize = graph.getSizeProperty("​viewSize"​)
 +
 + # sommet source (selectionne)
 + source = None
 + for n in graph.getNodes():​
 + if viewSelection[n]:​
 + source = n
 + break
 +
 + distance_to_source = {}
 + parent = {}
 + non_visited_nodes = [n for n in graph.getNodes()]
 +
 + # initialisation
 + for n in graph.getNodes():​
 + distance_to_source[n] = graph.numberOfNodes()
 + distance_to_source[source] = 0
 +
 + parent[source] = None
 +
 + while len(non_visited_nodes) > 0:
 + i, node = min_distanceNode(graph,​ distance_to_source,​ non_visited_nodes)
 + non_visited_nodes.pop(i)
 + for neigh in graph.getInOutNodes(node):​
 + if distance_to_source[neigh] > distance_to_source[node] + 1:
 + distance_to_source[neigh] = distance_to_source[node] + 1
 + parent[neigh] = node
 +
 + for n in parent.keys():​
 + if parent[n] != None:
 + e = graph.existEdge(n,​ parent[n], False)
 + viewSelection[e] = True
 +</​file>​
 +
 +<file python Dijkstra_imperatif.py>​
 +# 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 + I : indent selected lines.
 +#   * Ctrl + Shift + I  : unindent selected lines.
 +#   * Ctrl + Return ​ : run script.
 +#   * Ctrl + F  : find selected text.
 +#   * Ctrl + R  : replace selected text.
 +#   * Ctrl + Space  : show auto-completion dialog.
 +
 +from tulip import *
 +
 +# the updateVisualization(centerViews = True) function can be called
 +# during script execution to update the opened views
 +
 +# the pauseScript() function can be called to pause the script execution.
 +# To resume the script execution, you will have to click on the "Run script " button.
 +
 +# the runGraphScript(scriptFile,​ graph) function can be called to launch another edited script on a tlp.Graph object.
 +# The scriptFile parameter defines the script name to call (in the form [a-zA-Z0-9_]+.py)
 +
 +# the main(graph) function must be defined
 # to run the script on the current graph # to run the script on the current graph
  
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/algorithme_de_dijkstra.txt · Last modified: 2016/05/26 03:46 by melancon