User Tools

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
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/algorithme_de_dijkstra.txt · Last modified: 2016/05/26 03:46 by melancon