Consignes

La partie obligatoire de ce TP sera notée par votre intervenant pendant la séance de TP. Vous devrez donc appeler votre intervenant à chaque fois que vous avez terminé une question.

Les questions « bonus » peuvent être envoyée par email à votre intervenant pendant la semaine (7 jours) qui suivent votre séance de TP. N'oubliez pas de mettre votre nom ainsi que votre filière en commentaire dans les fichiers que vous nous envoyez...

Attention : pour que les questions bonus soient prises en compte, il faut que les questions obligatoires aient été traitées. Si vous n'avez pas fini les questions obligatoires en TP, il faut donc les finir chez vous avant de traiter les questions bonus...

Liens utiles

• la page du langage Python
• la page de la documentation de la librairie standard de Python
• un livre d'apprentissage de la programmation en Python (en français) (lien direct (pdf)) Pour les chaînes de caractères, reportez vous au début de la partie 10.
• email des enseignants
  • Chambéry : Pierre.Hyvernat@univ-savoie.fr (cours, TD et TP), Thomas.Seiller@univ-savoie.fr (TD et TP) et tom.hirschowitz@univ-savoie.fr (TP),
  • Annecy : Christophe.Raffalli@univ-savoie.fr (cours, TD et TP), lionel.valet@univ-savoie.fr (TD et TP) et Ilham.Alloui@univ-savoie.fr (TP).

1. GoogleMap, graphe des distances

Dans ce TP, nous allons utiliser l'API ("Application Programming Interface") GoogleMap qui permet à un utilisateur d'interroger le serveur et récupérer des information utilisables par un programme :

