Discussion :

[etudiante0020]

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.

Pour être plus concret, voici donc ce que j'ai. J'ai une liste nommée "métros" contenant 16 listes. Chacune des 16 listes contenue dans "métros" est une liste contenant la succession des stations de métro d'une ligne.

Voici un extrait de la liste "métros" :

métros=[[’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’],[’Charles de Gaulle – Étoile’,’Ternes’,’Courcelles’,’Monceau’,’Villiers’,’Rome’,’Place de Clichy’,’Blanche’,’Pigalle’,’Anvers’,’Sacré-Cœur’,’Barbès - Rochechouart’,’Chapelle’,’Stalingrad’,’Jaurès’,’Colonel Fabien’,’Belleville’,’Couronnes’,’Ménilmontant’,’Père Lachaise’,’Philippe Auguste’,’Alexandre Dumas’,’Avron’,’Nation’],...]

métros[0] est donc la liste des stations de métro de la ligne 1 du métro de Paris. Et là, on voit déjà quelque chose de pas cool : métros[0] alors que c'est la ligne 1...

métros[13] est donc la liste des stations de métro de la ligne 14.

Il faut aussi savoir que j'ai un fichier Excel avec la distance de chaque station par rapport à un des terminus de la ligne. J'ai ça pour toutes les lignes.

Maintenant je veux donc créer le graphe des lignes de métro de Paris : comment faire ?

Je pense faire un dictionnaire... Avec en clé le nom d'une station, mais que mettre en valeur ? Et comment faire ça en Python surtout ? Automatiser la création d'un dictionnaire pour chaque station ?

Merci beaucoup par avance pour votre aide, cela fait longtemps que je suis sur ce travail, et je commence à être désemparée.....

[wiztricks]

Salut,

Vous devriez commencer par simplifier i.e. prendre 2 lignes de métro fictives où la première ligne à 3 stations A, B, C et croise la deuxième ligne D, B, E en B.
Vous voyez bien qu'aller de A en C sans changer de ligne sera à traiter différemment qu'aller de A en E en changeant de ligne en B.
Car même si on dit que les métros roulent à vitesse constante, changer de ligne n'est aussi indolore (côté durée) que tourner à la première à gauche lorsqu'on se déplace à pied ou en voiture.

Tout çà pour dire que votre représentation de donnée doit être adaptée aux contraintes que vous voulez prendre en compte et aux opérations que vous allez vouloir réaliser. Et que si vous voulez visualiser un peu ce dont vous avez besoin, vous avez intérêt à réfléchir à tout çà sur un modèle réduit avant de généraliser.

Et là vous êtes dans la conception et encore loin de vous poser la question de traduire çà en structures de données (dictionnaires, listes,...).
De toutes façons, pour résoudre ce genre de problème, on apprendra à utiliser networkx, mais sans avoir fait le boulot de conception préalable vous ne saurez pas plus comment construire votre graphe...

- W

[etudiante0020]

Merci beaucoup !


Deux lignes : L1=["A","B","C"] et L2=["B","D","E"]. Soit L=[["A","B","C"],["B","D","E"]].
L[0] est donc la liste des stations de la ligne 1...

A partir de cette liste L, je dois donc construire les dictionnaires pour chaque gare.

Donc, construisons ces dictionnaires pour chaque gare A, B, C, D et E à partir de la liste L.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Avec ça, on a donc, la liste des stations, non ? Comment continuer pour avoir les dictionnaires attendus ? C'est-à-dire dictionnaire avec en entrée une station de métro, et chaque valeur associée est la liste des stations sur la même ligne ainsi que les distances les séparant de la station de départ (terminus).

Merci beaucoup.

[etudiante0020]

Je précise que voici le genre de données que j'ai pour chaque ligne de métro :

[wiztricks]

Salut,

Avec ça, on a donc, la liste des stations, non ? Comment continuer pour avoir les dictionnaires attendus ? C'est-à-dire dictionnaire avec en entrée une station de métro, et chaque valeur associée est la liste des stations sur la même ligne ainsi que les distances les séparant de la station de départ (terminus).

Parler de "dictionnaires attendus" suppose que vous ayez décrit ces choses là.
Essayez décrire (sur une feuille de papier) ce que vous voulez obtenir à partir de L=[["A","B","C"],["B","D","E"]].

Et vérifiez que cette représentation là vous aide à traduire ce que vous voulez avant d'imaginer quelles seraient les structures de données les plus adaptées et éventuellement coder.

- W

[etudiante0020]

Salut,

Essayez décrire (sur une feuille de papier) ce que vous voulez obtenir à partir de L=[["A","B","C"],["B","D","E"]].

Vous avez raison, je n'y arrive pas...

C'est parce que la structure de données (le dictionnaire) n'est pas adaptée ?

[Flodelarab]

Bonjour

Dans une base de données, j'aurais fait une colonne pour la station de départ et une colonne pour la station adjacente. Soit 2 colonnes.
Exemple :

