# Visual Analytics Course

### Site Tools

chicoutimi_2016:algorithme_de_dijkstra

# Differences

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

 chicoutimi_2016:algorithme_de_dijkstra [2016/05/26 02:58]melancon chicoutimi_2016:algorithme_de_dijkstra [2016/05/26 03:46]melancon Both sides previous revision Previous revision 2016/05/26 03:46 melancon 2016/05/26 03:05 melancon 2016/05/26 02:58 melancon 2016/05/26 02:57 melancon created Next revision Previous revision 2016/05/26 03:46 melancon 2016/05/26 03:05 melancon 2016/05/26 02:58 melancon 2016/05/26 02:57 melancon created 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. ​ 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 + ​ + + ​ + # 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