Graphique

Retrouver tous les sujets résolus.
Invité

Re: Graphique

Message par Invité » mar. 18 févr. 2020 21:40

Merci pour votre réponse.

Avec ce code :

Code : Tout sélectionner

import csv

def conversion(chaine):
    if "+" in chaine :
        return float(chaine.split("+")[0]+"."+chaine.split("+")[1])
    elif "-" in chaine:
        return float(chaine.split("-")[0]+"."+chaine.split("-")[1])

with open('liste-des-gares.csv',newline='',encoding='utf-8') as h :
    extraction  = csv.reader(h,delimiter = ";")
    liste_brute = [ligne for ligne in extraction]
    liste_brute = liste_brute[1:]
    liste_gares = [[int(ligne[4]),ligne[1],conversion(ligne[6]),float(ligne[13]),float(ligne[14])] for ligne in liste_brute if ligne[2]=='O' and ligne[15] != '']

myDict = {}

for element in liste_gares:
    if element[0] in myDict:
        myDict[element[0]].append([element[1],element[2]])
    else:
        myDict[element[0]] = [[element[1], element[2]]]

def dico_lignes() :
    dico={}
    for gare in liste_gares :
        dico_noeud = {}
        for element in liste_gares :
            if element[0] != gare[0] and element[2] == gare[2]:
                dico_noeud[element[1]] = ((gare[3]-element[3]),element[2])
        if gare[1] in dico.keys():
            dico[gare[1]].update(dico_noeud)
        else :
            dico[gare[1]] = dico_noeud
    return dico
pour dico_lignes()['Poitiers'] j'obtiens : {}. Et donc un dictionnaire vide...

Voyez-vous une erreur dans le code ? Je n'ai modifié que très légèrement dico_lignes...

Sachant qu'il faut vraiment calculer la distance avec les PK, donc avec votre fonction "conversion"...

MERCI !
sos-math(21)
Messages : 10334
Enregistré le : lun. 30 août 2010 11:15

Re: Graphique

Message par sos-math(21) » mer. 19 févr. 2020 14:12

Bonjour,
je pense qu'il y avait une erreur dans ton fichier extrait (peut-être une colonne en moins).
Je te propose donc le code suivant qui fonctionne :

Code : Tout sélectionner

import csv

def conversion(chaine):
    if "+" in chaine :
        return float(chaine.split("+")[0]+"."+chaine.split("+")[1])
    elif "-" in chaine:
        return float(chaine.split("-")[0]+"."+chaine.split("-")[1])

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 = liste_gares = [[int(ligne[0]),ligne[1],int(ligne[4]),conversion(ligne[6]),float(ligne[13]),float(ligne[14])] for ligne in liste_brute if ligne[2]=='O' and ligne[15] != '']
    liste_gares_bis = [[int(ligne[4]),ligne[1],conversion(ligne[6]),float(ligne[13]),float(ligne[14])] for ligne in liste_brute if ligne[2]=='O' and ligne[15] != '']

myDict = {}

for element in liste_gares:
    if element[0] in myDict:
        myDict[element[0]].append([element[1],element[2]])
    else:
        myDict[element[0]] = [[element[1], element[2]]]

def dico_lignes() :
    dico={}
    for gare in liste_gares :
        dico_noeud = {}
        for element in liste_gares :
            if element[0] != gare[0] and element[2] == gare[2]:
                dico_noeud[element[1]] = (abs(gare[3]-element[3]),element[2])
        if gare[1] in dico.keys():
            dico[gare[1]].update(dico_noeud)
        else :
            dico[gare[1]] = dico_noeud
    return dico
J'ai comparé les distances avec celles que nous avions avec ma fonction distance (qui calculait une distance à vol d'oiseau en utilisant geopy).
Elles sont supérieures mais assez proches, ce qui paraît vraisemblable.
Bonne continuation
Invité

Re: Graphique

Message par Invité » mer. 19 févr. 2020 14:51

C'est génial, merci beaucoup.

Maintenant il faut donc appliquer l'algorithme de Dijkstra. Pour l'implémentation en Python, ça c'est OK, le prof l'a donnée. Mais pour utiliser son programme, il faut une liste d'adjacence du graphe non orienté du réseau ferré.

Ma question est donc : comment créer cette liste ? Ne pourrait-on pas plutôt utiliser dico_lignes ? Mais dans ce cas là on a plus de liste d'adjacence du réseau ferré, donc je ne peux plus utiliser l'algorithme de Dijkstra du prof... Voyez-vous le problème, et auriez-vous une idée pour le résoudre ? Moi pour l'instant je n'en ai pas malheureusement...

