Adjacence et graphe

Version imprimable

15/02/2020, 13h34
etudiante0020

Adjacence et graphe

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.....
15/02/2020, 15h43
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
15/02/2020, 16h43
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:

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.
15/02/2020, 16h56
etudiante0020

1 pièce(s) jointe(s)

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

Pièce jointe 538866
15/02/2020, 17h37
wiztricks

Salut,

Citation:

Envoyé par etudiante0020

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
15/02/2020, 17h53
etudiante0020

Citation:

Envoyé par wiztricks

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 ?
15/02/2020, 18h10
Flodelarab
Bonjour :coucou:

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:

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.
15/02/2020, 18h19
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." ?
15/02/2020, 18h39
Flodelarab
```
A > B > C > D > E
A < B < F < D < E
```
À l'aller, il faut prendre C; au retour, il faut descendre à F.
15/02/2020, 19h14
wiztricks

Citation:

Envoyé par etudiante0020

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
15/02/2020, 20h03
etudiante0020

Citation:

Envoyé par wiztricks

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.
15/02/2020, 20h47
wiztricks

Citation:

Envoyé par etudiante0020

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
15/02/2020, 21h44
etudiante0020

1 pièce(s) jointe(s)

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.

Pièce jointe 538886

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...
15/02/2020, 23h20
wiztricks

Salut,

Citation:

Envoyé par etudiante0020

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.

Citation:

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
16/02/2020, 01h49
etudiante0020

1 pièce(s) jointe(s)

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

Pièce jointe 538895

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.
16/02/2020, 12h25
wiztricks

Citation:

Envoyé par etudiante0020

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
16/02/2020, 14h53
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 ?

Citation:

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.
16/02/2020, 15h32
wiztricks
Salut,

Citation:

Envoyé par etudiante0020

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:

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
16/02/2020, 16h05
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:

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.
16/02/2020, 16h23
wiztricks

Citation:

Envoyé par etudiante0020

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
16/02/2020, 16h46
etudiante0020

Le problème est que, même à la main, je viens de réessayer, et je n'arrive pas à trouver de quelle manière il faut parcourir le graphe...

Comment le parcouriez-vous ?

Je vous suis infiniment reconnaissante.
16/02/2020, 17h46
wiztricks

Citation:

Envoyé par etudiante0020

Le problème est que, même à la main, je viens de réessayer, et je n'arrive pas à trouver de quelle manière il faut parcourir le graphe...

Déjà vous ne parcourrez pas le graphe mais la liste représentant les stations de métro d'une ligne.

Et vous faites un parcours particulier de A, B, C.
A la première itération vous devez travailler sur (A, B), à la deuxième sur (B, C),...

Ce qui peut se reformuler avec un indice par (L[i], L[i+1]) où i varie de 0 à l'indice de l'avant dernier élément de la liste.

- W

Merci.

Je propose :
Code:

1 2 3 4 5 6 7 8 9 L = ['A', 'B', 'C' ] G = {} for i in range (len(L)-1): if L[i] in G: G[L[i]].append(L[i]) else: G[L[i]] = L[i+1]
Est-ce mieux ? En tout cas, ça donne le dictionnaire attendu, non ?

Merci beaucoup.

16/02/2020, 18h42
wiztricks

Salut,

Citation:

Envoyé par etudiante0020

En tout cas, ça donne le dictionnaire attendu, non ?

Vous avez la commande "print" pour afficher le contenu et vérifier que c'est ce que vous attendiez.

- W
16/02/2020, 18h51
etudiante0020

Cela donne :

Code:

{'A': 'B', 'B': 'C'}

Donc c'est le bon dictionnaire attendu ?

Mais par contre, je ne suis pas sûre qu'il soit construit de la bonne manière... Est-ce qu'en généralisant ça va fonctionner ?
16/02/2020, 18h59
wiztricks

Citation:

Envoyé par etudiante0020

Cela donne :

Code:

{'A': 'B', 'B': 'C'}

Donc c'est le bon dictionnaire attendu ?

Vous voyez bien que les valeurs associées à vos clefs ne sont pas des listes. Donc déjà c'est pas bon.
De plus, le dictionnaire attendu devrait être G: { 'A': ['B'], 'B': ['A', 'C'], 'C': [] }.