A B
A C
A D
...

Mais en python, avec dictionnaire, la valeur serait la liste des stations adjacentes atteintes à partir de la station d'indice.
Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
>>> dic={}
>>> dic['A']=['B','C','D']
>>> dic
{'A': ['B', 'C', 'D']}
>>> len(dic['A'])
3
>>>

La dernière commande dit que la station 'A' a 3 voisins.

Il te reste à parcourir les listes des lignes pour déterminer les voisins. Attention ! Les lignes n'ont pas forcément le même retour que l'aller.

[etudiante0020]

Merci beaucoup pour votre réponse que j'étudie.

Toutefois, que signifie ceci "Les lignes n'ont pas forcément le même retour que l'aller." ?

[Flodelarab]

A > B > C > D > E
A < B < F < D < E

À l'aller, il faut prendre C; au retour, il faut descendre à F.

[wiztricks]

Vous avez raison, je n'y arrive pas...

C'est parce que la structure de données (le dictionnaire) n'est pas adaptée ?

Non: c'est parce que vous ne savez pas ce que vous voulez... et tant que vous n'y arriverez pas, pas la peine de coder.

- W

[etudiante0020]

Non: c'est parce que vous ne savez pas ce que vous voulez... et tant que vous n'y arriverez pas, pas la peine de coder.

- W

Vous avez probablement raison malheureusement... Pouvez-vous m'aider à savoir ce que je veux ? Car là je suis perdue dans ce travail...

Merci beaucoup.

[wiztricks]

Vous avez probablement raison malheureusement... Pouvez-vous m'aider à savoir ce que je veux ? Car là je suis perdue dans ce travail...

Simplifiez encore: supprimez les lignes de métro et considérez que vous avez des "routes" qui relient ABC et DBE.
Puis si vous arrivez à y voir plus clair, il sera temps de compliquer avec des lignes de métro.

- W

[etudiante0020]

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...

[wiztricks]

Salut,

Je trouve que c'est pas mal.

Ma foi, vous aviez la liste L des stations de métros maintenant vous avez aussi un dictionnaire D de stations de métro et on passe de l'un à l'autre par L[x] = D[x+1]. Pour moi, c'est la même chose.

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 ?

Absolument... mais comme vous n'avez toujours pas essayé de représenter la liste d'adjacence des 2 lignes du métro simplifié: A, B, C et D, B, E difficile d'envisager de vous lancer à faire plus compliqué.

Le seul progrès que vous avez fait depuis le début est de sortir le terme technique "liste d'adjacence" du vocabulaire de la théorie des graphes. Bravo! Mais maintenant, vous allez pouvoir chercher sur Internet "graphe liste d'adjacence" et y trouver de la littérature qui explique ce que c'est et comment le construire.

- W

[etudiante0020]

Merci beaucoup pour votre réponse.

Prenons donc 2 lignes de métro fictives où la première ligne (L1) a 3 stations A, B, C et croise la deuxième ligne (L2) D, B, E en B. J'ai donc tracé le graphe (voir image), et j'ai mis des poids sur les arêtes pour avoir comme dans le cas de l'image que j'avais postée, sinon je ne sais pas faire autrement...



Créons donc la liste d'adjacence de la même manière que ce qui est fait sur l'image que j'avais envoyée :

D [(B,3)]
A [(B,5)]
B [(D,3),(A,5),(C,4),(E,7)]
C [(B,4)]
E [(B,7)]

Donc la liste d'adjacence est :

graphe=[[(B,3)],[(B,5)],[(D,3),(A,5),(C,4),(E,7)],[(B,4)],[(B,7)]]

Qu'en pensez-vous ?

Merci encore.

[wiztricks]

Qu'en pensez-vous ?

Supprimez le poids sur les arêtes, çà donne:
D [ B ]
A [ B ]
B [ D, A, C, E ]
C [ B ]
E [ B ]
autrement dit une liste de lignes où le premier élément est le nœud et où le second est la liste des nœuds adjacents.
Et çà dit quoi? La première ligne dit que depuis D on peut aller en B. On cherche alors la ligne qui commence par B pour voir qu'à partir de B on peut aller en D, A, C ou E.
Et typiquement vous avez là quelque chose qui se représente bien avec un dictionnaire où les clefs seraient les différents nœuds avec comme valeur la liste des nœuds adjacents: G['D'] retourne [ 'B' ] et si on récupère G['B'] on a bien [ 'D', 'A', 'C',' E' ]


Par contre la forme [[ B ], [ B ], [ B, D, A, C, E ] , [ B ], [ B ]] est une liste et si L[0] retourne ['B'], il va falloir récupérer l'index de 'B' quelque part pour savoir quel L[i] correspond au nœud B.
Donc la liste d'adjacence n'est liste que si les nœuds sont numérotés de 0 à 4, histoire que l'index dans la liste corresponde au numéro de nœud. Et si les nœuds sont des labels/chaînes de caractères, il est préférable de représenter cette liste d'adjacence par un dictionnaire.

