Graphique

[sos-math(21)]

Bonjour,
j'ai bien reçu tes scripts et je t'en remercie.
Pour ces scripts, les données sont sous forme d'une liste de listes, ce qui ne correspond pas à notre travail.
Il faudrait donc adapter notre dictionnaire et le convertir en liste de listes.
As-tu une idée du "comment faire" ?
Bonne continuation

[Invité]

Merci pour cette réponse.

J'ai réfléchi toute la journée et pour l'instant je ne vois pas de solution...

Pensez-vous qu'il vaille mieux adapter les fonctions de Dijkstra pour qu'elles acceptent des dictionnaires, ou transformer notre structure pour que les fonctions Dijkstra puissent la lire ?

Merci encore.

[sos-math(21)]

Bonjour,
à mon avis, le plus simple est de faire évoluer notre structure de données.
Il faut donc que tu essaies de transformer notre dictionnaire de dictionnaires en une liste de listes mais ce serait bien que ton professeur précise la structure exacte de la variable source de ses algorithmes de Dijkstra : comment repère-t-on un nœud dans le graphe ? Est-ce qu'il est repéré par son nom en tête de liste ou y-a-t-il un système de numérotation des gares en amont ?
Bonne continuation

[Invité]

Merci beaucoup pour votre réponse.

Mon prof m'a répondu par mail et m'a dit que le code Python de Dijkstra qu'il a donné et que je vous ai envoyé est un exemple. Selon lui il est possible d'adapter Dijkstra et même trouver une autre version sur internet si besoin.

Pensez-vous que ce soit une bonne idée ?

Parce qu'il a dit ensuite que c'était à moi de voir s'il était vraiment judicieux de changer Dijkstra. Donc il n'est pas très clair... Peut-on appliquer Dijkstra à un dictionnaire ?

Merci encore pour votre aide.

[sos-math(21)]

Bonjour,
oui, il est tout à fait possible d'appliquer dijkstra à un dictionnaire de dictionnaires.
Je te laisse consulter cette page qui propose une implémentation de l'algorithme de Dijkstra avec un dictionnaire de dictionnaires :
http://informathix.tuxfamily.org/?q=node/119
Bon courage

[Invité]

C'est génial !

Mais nous quel serait le graphe ?

Je n'arrive pas à trouver pour notre cas l'analogue de celui présenté.

[sos-math(21)]

Bonjour,
pour nous, le graphe serait le dictionnaire de dictionnaires des gares avec les gares adjacentes et leurs distances.
J'ai donc, une nouvelle fois, retouché le code pour que cela fonctionne : désormais la fonction dico_adjacence() renvoie le dictionnaire des gares auxquelles j'ai associé les gares adjacentes et leurs distances.
Je te redonne le code complet pour qu'il n'y ait pas d’ambiguïté :

Code : Tout sélectionner

import csv

def conversion(chaine):
    """ convertit un point kilométrique de la forme 'km+m' ou 'km-m' en nombre flottant km.m"""
    if "+" in chaine :
        return float(chaine.split("+")[0]+"."+chaine.split("+")[1])
    elif "-" in chaine:
        return float(chaine.split("-")[0]+"."+chaine.split("-")[1])

### extraction des colonnes du fichier liste des gares : on a besoin du code UIC (0),du libellé (1), du code ligne(4), du point kilométrique (6) et on ne prend que les lignes de fret (if ligne[2]=='O'). Dans ce fichier les gares apparaissent autant de fois que les lignes auxquelles elles appartiennent

with open('liste-des-gares.csv',newline='',encoding='utf-8') as h :
    extraction  = csv.reader(h)
    liste_brute = [ligne for ligne in extraction]
    liste_brute = liste_brute[1:]
    liste_gares = [[int(ligne[0]),ligne[1],int(ligne[4]),conversion(ligne[6])] for ligne in liste_brute if ligne[2]=='O']

