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
Next revision
Previous revision
chicoutimi_2016:algorithme_de_dijkstra [2016/05/26 02:58]
melancon
chicoutimi_2016:algorithme_de_dijkstra [2016/05/26 03:46]
melancon
Line 8: Line 8:
  
   * [[chicoutimi_2016:​session_by_session_cutdown|Back to the course start page]]   * [[chicoutimi_2016:​session_by_session_cutdown|Back to the course start page]]
 +    * [[chicoutimi_2016:​code_examples|Back to the code example page]]
  
 ==== 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 45:
  
 # 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