Et puisque vous avez 2 lignes de métro A, B, C et D, B, E, il va falloir construire maintenant ce dictionnaire sur votre feuille de papier, i.e. commencer par la première ligne A, B, C et voir quelles sont les étapes pour fabriquer G: { 'A': ['B'], 'B': ['A', 'C'], 'C': [ 'B' ] }.

Intuitivement, vous voyez qu'il serait plus facile de partir de (A, B), (B, A), (B, C), (C, B) une liste de nœuds de départ, nœuds d'arrivée: pour chaque (x, y) de cette liste, soit G[x] existe et on lui ajoute y, soit il n'existe pas et on crée l'entrée x avec pour valeur [ y ].

Cela fait, vous vous rendez compte que (A, B), (B, A), (B, C), (C, B) peut se ramener à (A, B), (B, C) en convenant que pour chaque (x, y) de cette liste, on ajoute aussi un chemin de y vers x chaque fois qu'on y ajoute un chemin de x vers y.

Puis que construire (A, B), (B, C) à partir de A, B, C, c'est parcourir une liste où on regroupe deux éléments successifs.
Sans oublier de traiter "à part" le dernier élément de la liste: c'est un nœud sans successeur.

Et une fois que vous saurez jongler avec tout çà, vous saurez intégrer une ligne de métro à votre liste d'adjacence (qui sera un dictionnaire) et y intégrer la deuxième ligne où autant de lignes que vous voulez...
Et il sera temps d'essayer de coder.

- W

[etudiante0020]

Merci beaucoup pour votre réponse.

J'ai compris la première partie de votre message, jusqu'à " il est préférable de représenter cette liste d'adjacence par un dictionnaire."...

Par contre, que voulez-vous dire ici ?

Et puisque vous avez 2 lignes de métro A, B, C et D, B, E, il va falloir construire maintenant ce dictionnaire sur votre feuille de papier, i.e. commencer par la première ligne A, B, C et voir quelles sont les étapes pour fabriquer G: { 'A': ['B'], 'B': ['A', 'C'], 'C': [] }.

Intuitivement, vous voyez qu'il serait plus facile de partir de (A, B), (B, A), (B, C), (C, B) une liste de nœuds de départ, nœuds d'arrivée: pour chaque (x, y) de cette liste, soit G[x] existe et on lui ajoute y, soit il n'existe pas et on crée l'entrée x avec pour valeur [ y ].

Cela fait, vous vous rendez compte que (A, B), (B, A), (B, C), (C, B) peut se ramener à (A, B), (B, C) en convenant que pour chaque (x, y) de cette liste, on ajoute aussi un chemin de y vers x chaque fois qu'on y ajoute un chemin de x vers y.

Ca je ne comprends vraiment pas, j'en suis désolée... Je débute vraiment. Pourriez-vous m'expliquer svp ?

Merci encore.

[wiztricks]

Salut,

Je débute vraiment. Pourriez-vous m'expliquer svp ?

Pour comprendre ce que je raconte, il vous suffit de prendre une feuille de papier, y écrire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
L = [ A, B, C ] 
G = {}

Et imaginez comment vous allez parcourir la liste L pour fabriquer la liste d'adjacence.
Vous allez d'abord considérer (A, B) pour ajouter la clef A avec la liste [ B ]
Puis le suivant (B, C), pour y ajouter la clef B avec la liste [ C ]
Arrivé là, vous constatez que le dictionnaire sera G = { A: [ B ], B : [ C ] } et non { A: [ B ], B: [ A, C], C: [] } essayez de comprendre ce qu'il manque et voir comment l'ajouter.

Vous faites des gribouillages de représentations sur une feuille de papier depuis au moins la maternelle. A l'époque vous saviez déjà gribouiller une maison, le soleil, la lune, des arbres, un bouquet de fleur,... çà fait longtemps que vous avez débuté.

- W

[etudiante0020]

Merci pour la réponse, je commence à mieux comprendre.

J'ai écrit à la main, puis en Python, et voici ce que je propose en Python :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
L = ['A', 'B', 'C' ]
G = {}
 
for element in L:
    if element in G:
        G[element].append(element)
    else:
        G[element] = [element]

Pour moi on parcourirait donc la liste de cette manière, mais cela ne donne pas le bon G... Comment modifier le code ?

Merci encore W.

[wiztricks]

Pour moi on parcourirait donc la liste de cette manière, mais cela ne donne pas le bon G... Comment modifier le code ?

Pas besoin de coder pour se rendre compte que çà ne donne pas le bon résultat: vous le saviez déjà lorsque vous avez gribouillé çà sur votre feuille de papier... Et je vous ai déjà répondu: réfléchissez à ce qu'il manque et à comment l'ajouter.

- W