### Construction du dictionnaire des gares
def dico_lignes_alg() :
    """créé un dictionnaire contenant les gares et les lignes auxquelles elles appartiennent, avec les gares de ces lignes et les distances algébriques avec la gare considérée"""
    dico={}
    for gare in liste_gares :
        dico_noeud = {}
        for element in liste_gares :
            if element[0] != gare[0] and element[2] == gare[2]:
                if element[2] not in dico_noeud.keys() :
                    dico_noeud[element[2]]=[(element[1],gare[3]-element[3])]
                else :
                    dico_noeud[element[2]].append((element[1],gare[3]-element[3]))
        if gare[1] in dico.keys():
            dico[gare[1]].update(dico_noeud)
        else :
            dico[gare[1]] = dico_noeud
    return dico

### Construction du dictionnaire d'adjacence
def dico_adjacence() :
    """créé un dictionnaire de dictionnaires contenant les gares et leurs distances aux noeuds les plus proches sur les lignes auxquelles elles appartiennent"""
    dico = dico_lignes_alg()
    adjacence = {}
    for gare in dico.keys() :
        for ligne in dico[gare].keys():
            liste_amont = [element for element in dico[gare][ligne] if element[1]<0]
            if liste_amont != []:
                dico_amont = {}
                liste_amont_triee = sorted(liste_amont, key=lambda t: t[1])
                maximum = max(liste_amont_triee,key=lambda t: t[1])
                dico_amont[maximum[0]] = abs(maximum[1])
                if gare not in adjacence.keys() :
                    adjacence[gare] = dico_amont
                else :
                    adjacence[gare].update(dico_amont)
            liste_aval = [element for element in dico[gare][ligne] if element[1]>0]
            if liste_aval != []:
                dico_aval = {}
                liste_aval_triee = sorted(liste_aval, key=lambda t: t[1])
                minimum = min(liste_aval_triee,key=lambda t: t[1])
                dico_aval[minimum[0]] = abs(minimum[1])
                if gare not in adjacence.keys() :
                    adjacence[gare]=dico_aval
                else :
                    adjacence[gare].update(dico_aval)

    return adjacence

L'appel de cette fonction donne bien ce que l'on veut :

Code : Tout sélectionner

>>> dico_adjacence()['Poitiers'] # recherche des gares adjacentes à Poitiers
{'Couhé-Vérac': 33.5, 'Chasseneuil (Vienne)': 8.411999999999978, 'St-Jean-de-Sauves': 34.973}

Bonne continuation

[Invité]

C'est vraiment super !
Est-ce que le lien que vous m'avez donné avec l'algorithme de Dijkstra pour les dictionnaires fonctionne avec ça ?

En fait je ne comprends pas ce qu'attend en entrée le programme de votre lien ni ce qu'il est censé retourner.

Pourtant je l'ai bien examiné...

Je sens que je progresse énormément grâce à Vous, j'apprends plein de choses en Python, merci beaucoup !

Bon dimanche.

[sos-math(21)]

Bonjour,
le lien que je t'ai donné fonctionne avec ce dictionnaire. En revanche le programme proposé est une version récursive de Dijkstra, est-ce que tu connais le principe de la récursivité ?
Le programme complet est donc :

Code : Tout sélectionner

import csv

def conversion(chaine):
    """ convertit un point kilométrique de la forme 'km+m' ou 'km-m' en nombre flottant km.m"""
    if "+" in chaine :
        return float(chaine.split("+")[0]+"."+chaine.split("+")[1])
    elif "-" in chaine:
        return float(chaine.split("-")[0]+"."+chaine.split("-")[1])

### extraction des colonnes du fichier liste des gares : on a besoin du code UIC (0),du libellé (1), du code ligne(4), du point kilométrique (6) et on ne prend que les lignes de fret (if ligne[2]=='O'). Dans ce fichier les gares apparaissent autant de fois que les lignes auxquelles elles appartiennent

with open('liste-des-gares.csv',newline='',encoding='utf-8') as h :
    extraction  = csv.reader(h)
    liste_brute = [ligne for ligne in extraction]
    liste_brute = liste_brute[1:]
    liste_gares = [[int(ligne[0]),ligne[1],int(ligne[4]),conversion(ligne[6])] for ligne in liste_brute if ligne[2]=='O']