1. on envoie une requête http particulière,
2. au lieu d'une page web (au format html), on obtient un fichier JSON qui contient les informations demandées,
3. on convertit très facilement les données JSON en données Python (ou Java, ou n'importe quel autre langage de programmation...

1.1. Distances entres les villes

1.1.1. Distance entre deux villes

Pour demander la distance (à vol d'oiseau) entre New-York et Los-Angeles, il « suffit » d'aller sur la page web http://maps.googleapis.com/maps/api/distancematrix/json?origins=New-York&destinations=los-angeles&sensor=false . Le résultat sera une page-web spéciale dans un format texte appellé "JSON" :

{
   "destination_addresses" : [ "Los Angeles, Californie, États-Unis" ],
   "origin_addresses" : [ "New York, État de New York, États-Unis" ],
   "rows" : [
      {
         "elements" : [
            {
               "distance" : {
                  "text" : "4 469 km",
                  "value" : 4469340
               },
               "duration" : {
                  "text" : "1 jour 21 heures",
                  "value" : 161474
               },
               "status" : "OK"
            }
         ]
      }
   ],
   "status" : "OK"
}

On voit bien la distance entre les deux villes dans le champs "value", du dictionnaire "distance" qui est l'unique élément d'une liste etc.

Pour récupérer cette page web, le mieux est d'utiliser la fonction "get_url" suivante, qui gardera une copie locale afin d'éviter que des requêtes successives pour les même informations repassent par le réseau.

import urllib.request
import os
import hashlib

def get_url(url, local=True, binaire=False):
    """charge une url et crée une version dans un cache local.
    Lors des requêtes suivantes, la verstion en cache est chargée
    si local=True.
    Pour des fichiers binaires (images), utiliser "binaire=True"."""
    if not os.path.exists("url_cache"):
        os.makedirs("url_cache/")
    nom_fichier = "url_cache/"+hashlib.md5(url.encode("utf8")).hexdigest() + ".tmp"

    if os.path.exists(nom_fichier) and local:
        text = open(nom_fichier, "rb" if binaire else "r").read()
    else:
        fichier = open(nom_fichier, "wb" if binaire else "w")
        text = urllib.request.urlopen(url).read()
        if not binaire:
            text = text.decode("utf8","ignore") + '\n'
        fichier.write(text)
        fichier.close()
    return(text)

1.1.2. Distances entres plusieurs villes

Il est possible de récupérer les distances entre une liste de ville et une autre liste de villes :

Une requête sur l'url http://maps.googleapis.com/maps/api/distancematrix/json?origins=tokyo|hokkaido&destinations=tokyo|osaka|kyoto&sensor=false donne le résultat

{
   "destination_addresses" : [
      "Tokyo, Japon",
      "Ōsaka, Préfecture d'Ōsaka, Japon",
      "Kyōto, Préfecture de Kyōto, Japon"
   ],
   "origin_addresses" : [ "Tokyo, Japon", "Hokkaido Prefecture, Japon" ],
   "rows" : [
      {
         "elements" : [
            {
               "distance" : {
                  "text" : "1 m",
                  "value" : 0
               },
               "duration" : {
                  "text" : "1 minute",
                  "value" : 0
               },
               "status" : "OK"
            },
            {
               "distance" : {
                  "text" : "512 km",
                  "value" : 512076
               },
               "duration" : {
                  "text" : "6 heures 41 minutes",
                  "value" : 24033
               },
               "status" : "OK"
            },
            {
               "distance" : {
                  "text" : "465 km",
                  "value" : 464930
               },
               "duration" : {
                  "text" : "6 heures 9 minutes",
                  "value" : 22112
               },
               "status" : "OK"
            }
         ]
      },
      {
         "elements" : [
            {
               "distance" : {
                  "text" : "1 134 km",
                  "value" : 1134088
               },
               "duration" : {
                  "text" : "17 heures 52 minutes",
                  "value" : 64337
               },
               "status" : "OK"
            },
            {
               "distance" : {
                  "text" : "1 493 km",
                  "value" : 1493375
               },
               "duration" : {
                  "text" : "23 heures 49 minutes",
                  "value" : 85751
               },
               "status" : "OK"
            },
            {
               "distance" : {
                  "text" : "1 446 km",
                  "value" : 1446230
               },
               "duration" : {
                  "text" : "23 heures 17 minutes",
                  "value" : 83831
               },
               "status" : "OK"
            }
         ]
      }
   ],
   "status" : "OK"
}

Le résultat s'interprète de la manière suivante :

1. les villes de départ ("origin_addresses") sont
   • Tokyo
   • Hokkaido
   dans cet ordre,
2. les villes d'arrivée ("destination_addresses") sont
   • Tokyo
   • Ōsaka
   • Kyōto
   dans cet ordre,
3. la suite est une liste de "lignes" ("rows") dans l'ordre des villes de départ
4. chaque ligne contient une liste d'éléments ("elements") dans l'ordre des villes de d'arrivée
5. chaque élément contient la distance et la durée du trajet entre la ville de départ et la ville d'arrivée correspondante.

Par exemple, le résultat si dessus peut se résumer en un tableau :

>>> import urllib.parse
>>> urllib.parse.quote("Chambéry")
'Chamb%C3%A9ry'

Le résultat de la fonction "distances_villes" est une grosse chaîne de caractères. Vous pouvez transformer cette chaîne en données structurées avec le code Python suivant :

import json

    ... # la variable "resultat" contient la chaîne produite par une url
    u = json.loads(resultat)
    distances = {}
    for d in range(len(u["origin_addresses"])):
        ville_depart = u["origin_addresses"][d]
        distances[ville_depart] = {}
        for a in range(len(u["destination_addresses"])):
            ville_arrivee = u["destination_addresses"][a]
            value = int(u["rows"][d]["elements"][a]["distance"]["value"])
            distances[ville_depart][ville_arrivee] = value

>>> affiche_distances(distances)
Distance de Tokyo, Japon à Tokyo, Japon  =  0 mètres.
Distance de Tokyo, Japon à Ōsaka, Préfecture d'Ōsaka, Japon  =  512076 mètres.
Distance de Tokyo, Japon à Kyōto, Préfecture de Kyōto, Japon  =  464930 mètres.
Distance de Hokkaido Prefecture, Japon à Tokyo, Japon  =  1134088 mètres.
Distance de Hokkaido Prefecture, Japon à Ōsaka, Préfecture d'Ōsaka, Japon  =  1493375 mètres.
Distance de Hokkaido Prefecture, Japon à Kyōto, Préfecture de Kyōto, Japon  =  1446230 mètres.

1.1.3. Bonus

Un fichier JSON contient une description au format texte d'une valeur Python. On peut transformer une chaîne JSON en véritable valeur avec la fonction "json.loads(chaîne)".

>>> json.loads('{ "a": [1,2,3], "b": { "c": "toto" } }')
{'a': [1, 2, 3], 'b': {'c': 'toto'}}

   raise DistanceError(chaîne)

class DistanceError(Exception):
    def __init__(self,msg):
        self.msg=msg
    def __str__(self):
        return(self.msg)

>>> eloignement(["Paris", "Lyon", "Marseille"])
Il faut 7 hours 47 mins pour aller de
  - Marseille, France
à
  - Paris, France.

1.2. Calcul du plus court chemin pour aller dans plusieurs villes

Étant donné une liste de ville, nous allons essayer de résoudre le problème du voyageur de commerce : comment se rendre dans toutes les villes en minimisant la distance totale parcourue. Ce problème est très complexe lorsque le nombre de villes atteint l'ordre d'une centaine. Nous nous restreindrons à un petit nombre de villes (une dizaine) pour pouvoir utiliser un algorithme naïf.

L'idée est simplement de tester toutes les possibilités et de garder la meilleure !

Pour générer toutes les possibilités, on utilisera ensuite la fonction "permutations" de la bibliothèque "itertools" :

>>> from itertools import permutations
>>> for l in permutations([1,2,3]):
...         print(list(l))
...
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

1.2.1. Un algorithme plus rapide (BONUS)

Le problème quand on teste toutes les permutations possibles, c'est que ça prend du temps. (Pour n villes, cela fait n! permutations à regarder...)

On peut essayer d'optimiser la distance localement, on choisissant, à chaque fois, la ville la plus proche de là où on se trouve. De cette manière, on n'a pas à explorer toutes les permutations.

>>> d = { "a" : 0 , "b" : 12742 , "c" : 111 }
>>> print(d)
{'a': 0, 'c': 111, 'b': 12742}
>>> del d["b"]
>>> print(d)
{'a': 0, 'c': 111}

2. GoogleMap, image du résultat (BONUS)

2.1. Récupérer une carte du trajet

Vous pouvez maintenant afficher l'image correspondante avec la fonction suivante :

from tkinter import *
import binascii

def affiche_carte(url):
    """affiche la carte correspondant à l'url donnée en argument (q pour fermer la fenêtre)"""

    img = get_url(url,binaire=True)
    img = binascii.b2a_base64(img)

    root = Tk()
    photo=PhotoImage(data=img)
    labl = Label(root, image=photo)
    labl.pack() ;
    root.bind("q", lambda _: root.destroy())
    root.mainloop()

Remarque : on utilise encore "get_url" en précisant bien que l'url ne pointe pas sur un fichier au format texte.

2.2. Interface graphique