Bonjour,

J'ai un travail d'informatique qui consiste à modéliser le réseau du métro parisien par un graphe.

Donc là l'objectif c'est de savoir, pour chaque station, à quelles autres stations elle est reliée.

J'ai commencé à étudier un exemple, dans le cas d'un modèle réduit : deux lignes : L1=["A","B","C"] et L2=["B","D","E"]. A, B, C, D et E étant des stations de métro. Soit la liste L=[["A","B","C"],["B","D","E"]]. L[0] est donc la liste des stations de la ligne 1...

J'ai pour chaque ligne un fichier CSV du type (voir photo).

Je souhaite obtenir pour chaque gare, un dictionnaire avec en entrée le nom de la station de métro (A, B, C....), et en valeur associée la liste des stations sur la même ligne ainsi que les distances les séparant de la station de départ (terminus).

Comment faire ceci ?

J'ai commencé à écrire ça, mais je me perds... :

dic={}
for i in range (len(L)):
    for j in range (len(L[i])):
        station=L[i][j]

Comment continuer ?

Merci beaucoup pour l'aide par avance.

alors déjà on évite les range(len) et on fait directement "for ligne in L" et "for station in ligne"

Merci !

Voilà où j'en suis désormais :

OK, alors voilà là où j'en suis.

Je suis passé par votre exemple avec la route pour mieux comprendre le problème, et ça a bien marché.

J'ai construit un dictionnaire qui, pour un numéro de ligne de métro donné (clé), donne la liste des station de cette ligne de métro (valeur).