### Construction du dictionnaire des gares
def dico_lignes_alg() :
    """créé un dictionnaire contenant les gares et les lignes auxquelles elles appartiennent, avec les gares de ces lignes et les distances algébriques avec la gare considérée"""
    dico={}
    for gare in liste_gares :
        dico_noeud = {}
        for element in liste_gares :
            if element[0] != gare[0] and element[2] == gare[2]:
                if element[2] not in dico_noeud.keys() :
                    dico_noeud[element[2]]=[(element[1],gare[3]-element[3])]
                else :
                    dico_noeud[element[2]].append((element[1],gare[3]-element[3]))
        if gare[1] in dico.keys():
            dico[gare[1]].update(dico_noeud)
        else :
            dico[gare[1]] = dico_noeud
    return dico

### Construction du dictionnaire d'adjacence
def dico_adjacence() :
    """créé un dictionnaire de dictionnaires contenant les gares et leurs distances aux noeuds les plus proches sur les lignes auxquelles elles appartiennent"""
    dico = dico_lignes_alg()
    adjacence = {}
    for gare in dico.keys() :
        for ligne in dico[gare].keys():
            liste_amont = [element for element in dico[gare][ligne] if element[1]<0]
            if liste_amont != []:
                dico_amont = {}
                liste_amont_triee = sorted(liste_amont, key=lambda t: t[1])
                maximum = max(liste_amont_triee,key=lambda t: t[1])
                dico_amont[maximum[0]] = abs(maximum[1])
                if gare not in adjacence.keys() :
                    adjacence[gare] = dico_amont
                else :
                    adjacence[gare].update(dico_amont)
            liste_aval = [element for element in dico[gare][ligne] if element[1]>0]
            if liste_aval != []:
                dico_aval = {}
                liste_aval_triee = sorted(liste_aval, key=lambda t: t[1])
                minimum = min(liste_aval_triee,key=lambda t: t[1])
                dico_aval[minimum[0]] = abs(minimum[1])
                if gare not in adjacence.keys() :
                    adjacence[gare]=dico_aval
                else :
                    adjacence[gare].update(dico_aval)

    return adjacence

import sys

# récupérer la limite
limite = sys.getrecursionlimit()
# changer la limite
sys.setrecursionlimit(10000)

"""
Quelques fonctions python utiles ici :

- on va rentrer un graphe comme un dictionnaire de dictionnaires pour pouvoir pondérer les arêtes:
g = {'a': {'b': 4, 'c': 2},
     'b': {'a' : 4,'d': 5, 'c': 1},
     'c': {'a' : 2, 'b' : 1, 'd' : 8,'e': 10},
     'd': {'b': 5, 'c': 8, 'e': 2},
     'e': {'c': 10, 'd' : 2, 'f': 3},
     'f': {'e' : 3,'d' : 6}}

Ainsi, g['a'] est le dictionnaire des voisins avec leurs poids :

>>> g['a']
{'c': 2, 'b': 4}
>>> g['a']['b']
4
>>> 'c' in g['a']
True

- pour trouver la clé correspondant à la valeur mini d'un dictionnaire, on utilise une syntaxe très pythonesque. Par exemple, pour avoir le voisin le plus proche de 'a' :

>>> min(g['a'], key = g['a'].get)
'c'

- dict.get(cle,defaut) : retourne la valeur de cle si elle se trouve dans le dictionnaire et defaut sinon ;

- float('inf') représente l'infini

"""




def affiche_peres(pere,depart,extremite,trajet):
    """
    À partir du dictionnaire des pères de chaque sommet on renvoie
    la liste des sommets du plus court chemin trouvé. Calcul récursif.
    On part de la fin et on remonte vers le départ du chemin.

    """
    if extremite == depart:
        return [depart] + trajet
    else:
        return (affiche_peres(pere, depart, pere[extremite], [extremite] + trajet))

