Discussion :

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

[wiztricks]

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

[etudiante0020]

Merci.

Je propose :

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

[wiztricks]

Salut,

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

[etudiante0020]

Cela donne :

Code :

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

{'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 ?

[wiztricks]

Cela donne :

Code :

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

{'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

[etudiante0020]

Alors là, je ne comprends pas...

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

[wiztricks]

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

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

[wiztricks]

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

[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 :

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

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.

[wiztricks]

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.

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

[etudiante0020]

Merci pour la réponse.

J'ai donc écrit ça :

Code :

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

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.

[wiztricks]

Salut,

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 :

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

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

- W

[etudiante0020]

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 :

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

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

[wiztricks]

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.

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

En pseudo code çà s'écrit:

Code :

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

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