Merci encore, tout cela progresse vraiment ! Je vous suis très reconnaissant.
sos-math(21)
Messages : 10334
Enregistré le : lun. 30 août 2010 11:15

Re: Graphique

Message par sos-math(21) » mer. 19 févr. 2020 22:03

Bonjour,
le problème est que ce que nous avons produit donne une liste de dépendance : une gare et une liste de gares qui appartiennent à la même ligne.
Comment définis-tu la notion d'adjacence ? Sur un graphe on parle d'adjacence pour des sommets voisins, c'est-à-dire reliés par une arête et sur lesquels on met un "poids".
L'algorithme de Dijkstra va parcourir de proche en proche et va conserver à chaque nouveau nœud visité le plus court chemin depuis le point de départ.
Ce qui me gêne, c'est que notre dictionnaire ne contient pas la liste des voisins directs d'une gare mais la liste de toutes les gares sur la même ligne que cette gare.
Je ne sais pas si tu vois le problème mais cela risque de ne pas être adapté à l'algorithme de Dijkstra. Peut-être peux-tu demander des précisions à ton professeur sur la forme finale de la liste d'adjacence ainsi que quelques indications pour déterminer les sommets voisins : je pense qu'on pourrait considérer les sommets les plus proches en regardant ceux dont les pk encadrent le pk de la gare considérée.
Je te laisse réfléchir à cette idée.
Invité

Re: Graphique

Message par Invité » jeu. 20 févr. 2020 01:25

Bonsoir,
Comment définis-tu la notion d'adjacence ? Sur un graphe on parle d'adjacence pour des sommets voisins, c'est-à-dire reliés par une arête et sur lesquels on met un "poids".
C'est exactement comme ça que je définis la notion d'adjacence, comme votre phrase ci-dessus.

J'ai fait des copies d'écran de l'algorithme de Dijkstra Python que le prof nous a envoyé : https://www.cjoint.com/data3/JBuagEIXvq0_2-versions.pdf. Mais comme indiqué dans le fichier, il a donné 2 versions, qui m'ont l'air très différentes. Y a-t-il une des 2 versions qui serait adaptée pour le projet ? Je n'ai pas compris sa première version, c'est pour un cas particulier, non ?

Et je comprends très bien le problème... Par adjacence, on entend bien les gares "juste à côté" d'une gare, les gares voisines, c'est-à-dire qu'il n'y aurait pas de gare intermédiaire entre la gare considérée et les gares adjacentes (il y en a donc 2 si la gare est sur une seule ligne, mais 1 si c'est un terminus, plus de 2 si la gare est située sur plusieurs lignes à la fois...). Suis-je clair ?

Maintenant, il faudrait donc stocker dans une structure Python (dictionnaire, liste...), les gares adjacentes à chaque gare, et les distances entre la gare et les gares adjacentes pour avoir les poids des arcs. On ferait ça encore avec un dictionnaire ? Mais utiliser un dictionnaire permettrait-il d'utiliser un des 2 algorithmes de Dijkstra envoyés dans le lien au-dessus ? Car s'il y a bien une chose que le prof a dite, c'est qu'il souhaitait que l'on utilise un de ces 2 scripts, même si on peut les modifier un peu selon lui.

Et oui, utiliser les PK avec un encadrement me semble être une très bonne idée, on est sur la même longueur d'onde, et c'est tant mieux. Sachant qu'il ne faut pas oublier les distances entre les gares pour avoir les poids.

En espérant que vous aurez un peu de temps pour répondre à ces questions, je vous remercie une énième fois pour votre dévouement. Vous êtes d'une pédagogie exemplaire ! :)
sos-math(21)
Messages : 10334
Enregistré le : lun. 30 août 2010 11:15

Re: Graphique

Message par sos-math(21) » ven. 21 févr. 2020 09:58

Bonjour,
dans le code de dico-lignes, nous traitons bien l'appartenance d'une gare à l'une ou l'autre des lignes.
Il faut donc arriver à déterminer seulement la gare amont et la gare aval de la ligne en utilisant le pk :
il faut donc établir la liste des gares de chaque ligne et calculer leur différence de pk, mais cette fois ci en valeur algébrique et séparer les gares selon que leur distance est positive ou négative, il faudrait faire cela dans deux listes.
Ensuite, trier chacune des listes par ordre croissant avec la méthode sort :
dans la liste des négatifs : extraire le tuple (avec la méthode pop) ayant la plus grande différence : elle sera bien la plus proche de 0 donc correspondra à la gare situé juste avant en amont ;
dans la liste des positifs : extraire le tuple (avec la méthode pop) ayant la plus petite différence : elle sera bien la plus proche de 0 donc correspondra à la gare situé juste avant en aval ;
Je ne suis pas du tout sûr de cette démarche mais je pense qu'il faut tenter.
Je te laisse réfléchir au code.
Bonne continuation
Invité

Re: Graphique

Message par Invité » ven. 21 févr. 2020 12:53

Merci beaucoup pour votre réponse.

J'ai bien pris le temps de comprendre et il y a seulement quelque chose qui me pose problème : cette méthode traite-t-elle les gares qui sont sur plusieurs lignes à la fois ? (la gare de Poitiers par exemple)

Comment faire pour établir votre processus quand la gare est située sur plusieurs lignes ?

Merci encore ! :)

