IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

fonctionnement des tuples


Sujet :

Python

  1. #1
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut fonctionnement des tuples
    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

  2. #2
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 240
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 240
    Points : 36 696
    Points
    36 696
    Par défaut
    Citation Envoyé par ImmoTPA Voir le message
    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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  3. #3
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    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.

  4. #4
    Expert éminent

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    4 298
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 4 298
    Points : 6 778
    Points
    6 778
    Par défaut
    Ce n'est probablement pas là
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    ....... == min(sPaths)[0]:
    que ça coince mais là: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.

  5. #5
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 240
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 240
    Points : 36 696
    Points
    36 696
    Par défaut
    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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  6. #6
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    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 ?

  7. #7
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 240
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 240
    Points : 36 696
    Points
    36 696
    Par défaut
    Citation Envoyé par ImmoTPA Voir le message
    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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  8. #8
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par wiztricks Voir le message
    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.

  9. #9
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    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
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    # *-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)
    Désolé c'est vrai que j'aurai du y penser avant je ne connaissais pas l'existence de cette balise. Merci

  10. #10
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Bonjour Jedai,

    Merci pour ta réponse, as tu une idée du problème ?

  11. #11
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par ImmoTPA Voir le message
    Merci pour ta réponse, as tu une idée du problème ?
    Si tu codes dans un langage dynamiquement typé, il faut prêter grande attention au type de tes objets, et quand tu as une structure à deux niveaux, il faut faire attention à ne pas en oublier 1, par exemple :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    sPaths = [(float('inf'), None)]*len(G.vertices)
     
    sPaths[source.value] = 0
    D'un côté sPaths est une liste de Tuples, de l'autre côté tu affecte à l'un de ses éléments (un tuple à l'origine) la valeur 0 (un entier)...
    Tu fais plusieurs erreurs similaires par la suite.

    --
    Jedaï

  12. #12
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    En effet je n'avais pas vu ça merci. J'essaie de corriger mes erreurs.

  13. #13
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    En fait ta principale erreur semble être que tu hésites entre des sommets numérotés et des sommets nommés... Du coup ton sPaths est plus compliqué que nécessaire (tu es censé stocker le sommet de destination dans la seconde composante de tes tuples, mais tu les laisses à None...) et tu n'arrêtes pas d'écrire ton code comme si sPaths était un tableau d'entiers. Je te conseille de choisir un modèle et de t'y tenir : soit tes sommets ont des noms et tes structures de données devraient pratiquement toute être des dictionnaires, soit ils sont numérotés implicitement à la création du graphe et tu n'as pas besoin de stocker leur numéro dans le sommet, juste leur nom et voisins.

  14. #14
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Grâce à ta réponse j'en suis là.
    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
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    # *-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, source)
     
        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][0] > sPaths[pivot.value][0] + pivot.buddies[buddy][0]):
                    sPaths[buddy.value][0] = sPaths[pivot.value][0] + pivot.buddies[buddy][0]
                    papas[buddy.value][1] = 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)
    J'ai le sentiment d'avoir respecter le type de mes objets et pourtant il n'accepte toujours pas les comparaisons de mon premier argument dans mes tuples (qui sont int). J'obtiens ce message d'erreur.

    File "Dijkstra.py", line 61, in <module>
    Dijkstra(G,E)
    File "Dijkstra.py", line 34, in Dijkstra
    if((sPaths[buddy.value])[0] > (sPaths[pivot.value])[0] + (pivot.buddies[buddy])[0]):
    TypeError: 'int' object has no attribute '__getitem__'

    Merci encore de ton aide.

  15. #15
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    (pivot.buddies[buddy]) est déjà un entier (car pivot.buddies est un dictionnaire d'entiers).

  16. #16
    Expert éminent

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    4 298
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 4 298
    Points : 6 778
    Points
    6 778
    Par défaut
    Vu avec l'indentation le code m'apparaît différemment, mais il reste possible que l'erreur soit dans
    du fait du code qui précède.

    Tu te simplifierais la vie en printant des données:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
                    for path in sPaths:
                        print path[0], sPath

  17. #17
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    J'ai fait le print que tu m'as conseillé. Auparavant j'ai pu corriger mes erreurs de syntaxe puisque maintenant mon programme s'execute mais je dois avoir une erreur car la console m'affiche ceci :

    177180
    inf
    inf
    inf
    inf
    inf
    177181
    inf
    inf
    inf

    à l'infini...

    Je dois avoir une erreur de raisonnement dans mes boucles.

  18. #18
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Ah nan je suis juste stupide, comme tu me l'as fait remarqué j'ai laissé mes sommets de mes tuples à None donc je ne risquais pas d'y arriver.

  19. #19
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 240
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 240
    Points : 36 696
    Points
    36 696
    Par défaut
    Citation Envoyé par Jedai Voir le message
    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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  20. #20
    Membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mars 2014
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mars 2014
    Messages : 126
    Points : 48
    Points
    48
    Par défaut
    Merci wiztricks. En effet ton code semble mieux fonctionner que le mien. Néanmoins lorsque je lance mon programme celui ci tourne à l'infini et lorsque je l'arrête au clavier j'ai ceci :

    File "Dijkstra.py", line 60, in <module>
    Dijkstra(G,E)
    File "Dijkstra.py", line 38, in Dijkstra
    if path[0] == min(sPaths, key=lambda e: e[0])[0]:
    KeyboardInterrupt

    Je ne sais pas si cela signifie que le programme plante à cet endroit là ou non.

    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
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    # *-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'), vertex) for vertex in G.vertices] 
        sPaths[source.value] = (0, source)
     
        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][0] > sPaths[pivot.value][0] + pivot.buddies[buddy]):
                    sPaths[buddy.value] = (sPaths[pivot.value][0] + pivot.buddies[buddy], sPaths[buddy.value][1])
                    papas[buddy.value] = pivot
                    done.append(pivot)
                    for path in sPaths:
                        if path[0] == min(sPaths, key=lambda e: e[0])[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)
    Merci à tous de votre intérêt.

Discussions similaires

  1. Fonctionnement des attributions de droits sur table et bdd ?
    Par shako95 dans le forum MS SQL Server
    Réponses: 2
    Dernier message: 28/11/2005, 14h39
  2. Comportement différent des listes [] et des tuples () ??
    Par JujuKéblo dans le forum Général Python
    Réponses: 2
    Dernier message: 12/10/2005, 10h08
  3. Fonctionnement des WeakHashMap
    Par seiryujay dans le forum Collection et Stream
    Réponses: 2
    Dernier message: 03/10/2005, 15h12
  4. Fonctionnement des fichiers.
    Par phoenix440 dans le forum Autres Logiciels
    Réponses: 7
    Dernier message: 29/05/2005, 16h36
  5. [langage] fonctionnement des Processus
    Par GMI3 dans le forum Langage
    Réponses: 3
    Dernier message: 19/09/2003, 12h12

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo