Initialisation du TPE

Le TPE sera réalisé en Python, en se basant sur :

Un graphe représenté sous forme de matrice CSV
La librairie Pandas, qui permet de charger facilement des fichiers CSV
La libraire igraph, qui implémente l'agorithme de Dijkstra pour calculer le chemin de plus court d'un point à un autre.
Le tout est présenté sous forme de notebook Jupyter, qui permet de mixer du code et de la documentation, et d'exécuter le code par étape

Travaux préparatoires

Description pour Windows

Installer un environnement Python 2 à partit du site de Continuum
Installer igraph en utilisant la commande pip install python-igraph
Installer les librairies Cairo (télécharger PyCairo et PyGtk et installer en utilisant la commande pip install nom_du_fichier.whl)

Première étape : initialisation

La première étape consiste à indiquer au langage Python quelles libraires il doit utiliser en utilisant la directive import. Nous allons importer les libraires listées ci-dessus.



In [1]:

    
from igraph import *
import igraph
import pandas as pd

print igraph.__version__

Deuxième étape : chargement de la matrice

La matrice préalablement préparée au format CSV, avec des points-virgules en tant que séparateur, est chargé avec la libraire Pandas. On indique à Pandas :

L'emplacement du fichier
La ligne qui contient les étiquettes de données (le nom des noeuds du graphe)
De même pour la colonne
Le séparateur de données (le point-virgule)



In [2]:

    
#Chargement de la matrice
matrice = pd.read_csv('matrice.csv', header=0, index_col=0, sep=';')

#Affichage de la matrice sous forme de tableau
print matrice









    



           Charlotte  Valentine  David  Sophia
Charlotte          0          1      3       0
Valentine          0          0      1       2
David              0          0      0       2
Sophia             0          0      0       0

Troisième étape : chargement du graphe

Durant cette étape nous transformons la matrice en graphe et lui positionnons quelques attributs (poids des arcs reliant les noeuds, étiquettes, ...).

Nous afficherons le graphe ensuite... de forme pas très intelligible...



In [3]:

    
# Get the values as np.array, it's more convenenient.
valeurs = matrice.values

# Create graph, A.astype(bool).tolist() or (A / A).tolist() can also be used.
graphe = igraph.Graph.Adjacency((valeurs > 0).tolist())

# Add edge weights and node labels.
graphe.es['weight'] = valeurs[valeurs.nonzero()]
graphe.vs['label'] = matrice.index # or a.index/a.columns
graphe.vs['name'] = graphe.vs['label']
graphe.es['width'] = valeurs[valeurs.nonzero()]

print graphe









    



IGRAPH DNW- 4 5 --
+ attr: label (v), name (v), weight (e), width (e)
+ edges (vertex names):
Charlotte->Valentine, Charlotte->David, Valentine->David, Valentine->Sophia,
David->Sophia

Quatrième étape : affichage du graphe

Dessinons le graphe pour le rendre plus intelligible. La verison actuelle d'igraph ne supporte pas encore l'affichage des poids des arcs. Pour compenser, les arcs seront plus épais selon leur poids.



In [4]:

    
layout = graphe.layout('kk')

visual_style = {}
visual_style["vertex_size"] = 20
visual_style["vertex_label"] = graphe.vs["name"]
visual_style["layout"] = layout
visual_style["vertex_color"] = 'blue'
visual_style["margin"] = 20
visual_style["vertex_label_size"] = 12
visual_style["vertex_label_dist"] = 1
visual_style["margin"] = 75


plot(graphe, **visual_style)









    Out[4]:

Cinquième étape : calcul du chemin le plus court

Nous calculerons ici le chemin le plus court entre Charlotte et Sophia. Ce résultat est la durée du parcours le plus cours.



In [60]:

    
res = Graph.shortest_paths(graphe, source='Charlotte',target='Sophia', mode='OUT', weights = graphe.es['weight'])
print res[0][0]

3.0

Le parcours le plus cours est donc un parcours de 3.

Sixème étape : déterminer quel est ce parcours le plus cours

La dernière étape est de déterminer quelles sont les étapes de ce chemin.



In [64]:

    
path = graphe.get_shortest_paths(graphe.vs.select(name='Charlotte')[0], to = 'Sophia', weights = graphe.es['weight'], mode='OUT', output = 'vpath')

print "Le chemin le plus court (durée %i) est le suivant : " %res[0][0]

for step in path[0] : 
    print graphe.vs[step].attributes()['name']









    



Le chemin le plus court (durée 3) est le suivant : 
Charlotte
Valentine
Sophia