Discussion :

[ImmoTPA]

Bonjour,

Je suis débutant en Python et j'ai un problème dans mon code que voici :

# *-coding:Utf-8 -*

class vertex:

def __init__(self, name, value):
self.name = name
self.buddies = dict()
self.value = value

def __str__(self):
return str(self.name)

class Graph:

def __init__(self, name, vertices):

self.vertices = vertices
self.name = name

def Dijkstra(G, source):

sPaths = [(float('inf'), None)]*len(G.vertices)

sPaths[source.value] = 0

pivot = source

papas = [None]*len(G.vertices)

done = []

while len(done) != (len(G.vertices)-1):
for buddy in pivot.buddies.keys():
if(sPaths[buddy.value] > sPaths[pivot.value] + pivot.buddies[buddy]):
sPaths[buddy.value] = sPaths[pivot.value] + pivot.buddies[buddy]
papas[buddy.value] = pivot
done.append(pivot)
for path in sPaths:
if path[0] == min(sPaths)[0]:
pivot = path[1]

for path in sPaths:
print("distance de "+str(source)+"à "+ str(path[1])+"= "+path[0]+"\n")

A = vertex("A", 0)
B = vertex("B", 1)
C = vertex("C", 2)
D = vertex("D", 3)
E = vertex("E", 4)
S = vertex("S", 5)

E.buddies = {A:3, B:1}
A.buddies = {E:3, B:1, C:3}
B.buddies = {E:1, A:1, C:3, D:5}
C.buddies = {A:3, B:3, D:1, S:3}
D.buddies = {B:5, C:1, S:1}


G = Graph("G", [A, B, C, D, E, S])

Dijkstra(G,E)

Le rapport d'erreur est le suivant :

File "Dijkstra.py", line 61, in <module>
Dijkstra(G,E)
File "Dijkstra.py", line 39, in Dijkstra
if path[0] == min(sPaths)[0]:
TypeError: 'int' object has no attribute '__getitem__'

Je suis désolé par avance si la solution est évidente mais j'ai fait des tests intermédiaires et a priori la méthode min renvoie bien un tuple alors je ne comprends pas pourquoi min(sPaths)[0] renvoie une erreur. Merci à tous ceux qui prendront le temps de réfléchir à mon problème.

Cordialement

[wiztricks]

Je suis désolé par avance si la solution est évidente mais j'ai fait des tests intermédiaires et a priori la méthode min renvoie bien un tuple alors je ne comprends pas pourquoi min(sPaths)[0] renvoie une erreur. Merci à tous ceux qui prendront le temps de réfléchir à mon problème.

Une valeur minimum étant par définition unique, il n'y a pas de bonne raison pour que "min" retourne autre chose qu'une valeur.
Après la fonction "min" de Python pourrait inventer autre chose mais elle ne fera que ce qui est documenté:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
>>> help(min)
Help on built-in function min in module builtins:
 
min(...)
    min(iterable[, key=func]) -> value
    min(a, b, c, ...[, key=func]) -> value
 
    With a single iterable argument, return its smallest item.
    With two or more arguments, return the smallest argument.
 
>>>

- W

[ImmoTPA]

Bonjour wiztricks,

Je te remercie de ta réponse, par ailleurs je ne comprends pas. Voici le résultat du code suivant que j'ai écrit dans un fichier test :

sPaths = [(float('inf'), None)]*len(G.vertices)
sPaths[1] = (12, A)
a = min(sPaths)
print(a)

(12, <__main__.vertex instance at 0x7fa91e37ec20>)

et donc voici ce que j'obtiens quand j'écris cela :

a = min(sPaths)
print(a[1])
print(a[0])

A
12

Donc au final je crois que min renvoie le tuple minimal au sens du premier argument, ici ce sont des distances donc mon plus petit tuple au sens de la distance est bien celui proposé et pourtant pas moyen de faire la comparaison entre le premier argument de ce tuple qui est un int et un autre int. Si tu vois ce qui m'échappe je t'en prie...En te remerciant à nouveau de te pencher sur mon problème.

[VinsS]

Ce n'est probablement pas là

Code :

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

....... == min(sPaths)[0]:

que ça coince mais là:

Code :

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

if path[0] == ...