Plutôt que de vous disperser à discutailler dans les forums, pourquoi ne pas vous mettre à bosser un peu sérieusement?

- W
16/02/2020, 19h13
etudiante0020

Alors là, je ne comprends pas...

Citation:

De plus, le dictionnaire attendu devrait être G: { 'A': ['B'], 'B': ['A', 'C'], 'C': [] }.

Pourquoi une liste vide pour C ?! Il est pourtant relié à B ! C'est un graphe non orienté que l'on souhaite...
16/02/2020, 19h47
wiztricks

Citation:

Envoyé par etudiante0020

Alors là, je ne comprends pas...

Pourquoi une liste vide pour C ?! Il est pourtant relié à B ! C'est un graphe non orienté que l'on souhaite...

Ben relisez ce que vous avez écrit dans cette réponse: c'est vous qui dites ce que vous voulez obtenir (j'ai juste enlevé les "poids" histoire de simplifier).

Si vous êtes même incapable d'un peu de cohérence avec ce que vous avez écrit vous même, n'apprenez pas à programmer: vous perdez votre temps!
Il faut des compétences exceptionnelles pour être compétitif via à vis des russes, indiens et autres chinois.
Recyclez vous dans le commerce ou la dentelle.

- W
16/02/2020, 20h38
etudiante0020

Dans mon message avec les poids, j'ai construit la liste d'adjacence d'un graphe NON orienté, n'est-ce-pas ?

Je confirme que c'est bien ce que je souhaite obtenir...

Merci de m'aider en tout cas.

NB : C'est un travail demandé par mon école, je ne souhaite pas devenir programmeur...
16/02/2020, 21h03
wiztricks

Citation:

Envoyé par etudiante0020

Dans mon message avec les poids, j'ai construit la liste d'adjacence d'un graphe NON orienté, n'est-ce-pas ?

C'est à vous de savoir ce que vous voulez: vous enlevez les poids et vous refaites le boulot pour une seule ligne A, B, C. Comme çà vous savez à quoi doit ressembler votre graphe G peu importe le nom technique que vous lui donnez.
Normalement, çà ne devrait pas être très éloigné de ce que je vous ai indiqué.

Maintenant, si vous partez à coder et que vous êtes incapable de vérifier que ce que çà sort est cohérent avec vos attentes... ben c'est même pas la peine d'essayer de faire l'exercice car pour l'instant vous n'en êtes qu'aux prémisses, la partie la plus facile! Prenez du bon temps, assumez de rendre une copie blanche et attendez le corrigé du prof.

- W
17/02/2020, 01h34
etudiante0020
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.)
Code:

1 2 3 4 5 6 7 8 import csv L=['A','B','C','D','E'] dico={} for element in L: dico[element]=[]
Voici un pseudo-code pour remplir les listes :

On parcourt les lignes successivement : on parcourt chacune des lignes station par station depuis un terminus jusqu'à l'autre et à chaque station on rajoute les deux gares voisines.

Est-ce mieux ? Mais comment implémenter ça ?

Je crois que je n'ai pas compris pourquoi on voudrait ce dictionnaire : G: { 'A': ['B'], 'B': ['A', 'C'], 'C': [] }. Car je souhaite encore un graphe orienté. Alors est-ce que ce que j'ai décrit ci-dessus convient ?

Merci encore.
17/02/2020, 10h10
wiztricks

Citation:

Envoyé par etudiante0020

Je crois que je n'ai pas compris pourquoi on voudrait ce dictionnaire : G: { 'A': ['B'], 'B': ['A', 'C'], 'C': [] }.

Effectivement, je me suis trompé on devrait bien avoir G: { 'A': ['B'], 'B': ['A', 'C'], 'C': [ 'B' ] }.
Et sachant que vous voulez obtenir çà, si vous obtenez {'A': 'B', 'B': 'C'}, pas la peine de demander si c'est bon.

Citation:

Envoyé par etudiante0020

Voici un pseudo-code pour remplir les listes :

On parcourt les lignes successivement : on parcourt chacune des lignes station par station depuis un terminus jusqu'à l'autre et à chaque station on rajoute les deux gares voisines.

Est-ce mieux ? Mais comment implémenter ça ?

