# Visual Analytics Course

### Site Tools

chicoutimi_2016:algorithme_de_dijkstra

# Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

## Chicoutimi Summer 2016 roadmap / May 3, 3pm course

### 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.

Disjkstra_objet.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

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
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

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