Par exemple : dic[1]=['La Défense Grande Arche','Esplanade de La Défense','Pont de Neuilly','Les Sablons','Jardin d'Acclimatation','Porte Maillot','Palais des Congrès','Argentine','Charles de Gaulle - Étoile','George V','Franklin D. Roosevelt','Champs-Élysées - Clemenceau','Grand Palais','Concorde','Tuileries','Palais-Royal - Musée du Louvre','Louvre - Rivoli','Châtelet','Hôtel de Ville','Saint-Paul','Le Marais','Bastille','Gare de Lyon','Reuilly - Diderot','Nation','Porte de Vincennes','Saint-Mandé','Bérault','Château de Vincennes'].

Je trouve que c'est pas mal.

Maintenant, j'ai besoin de créer le graphe de station de métro, via une liste d'adjacence, comme ce qui est fait sur l'image.



Est-ce possible dans mon cas ?

Mais il faudrait que chaque gare ait un numéro et non un nom ?

Merci encore de m'aider...

Les contours de ton projets sont très flous et l'ensemble reste assez incohérent. Tu veux modéliser le réseau du métro pour faire quoi ? c'est une question essentielle.

ArefaeAptaaer a écrit:

Par exemple : dic[1]=['La Défense Grande Arche','Esplanade de La Défense','Pont de Neuilly','Les Sablons','Jardin d'Acclimatation','Porte Maillot','Palais des Congrès','Argentine','Charles de Gaulle - Étoile','George V','Franklin D. Roosevelt','Champs-Élysées - Clemenceau','Grand Palais','Concorde','Tuileries','Palais-Royal - Musée du Louvre','Louvre - Rivoli','Châtelet','Hôtel de Ville','Saint-Paul','Le Marais','Bastille','Gare de Lyon','Reuilly - Diderot','Nation','Porte de Vincennes','Saint-Mandé','Bérault','Château de Vincennes'].

Je trouve que c'est pas mal.

Si les clés de ton dictionnaire sont des entiers consécutifs, je vois pas l'intérêt d'utiliser un dictionnaire, autant utiliser une liste de listes.

ArefaeAptaaer a écrit:

Maintenant, j'ai besoin de créer le graphe de station de métro, via une liste d'adjacence, comme ce qui est fait sur l'image.


Est-ce possible dans mon cas ?

Mais il faudrait que chaque gare ait un numéro et non un nom ?
 

Difficile de répondre dans la mesure où tu n'as pas dit quel était le but de la modélisation de ton réseau de transport. Concernant la représentation par listes d'adjacence, en effet, si tu veux représenter le réseau de métro avec des nombres comme tu suggérais, il va te falloir convertir le nom de toutes tes stations en des numéros consécutifs avec un dictionnaire et il te faudra aussi le dictionnaire inverse pour traduire en nom de stations ce que tu vas calculer en termes de numéros. Fais attention que dans ton dessin, tu as un graphe pondéré (ce n'est pas a priori le cas du réseau de métro, en tous cas tu n'as rien précisé à ce sujet) et que ton graphe est orienté ce qui n'est pas le cas du réseau de métro, le métro circule dans les deux sens même s'il y a quelques très rares paires stations où ce n'et pas le cas.

Une autre possibilité, peut-être plus simple, est d'utiliser un dictionnaire de stations (les clés) vers des listes (les stations voisines).

Attention qu'avec ces structures de données tu perds l'information sur les lignes. Donc imaginons que ton programme doive indiquer à un voyageur  le plus court chemin entre deux stations, il va falloir indiquer les correspondances au voyageur. Bien sûr, tu peux toujours aller consulter le dictionnaire que tu avais défini toi-même plus haut mais il n'est pas du tout adapté à cette recherche. 

Bonjour,

Merci pour votre réponse.

Je viens de réussir à construire le dictionnaire dico, tel que dico[1] donne par exemple : [['La Défense Grande Arche',5,4],['Esplanade de La Défense',0],['Pont de Neuilly',2],['Les Sablons',2],['Jardin d'Acclimatation',1],['Porte Maillot',8],['Palais des Congrès';2,5],['Argentine',7,1],['Charles de Gaulle - Étoile',8,9],['George V',7],['Franklin D. Roosevelt',2]].

Les nombres à côté des stations correspondent au point kilométrique des stations sur la ligne de métro, point kilométrique par rapport à une station terminus.

Le but de la modélisation du réseau de transport est de pouvoir l'utiliser pour appliquer l'algorithme de Dijkstra.

Je pense que créer une liste d'adjacence est intéressant. Mais comment créer la liste d'adjacence à partir du dictionnaire "dico" que j'ai créé ? Il faudrait déjà ranger par ordre de PK croissant les stations dans dico[1], dico[2]...

Suis-je sur la bonne voie ?

Merci encore pour l'aide.

ArefaeAptaaer a écrit:

Je pense que créer une liste d'adjacence est intéressant. Mais comment créer la liste d'adjacence à partir du dictionnaire "dico" que j'ai créé ? Il faudrait déjà ranger par ordre de PK croissant les stations dans dico[1], dico[2]...

Si tu disposes de toutes les lignes (avec ton dico), tu es capable de générer la liste L des listes d'adjacence puisque L[ma_station] doit être la liste de toutes les stations qui sont a exactement une station de ma_station.

Merci pour la réponse.

Ce que je ne comprends pas, c'est comment générer la liste L des listes d'adjacence ?

Pourquoi une liste de listes ?

Merci encore.

Je te donne une méthode, pas optimisée. Déjà, tu crées un dictionnaire où tu as toutes les gares du métro et qui pointent chacune vers une liste vide, imaginons

adj={"bastille":[], "duroc":[], "luxembourg":[] # etc}

Les listes d'adjacence sont pour l'instant vides. Ensuite, tu parcours toutes tes lignes une par une, et pour chaque ligne tu parcours station par station depuis un terminus jusqu'à l'autre et à chaque station tu rajoutes les deux gares voisines. Par exemple, quand tu tombes sur la station duroc de la ligne 10, tu rajoutes avec append dans la liste dico[10]["duroc"] les stations "ségur" et "vanneau".

Merci beaucoup pour votre réponse.

Voici ce que j'ai fait pour créer un dictionnaire avec toutes les gares du métro et des listes vides en valeur. (J'ai pris un exemple pour simplifier.)

import csv

L=['A','B','C','D','E']

dico={}

for element in L:
    dico[element]=[]

Cela donne bien ce que l'on attend.

Par contre, pourriez-vous m'aiguiller pour faire la suite que vous avez décrite ? (pour remplir les listes vides)

Prends des noms appropriés sinon on va pas se comprendre. C'est pas dico (qui était ton dico de lignes) mais adj et il faut que tu écrives dico et que tu le parcours. Et ne l'appelle pas dico mais lignes.

import csv
 
L=['A','B','C','D','E']
 
adj={}
 
for element in L:
    adj[element]=[]