Discussion :

[AaGayia]

Bonjour

Ça m'énerve de devoir en venir à poser la question ici parce que je suis certaine que ça ne doit pas être bien compliqué; mais j'y ai passé la journée, et je sens que je ne pourrai pas dormir tant que je n'aurai pas résolu mon problème -_-

Alors le voilà, mon problème :

J'ai une liste d'arêtes de la forme [(nom_arête, sommet_1, sommet_2, poids_arête)]. Pour pouvoir appliquer mon Dijkstra, je veux transformer cette liste en dictionnaire de dictionnaires.

Un exemple, soit la liste d'arêtes suivante :

Code :

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

listeArete = [(1,'a','b',30),(2,'b','d',5),(3,'d','e',10),(4,'d','c',5), (5,'a','c',25), (6,'a','e',60), (7,'f','e',15), (8,'b','c',15),(9,'c','e',30)]

Et je veux construire le dictionnaire suivant :

Code :

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

1
2
3
4
5
6
7
graphe = {'a': {'c': 25, 'b': 30, 'e' : 60},
          'b': {'d' : 5, 'c' : 15},
          'c': {'d' : 5, 'e' : 30},
          'd': {'e': 10},
          'f': {'e': 15},
          'e': {},
    }

J'ai essayé beaucoup beaucoup de choses différentes, et du coup je n'y comprends plus grand chose. Par exemple, tout simplement :

Code :

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

1
2
3
4
5
6
for i in range(len(listeArete)):
        sousDico = {}
        sousDico[listeArete[i][2]] = listeArete[i][3]
        print sousDico
        graphe[listeArete[i][1]] = sousDico
        print graphe

Cela me renvoit la chose suivante :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
{'b': 30}
{'a': {'b': 30}}
{'d': 5}
{'a': {'b': 30}, 'b': {'d': 5}}
{'e': 10}
{'a': {'b': 30}, 'b': {'d': 5}, 'd': {'e': 10}}
{'c': 5}
{'a': {'b': 30}, 'b': {'d': 5}, 'd': {'c': 5}}
{'c': 25}
{'a': {'c': 25}, 'b': {'d': 5}, 'd': {'c': 5}}
{'e': 60}
{'a': {'e': 60}, 'b': {'d': 5}, 'd': {'c': 5}}
{'e': 15}
{'a': {'e': 60}, 'b': {'d': 5}, 'd': {'c': 5}, 'f': {'e': 15}}
{'c': 15}
{'a': {'e': 60}, 'b': {'c': 15}, 'd': {'c': 5}, 'f': {'e': 15}}
{'e': 30}
{'a': {'e': 60}, 'c': {'e': 30}, 'b': {'c': 15}, 'd': {'c': 5}, 'f': {'e': 15}}

Tout se passe bien jusqu'à la ligne 8, où, au lieu d'ajouter la nouvelle valeur de "a" à son sous-dictionnaire correspondant, le sous-dictionnaire en question est écrasé.

En fait, il suffirait de concaténer le sousDico courant avec le sous-dictionnaire de la clef courante / d'ajouter une nouvelle clef et une nouvelle valeur au sous-dictionnaire; mais je n'y parviens pas.

Est-ce que quelqu'un voit la grosse bêtise que je fais quelque part ou bien aurait une idée ?

Merci beaucoup

Ah zut, j'me suis gourée d'emplacement -___-

[AaGayia]

Je crois avoir trouvé en fait peut-être; tout simplement :

Code :

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

1
2
3
4
5
6
7
8
9
graphe = {}
 
for i in range(len(listeArete)):
        if listeArete[i][1] not in graphe.keys():
                sousDico = {}
                sousDico[listeArete[i][2]] = listeArete[i][3]
                graphe[listeArete[i][1]] = sousDico
        elif listeArete[i][1] in graphe.keys():
                graphe[listeArete[i][1]][listeArete[i][2]] = listeArete[i][3]

graphe[listeArete[i][1]] pour la clef du dictionnaire principal ; listeArete[i][2] pour la clef du sous-dictionnaire !

[VinsS]

Salut,

Tout d'abord, je pense que tu te trompe avec l'indexation dans la liste.
Ceci:

Code :

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

1
2
sousDico[listeArete[i][2]] = listeArete[i][3]

Signifie que tu prend le troisième object du tuple pour clé alors que dans ton exemple tu montres le deuxième.

(1,'a','b',30) --> {'b': 30}

Tu dois évidement vérifier si la clé existe déjà dans le dictionnaire pour ne pas l'écraser.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
>>> la = [(1,'a','b',30),(2,'b','d',5),(3,'d','e',10),(4,'d','c',5), (5,'a','c',25), (6,'a','e',60), (7,'f','e',15), (8,'b','c',15),(9,'c','e',30)]
>>> aretes = {}
>>> for t in la:
...     if t[1] in aretes:
...             aretes[t[1]][t[2]] = t[3]
...     else:
...             aretes[t[1]] = {t[2]: t[3]}
... 
>>> aretes
{'a': {'c': 25, 'b': 30, 'e': 60}, 'c': {'e': 30}, 'b': {'c': 15, 'd': 5}, 'd': {'c': 5, 'e': 10}, 'f': {'e': 15}}

[AaGayia]

Cela marche nikel, merci beaucoup !