def plus_court(graphe,etape,fin,visites,dist,pere,depart):
    """
    Trouve récursivement la plus courte chaine entre debut et fin avec l'algo de Dijkstra
    visites est une liste et dist et pere des dictionnaires
    graphe  : le graphe étudié                                                               (dictionnaire)
    étape   : le sommet en cours d'étude                                                     (sommet)
    fin     : but du trajet                                                                  (sommet)
    visites : liste des sommets déjà visités                                                 (liste de sommets)
    dist    : dictionnaire meilleure distance actuelle entre départ et les sommets du graphe (dict sommet : int)
    pere    : dictionnaire des pères actuels des sommets correspondant aux meilleurs chemins (dict sommet : sommet)
    depart  : sommet global de départ                                                        (sommet)
    Retourne le couple (longueur mini (int), trajet correspondant (liste sommets))

    """
    # si on arrive à la fin, on affiche la distance et les peres
    if etape == fin:
       return dist[fin], affiche_peres(pere,depart,fin,[])
    # si c'est la première visite, c'est que l'étape actuelle est le départ : on met dist[etape] à 0
    if  len(visites) == 0 : dist[etape]=0
    # on commence à tester les voisins non visités
    for voisin in graphe[etape]:
        if voisin not in visites:
            # la distance est soit la distance calculée précédemment soit l'infini
            dist_voisin = dist.get(voisin,float('inf'))
            # on calcule la nouvelle distance calculée en passant par l'étape
            candidat_dist = dist[etape] + graphe[etape][voisin]
            # on effectue les changements si cela donne un chemin plus court
            if candidat_dist < dist_voisin:
                dist[voisin] = candidat_dist
                pere[voisin] = etape
    # on a regardé tous les voisins : le noeud entier est visité
    visites.append(etape)
    # on cherche le sommet *non visité* le plus proche du départ
    non_visites = dict((s, dist.get(s,float('inf'))) for s in graphe if s not in visites)
    noeud_plus_proche = min(non_visites, key = non_visites.get)
    # on applique récursivement en prenant comme nouvelle étape le sommet le plus proche
    return plus_court(graphe,noeud_plus_proche,fin,visites,dist,pere,depart)

def dij_rec(graphe,debut,fin):
    return plus_court(graphe,debut,fin,[],{},{},debut)

if __name__ == "__main__":
    g3 = {'a': {'d': 2, 'g': 2},
          'b': {'a' : 1},
          'c': {'b' : 1, 'f' : 2, 'g' : 3},
          'd': {'g': 4, 's': 7},
          'e': {'a': 5, 'b' : 3, 'c': 2},
          'f': {'d' : 1,'s' : 6},
          'g': {'f' :4},
          's':{}
    }
    l3,c3 = dij_rec(g3,'e','s')
    print('Plus court chemin ex3 : ',c3, ' de longueur :',l3)
    g4 = {'a': {'d': 5, 'e': 7, 'b' : 2},
          'b': {'e' : 4, 'c' : 9},
          'c': {'e' : 4, 'g' : 6},
          'd': {'e': 3, 'f': 5},
          'e': {'f': 3, 'g' : 4},
          'f': {'h' : 5},
          'g': {'h' : 3},
          'h': {}
    }
    l4,c4 = dij_rec(g4,'a','h')
    print('Plus court chemin ex4 : ',c4, ' de longueur :',l4)



"""
Réponse :
Plus court chemin ex3 :  ['e', 'c', 'f', 's']  de longueur : 10
Plus court chemin ex4 :  ['a', 'b', 'e', 'g', 'h']  de longueur : 13
"""

J'ai fait quelque tests :

Code : Tout sélectionner

>>> dij_rec(dico_adjacence(),'Poitiers','Thionville')
(767.844, ['Poitiers', 'Chasseneuil (Vienne)', 'Jaunay-Clan', 'La Tricherie', 'Naintré-les-Barres', 'Châtellerault', 'Ingrandes-sur-Vienne', 'Les Ormes-sur-Vienne', 'Port-de-Piles', 'Ste-Maure-Noyant', 'Villeperdue', 'St-Pierre-des-Corps', 'Blois-Chambord', 'Mer', 'Les Aubrais-Orléans', 'Artenay', 'Toury', 'Étampes', 'Brétigny', 'Juvisy', 'Villeneuve-le-Roi', 'Choisy-le-Roi', 'Rungis (MIN)', 'Wissous', 'Massy-Palaiseau', 'Longjumeau', 'Valenton', 'Sucy-Bonneuil', "Verneuil-l'Étang", 'Gretz-Armainvilliers', 'Tournan', 'Marles-en-Brie', 'Coulommiers', 'Esternay', 'Sézanne', 'Connantre', 'Fère-Champenoise', 'Vitry-le-François', 'Revigny', 'Nançois-Tronville', 'Lérouville', 'Metz-Ville', 'Metz-Chambière', 'Woippy', 'Hagondange', 'Uckange', 'Thionville'])
>>> 