Et pourquoi donc ?

Parce que tu as réutilisé le nom path dans une boucle plus avant, là:

Code :

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

1
2
 
for path in sPaths:

... et ouais.

[wiztricks]

Prenez un truc bizarre comme:

Code :

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

1
2
3
4
>>> paths = [ (ord(_),_) for _ in 'abcde' ]
>>> paths
[(97, 'a'), (98, 'b'), (99, 'c'), (100, 'd'), (101, 'e')]
>>>

"min" osera vous retourner quelque chose:

Code :

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

1
2
3
>>> min(paths)
(97, 'a')
>>>

Et il est "consistent" avec lui même:

Code :

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

1
2
3
>>> paths.reverse()
>>> min(paths)
(97, 'a')

Pour ce faire, il utilise une sorte de diversion: les objets ayant un id unique, retournons l'objet qui a le plus petit id.

Code :

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

1
2
3
4
5
6
7
8
>>> for e in paths:
...     print (e, id(e))
...
(101, 'e') 42830856
(100, 'd') 45304520
(99, 'c') 45215880
(98, 'b') 45303496
(97, 'a') 45303304

Que dire? garbage in garbage out...

- W

[ImmoTPA]

Merci pour vos réponses. Par contre Vinsz j'aimerai bien que vous m'expliquiez le problème. Si path n'était pas dans la boucle comment pourrais-je m'en servir ?

[wiztricks]

Merci pour vos réponses. Je vais essayer d'override min alors. Par contre Vinsz j'aimerai bien que vous m'expliquiez le problème. Si path n'était pas dans la boucle comment pourrais-je m'en servir ?

Il serait sage de reposter votre code avec la balise "code" pour respecter les indentations, sinon on racontera ce qu'on peut sur le reste mais c'est "au pif".

- W

[Jedai]

Prenez un truc bizarre comme:

Code :

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

1
2
3
4
>>> paths = [ (ord(_),_) for _ in 'abcde' ]
>>> paths
[(97, 'a'), (98, 'b'), (99, 'c'), (100, 'd'), (101, 'e')]
>>>

"min" osera vous retourner quelque chose:

Code :

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

1
2
3
>>> min(paths)
(97, 'a')
>>>

Pour ce faire, il utilise une sorte de diversion: les objets ayant un id unique, retournons l'objet qui a le plus petit id.

Code :

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

1
2
3
4
5
6
7
8
>>> for e in paths:
...     print (e, id(e))
...
(101, 'e') 42830856
(100, 'd') 45304520
(99, 'c') 45215880
(98, 'b') 45303496
(97, 'a') 45303304

Que dire? garbage in garbage out...

- W

Parce qu'évidemment 45_303_304 (id de (97, 'a')) < 42_830_856 (id de (101, 'e')) ?
Ah tiens, non ?
Peut-être finalement que min() est défini en fonction de l'ordre donné par les comparaisons... Et je suis relativement sûr que les comparaisons sont définies sur les tuples avec l'ordre classique sur les tuples : l'ordre lexicographique (celui du dictionnaire). Ça serait un peu gros que Python, qui se veut fortement typé fasse ce genre de comparaisons bidons sur des objets aussi souvent utilisés que les tuples.

[wiztricks]

Peut-être finalement que min() est défini en fonction de l'ordre donné par les comparaisons... Et je suis relativement sûr que les comparaisons sont définies sur les tuples avec l'ordre classique sur les tuples : l'ordre lexicographique (celui du dictionnaire). Ça serait un peu gros que Python, qui se veut fortement typé fasse ce genre de comparaisons bidons sur des objets aussi souvent utilisés que les tuples

Tout à fait, tuple et list sont comparés "lexicographiquement", merci de le rappeler.

Mon propos était de dire qu'il ne suffisait pas de passer à "min" n'importe quoi et d'espérer qu'il s'en débrouille.

La solution sera dans ce cas sera d'écrire:

Code :

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

1
2
3
                for path in sPaths:
                    if path[0] == min(sPaths, key=lambda e: e[0])[0]:
                        pivot = path

i.e. préciser l'indice de la valeur à comparer.

Mais c'est vrai qu'il y a d'autres "incohérences" à corriger avant.

- W