Discussion :

[mandok]

Bonjour,

J'essaye de coder en python l'algorithme de Prim qui permet d'obtenir l'arbre couvrant minimal dans un graphe connexe.

Malheureusement, j'obtiens une erreur que je n'arrive pas à résoudre :

[(1, 0)]
Traceback (most recent call last):
File "/Users/Moi/CX/Python/Graphe/primtest.py", line 46, in <module>
Prim(Graphe1)
File "/Users/Moi/CX/Python/Graphe/primtest.py", line 18, in Prim
if ((min and distanceMin[j] and 0 <= distanceMin[j] < min) or (not min and 0 <= distanceMin[j])):
TypeError: unorderable types: int() <= NoneType()
[Finished in 0.1s with exit code 1]

Voici mon code :

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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def Prim (Graphe):
  T = []
  n = len(Graphe)
  plusProche = []
  distanceMin = []
 
  for i in range(0,n):
    plusProche.append(0)
    distanceMin.append(0)
 
  for i in range(1,n):
    plusProche[i] = 0
    distanceMin[i] = Graphe[i][0]
 
  for i in range(0,n-1):
    min = None
    for j in range(1,n):
      if ((min and distanceMin[j] and 0 <= distanceMin[j] < min) or (not min and  0 <= distanceMin[j])):
        min = distanceMin[j]
        k = j
 
    T.append((k, plusProche[k]))
    print(T)
 
    distanceMin[k] = -1
    distanceMin[plusProche[k]] = -1
 
    for j in range(1,n):
      if ((distanceMin[j] and Graphe[k][j] and Graphe[k][j] < distanceMin[j]) or not distanceMin[j] ):
        distanceMin[j] = Graphe[k][j]
        distanceMin[k] = Graphe[j][k]
 
        plusProche[j] = k
        plusProche[k] = j
 
  return T
 
Graphe1 = [[None, 1, None, 4, None, None, None],
[1, None, 2, 6, 4, None, None],
[None, 2, None, None, 5, 6, None],
[4, 6, None, None, 3, None, 4],
[None, 4, 5, 3, None, 8, 7],
[None, None, 6, None, 8, None, 3],
[None, None, None, 4, 7, 3, None]]
 
Prim(Graphe1)

Pouvez-vous m'aider ?

Merci d'avance.

PS : je suis sous python 3.3.2

[fred1599]

Code :

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

1
2
3
4
>>> None < 5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: NoneType() < int()

Bonne déduction...

[mandok]

Code :

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

1
2
3
4
>>> None < 5
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unorderable types: NoneType() < int()

Bonne déduction...

Merci, même si je n'ai pas bien compris votre réponse.

J'ai réussi à résoudre mon problème en utilisant python 2.7 pourtant je ne vois pas ce qui dans la syntaxe créait cette erreur.

Le code est parfaitement fonctionnelle maintenant.

[dividee]

Le problème n'est pas lié à la syntaxe. Ce que fred1599 a essayé de te faire comprendre, c'est que le problème vient de la comparaison de None avec un entier. Quel sens cela a-t-il ? Est-ce que None < 5 ou None > 5 ?

Il se trouve qu'en Python 2.x, c'est autorisé, et None est plus petit que n'importe quelle autre valeur. C'est un choix arbitraire. Par chance, c'est ce qu'il te fallait pour que ton implémentation donne la bonne réponse. En Python 3.x, les concepteurs ont estimé que ce n'était pas une bonne idée de comparer des pommes et des torchons, et cela lève donc une exception.

La bonne solution, c'est d'éviter de dépendre de cette caractéristique "douteuse" du langage:

Code :

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

if ((min and distanceMin[j] and 0 <= distanceMin[j] < min) or (not min and distanceMin[j] is not None and 0 <= distanceMin[j])):

En gras, c'est ce qui a changé: un test de distanceMin[j] qui court-circuitera la comparaison avec 0 si distanceMin[j] est None. Tu l'avais déjà fait dans la première partie du test (à gauche du or), mais pas dans la seconde. Mais ici on est obligé de préciser (is not None), car sinon il rejettera aussi la valeur 0, alors que dans ton code la valeur 0 valide la condition (je n'ai pas vérifié si ça avait une réelle influence sur l'algorithme; je me suis contenté d'écrire une code sémantiquement équivalent à celui que tu as écris mais qui passe en Python 3.x).

[fred1599]

Quel sens cela a-t-il ?

Tout à fait, c'est à cela que je voulais en venir...

L'upgrade d'une version permet d'améliorer les bugs, etc... On va pas reprendre une version antérieure juste parce-qu'on t'as permis d'avoir une réflexion logique sur le problème posé. On garde la même version et on réfléchi.

Merci, même si je n'ai pas bien compris votre réponse.

Le problème c'est que pour comprendre on cherche...

Qu'est-ce que None ? Traduit ça veut dire aucun
Peut-on comparer 5 à rien ? Non

En python 2.x, ils étaient parti d'une logique (incorrecte à mon goût) incorrecte dans le sens, où None ne valant rien, quelque-soit l'entier, l'objet, ... objet x toujours supérieur à None.

En python 3.x, il corrige cette pensée (pensée correspondant à celle de dividee) pour éviter des incohérences en ce qui concerne les comparaisons.
Comparer une liste d'objets hétérogènes n'a plus de sens dans cette version, et c'est bien!

Est-ce que tu compares une chaîne de caractères à un entier? Non, pourquoi? Simplement parce-que ça te semble pas du tout cohérent...ça ne te viendrait même pas à l'esprit.

Eh bien ici c'est la même chose...

Bref ma petite ligne de code aurait dû te mettre la puce à l'oreille, mais apparemment ça n'a pas été le cas !

Mais à quoi sert None? On l'a dit, None veut dire rien ou aucun, on peut simuler l'absence de paramètre dans une fonction par exemple.

Code :

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

1
2
3
4
def func(param=None):
    if param is None: # Si aucun paramètre ("if not param : " fonctionne aussi)
        param = 0 # param vaut 0
    return param # retourne la valeur du paramètre

Bonne journée

[mandok]

Merci beaucoup, je débarque sur la planète python c'est pour ça que je suis encore un peu lent à la détente :p .

Cependant, j'avais compris l'exception soulever et je comprenais pourquoi ça poser un problème de logique. Mais étant donnée que je m'inspiré d'un code tournant sur du python 2, cela m'avait troublé.

En tant que débutant, je me focalise sur la version 3 mais la Super Bibliothèque Anaconda est encore en 2.7 donc je dois jongler tout le temps.