Si c'était du pseudo-code, vous n'auriez aucune difficulté à l'implémenté (c'est ce à quoi sert le pseudo-code). Et tant que vous n'arrivez pas ajouter une ligne au graphe, vous ne saurez pas ajouter les lignes suivantes.

- W
18/02/2020, 01h58
etudiante0020
Merci pour la réponse.

J'ai donc écrit ça :
Code:

1 2 3 4 5 6 7 8 9 10 11 import csv L=['A','B','C','D','E'] dico={} for i in range(len(L)): if L[i] in dico: dico[L[i]].append([L[i+1]]) else: dico[L[i]] = [L[i]]
Mais cela ne donne pas le résultat attendu ! Là je ne vois pas ce qui cloche... Quoi modifier selon vous ?

Merci encore.
18/02/2020, 08h47
wiztricks
Salut,

Citation:

Envoyé par etudiante0020

Mais cela ne donne pas le résultat attendu ! Là je ne vois pas ce qui cloche...

Ce qui cloche c'est le boulot que vous avez fait sur votre feuille de papier pour décrire l'algorithme qui permet de construire D = { a: [ b ], b: [ a ] } à partir de la liste L = [ a, b ]
ou D = { a: [b], b: [a, c], c: [ b ] } à partir de L = [ a, b, c ].

C'est pas compliqué de partir de L = [ a, b ], D = {} et de se dire, bon allez, pour i = 0 je me retrouve avec L[0] (= a) et L[1] (= b) qu'est ce que je peux faire pour remplir correctement D?
Qu'est ce qu'on a à la fin de cette itération? Est ce qu'on peut enclencher l'itération suivante?

Si vous aviez fait ce boulot là avant de coder ce que vous avez posté, vous auriez vu que pour i = 0, L[0] = a n'est pas dans D (qui est vide) donc on passe dans le "else" qui fait D[a] = [ a ]. Et si à la fin de la première itération on se retrouve avec D = { a : [ a ] }, çà sent pas bon. De plus, la condition L[i] in D étant toujours fausse, votre code ne fait pas plus que:
Code:

1 2 for e in L: D[e] = e
- W

Bonsoir,

Mais en fait je me suis trompée dès le début : on devrait plutôt avoir deux listes L1=['A','B','C] et L2=['D','B','E'] pour modéliser le graphe, non ?

(si l'on met déjà de côté les poids)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 import csv L1=['A','B','C'] L2=['D','B','E'] dico={} for i in range (len(L1)): for k in range (len(L2)): if L1[i] in dico: dico[L1[i]].append([L1[i-1],L1[i+1]]) else: dico[L1[i]] = [L1[i-1]]
Ce code ne fonctionne pas, et je ne sais pas comment prendre en compte L2...

19/02/2020, 08h24
wiztricks
Citation:

Envoyé par etudiante0020

Ce code ne fonctionne pas

Simplifier le problème à une ligne à deux stations, c'est juste pour pouvoir décrire l'ensemble des opérations à réaliser sur une feuille de papier.

Puis on vérifie qu'avec une ligne à 3 stations, la recette de cuisine (ou l'algorithme fonctionne encore (sinon on corrige).

Puis on vérifie qu'on pourra ajouter une deuxième ligne à la liste d'adjacence obtenue.

Si vous aviez fait ce travail de réflexion papier/crayon, vous n'auriez pas écrit ce code (puisqu'il ne fonctionne pas). Et si vous ne voulez pas réfléchir à ce que vous devez coder avant de le coder, çà ne fonctionne pas.

C'est comme pour faire un gâteau: vous avez de l'eau, des œufs, de la farine, ... si vous n'avez une recette/programme pour agencer les ingrédients, un passage au four,... pas la peine de proposer à vos copains de gouter un truc informe, probablement dégueulasse, voire toxique.

Citation:

Envoyé par etudiante0020

et je ne sais pas comment prendre en compte L2...

En pseudo code çà s'écrit:
Code:

1 2 pour chaque ligne dans metro: ajouter ligne à liste d'adjacence.
Et vous en êtes toujours à piétiner dans la réalisation de "ajouter ligne à liste d'adjacence" pour un métro réduit à une seule ligne avec deux stations.

- W

Fuseau horaire GMT +2. Il est actuellement 05h12.