Code : Tout sélectionner

>>> dij_rec(dico_adjacence(),'Rennes','Clermont-Ferrand')
(823.9270000000001, ['Rennes', 'Les Lacs', 'Vitré', 'St-Pierre-la-Cour', 'Laval', 'Neau', 'Voutré', 'Sillé-le-Guillaume', 'Le Mans', 'Sablé-sur-Sarthe', 'Tiercé', 'Écouflant', 'Angers-Maître-École', 'Loudun', 'Le Bouchet', 'Châtellerault', 'Ingrandes-sur-Vienne', 'Les Ormes-sur-Vienne', 'Port-de-Piles', 'La Haye-Descartes', 'Tournon-St-Martin', 'Argenton-sur-Creuse', 'Celon', 'La Souterraine', 'St-Sulpice-Laurière', 'Guéret', 'Lavaufranche', 'Archignat', 'Huriel', 'Montluçon-Ville', 'Commentry', 'Gannat', 'Pontmort', 'Riom-Châtel-Guyon', 'Gerzat', 'Clermont-Ferrand'])

Bonne continuation

[Invité]

Oui je connais la récursivité.

Donc est-ce qu'il vaut mieux utiliser mon programme Dihkstra avec la récursivité ou l'autre avec le dictionnaire ?

Encore merci, on avance.

[sos-math(21)]

Bonjour,
c'est toi qui vois, le programme que je t'ai envoyé hier est pleinement fonctionnel, simplement la récursivité peut allonger le temps de recherche et il faut augmenter le nombre d'appels récursifs initialement prévu dans Python (1000 initialement que j'ai porté à 10000 avec la commande du module syst, c'est fait dans le script que je t'ai envoyé) :

Code : Tout sélectionner

import sys

# récupérer la limite
limite = sys.getrecursionlimit()
# changer la limite
sys.setrecursionlimit(10000)

Si tu as le temps, tu peux chercher à adapter la version de ton prof (qui doit être itérative) à ton type de données ou inversement adapter ton format de données à son programme. Dans tous les cas, c'est un bon exercice pour comprendre les programmes qu'il te propose.
Bonne continuation

[Invité]

Merci, je comprends mieux ! Je pense que je vais rester sur la version récursive.

Maintenant, je me pose une autre question : oû dans le code entre-t-on la gare de départ et d'arrivée ?

Par exemple si l'on veut appliquer l'algorithme de Dijkstra pour un trajet Angers-Marseille, oû saisit on Angers et Marseille dans le programme ? Ça je n'ai pas encore compris...

Encore une fois merci, j'apprends beaucoup.

[sos-math(21)]

Bonjour
Si tu regardes bien mon avant-dernier dernier message, tu verras que je t’ai mis un exemple d’appel de la fonction.
Relis le et tu comprendras.
Bonne continuation

[Invité]

D'accord, je vais reprendre cela.

Et j'ai commencé à réfléchir à un autre problème : comment déterminer les gares les plus proches du point de départ ? Il faudrait comparer des distances...

Parce que l'on ne part pas de la gare, mais de l'usine.
Si vous avez une idée... J'y ai réfléchi ce matin.

[sos-math(21)]

Bonjour,
Je pense qu’il il faut que tu reprennes la listes des gares avec leur coordonnées gps et que tu crées une fonction qui prenne les coordonnées du point de départ et qui renvoie la gare la plus proche.
Cela se fait avec groom (voir une fonction distance déjà évoquée dans un de mes tout premiers scripts).
Bonne continuation