Je vais aussi réfléchir au code cet après-midi.
sos-math(21)
Messages : 10334
Enregistré le : lun. 30 août 2010 11:15

Re: Graphique

Message par sos-math(21) » sam. 22 févr. 2020 18:12

Bonjour,
maintenant que je suis en vacances, j'ai repris le problème depuis le début et je te propose les constructions suivantes :
- construction d'une liste extraite du fichier liste_des_gares en ne prenant que :
le code UIC (0), le libellé (1), le code ligne(4), le 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
- construction d'un dictionnaire dico_lignes qui a pour entrées toutes les gares de ce fichier et pour valeurs un dictionnaire des lignes auxquelles cette gare appartient, ainsi que, pour chaque ligne, la liste des gares lui appartenant et la distance algébrique avec la gare considérée au départ

- construction d'un dictionnaire adjacence() qui a pour entrées toutes les gares du fichier liste_des_gares et pour valeurs une liste de tuples des sommets adjacents par ligne obtenu par maximum des distances négatives et minimum des distances positives (la gare juste en amont et celle juste en aval).
Ceci donne le "petit code " suivant que je te laisserai décrypter :

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 matrice_adjacence() :
    """créé un dictionnaire 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 != []:
                liste_amont_triee = sorted(liste_amont, key=lambda t: t[1])
                maximum = max(liste_amont_triee,key=lambda t: t[1])
                if gare not in adjacence.keys() :
                    adjacence[gare] = [(maximum[0],abs(maximum[1]),ligne)]
                else :
                    adjacence[gare].append((maximum[0],abs(maximum[1]),ligne))
            liste_aval = [element for element in dico[gare][ligne] if element[1]>0]
            if liste_aval != []:
                liste_aval_triee = sorted(liste_aval, key=lambda t: t[1])
                minimum = min(liste_aval_triee,key=lambda t: t[1])
                if gare not in adjacence.keys() :
                    adjacence[gare]=[(minimum[0],abs(minimum[1]),ligne)]
                else :
                    adjacence[gare].append((minimum[0],abs(minimum[1]),ligne))

    return adjacence
Un petit appel pour la gare de Châteauroux donne :

Code : Tout sélectionner

>>> matrice_adjacence()['Châteauroux']
[('St-Maur-sur-Indre', 5.951999999999998, 594000), ('Argenton-sur-Creuse', 30.990999999999985, 590000), ('Montierchaume', 8.50200000000001, 590000)]
Lorsqu'on a pas l'autre bout d'une ligne, c'est que la gare appelée est un terminus de la ligne, ce qui est le cas de la 594000 qui va de Joué les tours à Châteauroux
Je te laisse le soin de décrypter ce travail qui doit se rapprocher de ce que ton professeur attend. Pour l'instant c'est un dictionnaire car cela me semble le plus logique : pour chaque gare, on lui attribue la liste des gares adjacentes avec leur distance (j'ai rajouté les numéros de ligne pour vérification mais on peut s'en passer.
Bon travail
Invité

Re: Graphique

Message par Invité » sam. 22 févr. 2020 20:06

C'est vraiment génial, merci beaucoup ! Cela fonctionne aussi chez moi.

Avant de me plonger ce soir dans le code, j'ai une question :
Avez-vous eu le temps de regarder les 2 versions de l'algorithme de Dijkstra données par mon professeur (le lien est dans mon message de jeudi dernier à 01h25) ?

En fait je ne comprends pas ce que prennent en entrée ces 2 versions, je ne saisis pas les arguments des fonctions... Enfin, y a-t il une version plus adaptée que l'autre dans le cas de ce travail ?

Merci encore, je vous suis infiniment reconnaissant une fois de plus. Je progresse et j'apprends énormément grâce à vous.
Invité

Re: Graphique

Message par Invité » dim. 23 févr. 2020 01:58

J'ai une autre question :

Pour la gare de Dunkerque-Port-Ouest, cela indique qu'il ne trouve pas cette clé... Pourquoi ? Tant pis ?
Cette gare doit pourtant bien être reliée à une ligne...
Mais tant pis sinon, c'est déjà très bien ce que l'on a. Car je viens de chercher 2 heures une solution et pour l'instant je n'en ai pas...
A moins que vous en ayiez une ?

Là le souci principal c'est surtout de savoir comment utiliser une des 2 versions de l'algorithme de Dijkstra données par mon prof avec ce que l'on a...

J'ai beaucoup cherché, pour l'instant je ne vois pas de solution car j'ai du mal à savoir ce qu'attendent en argument les fonctions des versions 1 et 2...

Y voyez-vous plus clair de votre côté ?

Encore merci.
sos-math(21)
Messages : 10334
Enregistré le : lun. 30 août 2010 11:15

Re: Graphique

Message par sos-math(21) » dim. 23 févr. 2020 11:17

Bonjour,
pour certaines gares comme Dunkerque Port Ouest, si tu fais la recherche dans le fichier liste des gares et que tu cherches cette gare, tu vois qu'elle appartient à la ligne 302511 et quand tu fais une recherche sur cette ligne, tu trouves que la seule gare qui appartient à cette ligne est justement Dunkerque Port Ouest : en gros elle est toute seule donc c'est normal que cette clé ne soit pas présente puisqu'il faut une liste d'adjacence non vide pour figurer dans le dictionnaire. Le fichier csv a sûrement des coquilles
Pour tes programmes, j'ai aussi un peu de mal à suivre à première vue et je pense que la structure de données est une liste de listes mais je ne vois pas comment le raccorder à notre situation. Peut-être que tu peux questionner ton professeur à ce sujet en lui montrant l'avancée de tes travaux et voir comment se rapprocher de l'une ou l'autre de ces fonctions implémentant dijkstra.
Bonne continuation
Invité

Re: Graphique

Message par Invité » dim. 23 févr. 2020 12:39

Merci beaucoup pour votre réponse.
Je vais envoyer un mail cet après-midi à mon professeur.

Sinon, connaissez-vous, de manière générale, l'algorithme de Dijkstra ?

Parce que j'ai regardé de nombreux cours et vidéos sur Internet, j'ai compris la "mécanique" avec le tableau, mais je ne comprends pas pourquoi cela fonctionne, je ne comprends pas le principe qu'il y a derrière.

Donc je suis loin de pouvoir comprendre un programme Python Dijkstra...

Auriez-vous un cours clair sur Dijkstra, ou pourriez-vous m'expliquer svp ?

Encore merci. Et bonnes vacances surtout. Moi il ne me reste qu'une semaine, et encore, j'ai énormément de travail (bacs blancs...).

PS : N'hésitez pas à répondre dans mon message comme vous l'aviez déjà fait si le forum est fermé quand vous voyez ce message. Cela me ferait gagner du temps... Merci encore ! :)
sos-math(21)
Messages : 10334
Enregistré le : lun. 30 août 2010 11:15

Re: Graphique

Message par sos-math(21) » lun. 24 févr. 2020 20:31

Bonjour,
j'avais fait deux vidéos il y a quelques temps pour une exemple d'utilisation de l'algorithme de Dijkstra :
directement sur le graphe : https://youtu.be/5DfAtUWLDhc
avec un tableau : https://youtu.be/KWzZCugDumk
Dijkstra s'exécute très bien à la main mais son traitement informatique est plus complexe : il faut modéliser un graphe, ce qui est loin d'être évident.
Est-ce que tu peux m'envoyer les fichiers .py pour les tester dans mon environnement python ?
Il suffira de le copier coller dans la balise
code

Code : Tout sélectionner

copier ici
Bonne continuation
Invité

Re: Graphique

Message par Invité » mar. 25 févr. 2020 02:52

Merci beaucoup pour ces vidéos, je les ai regardées et vous êtes, une fois de plus, d'une très grande pédagogie. C'est vraiment très bien expliqué. Maintenant que j'ai compris le principe, il va falloir l'appliquer à ce problème. Et c'est une autre histoire de le programmer en Python.

Voici la version 1 du prof (vous pouvez ainsi copier le code) : https://hastebin.com/vakirexixa.py
Et la version 2 : https://hastebin.com/ewolohayip.cs

Cela ne fonctionnait bizarrement pas quand je le mettais dans la balise code, mais du moment que vous pouvez le copier, c'est bon.

Pensez-vous qu'une des deux versions peut "coller" au projet ?

De mon côté, je suis encore en train d'essayer de les comprendre...

Encore merci pour votre soutien.
Invité

Re: Graphique

Message par Invité » jeu. 27 févr. 2020 00:40

Bonjour,

Avez-vous reçu le message que je vous avais envoyé avec les codes ? Je ne suis pas sûr qu'il soit parti...

Merci beaucoup et bonnes vacances.
Répondre