Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > fr.comp.lang.python > #3421 > unrolled thread

urgence! lire une matrice en graphe

Back to article view | Back to fr.comp.lang.python

Contents

  urgence! lire une matrice en graphe Student14 <nospam_ines.kasbi@icloud.com.invalid> - 2020-12-19 12:09 -0600
    Re: urgence! lire une matrice en graphe Benoit Izac <use.reply.to@INVALID.ADDRESS> - 2020-12-19 20:20 +0100

#3421 — urgence! lire une matrice en graphe

Bonjour,

Je suis en train de transformer une matrice en graphe. Pour pouvoir utiliser ce
graphe avec un autre algorithme. Mais le problème, c'est que la fonction est
correcte puisqu'elle m'affiche en print les coordonnées du graphe mais ensuite
l'algorithme ne veut pas utiliser les données du graphe. Que dois-je faire ? 

from collections import defaultdict
import numpy as np

mat =np.array([[40,88,98,0],
               [21,8,58,4],
               [22,11,1,6]])
graphe={}
graphe = dict(enumerate(dict(enumerate(row)) for row in mat))
print(graphe)

def Prim(graph):
    MST = defaultdict(set)
    MSTLen = 0
    starting_vertex='0'
    T = [starting_vertex]
    Q = [node for node in graphe if node!=starting_vertex]
    while len(T) < len(graphe):
        edges = [(cost, from_vertex, to_vertex) for from_vertex in T for
to_vertex, cost in graphe[from_vertex].items() if to_vertex in Q]
        min_weight_edge = 100000000 #infinity
        min_pos_edge = -1
        for e in edges:
            if e[0] < min_weight_edge:
                min_weight_edge = e[0]
                min_pos_edge = e
        T.append(min_pos_edge[2])
        Q.remove(min_pos_edge[2])
        MST[min_pos_edge[1]].add(min_pos_edge[2])
        MSTLen += min_pos_edge[0]
    print("Overall MST length: ", MSTLen)
    return  MST
print(Prim(graphe))

PS: la méthode prim est correcte car elle fonctionne si je rentre les
coordonnées d'un graphe.

Helpppp

Merci!

[toc] | [next] | [standalone]

#3422

Bonjour,

Le 19/12/2020 à 19:09, Student a écrit dans le message
<wJ-dnYX21u4g3EPCnZ2dnUU798zNnZ2d@giganews.com> :

> graphe = dict(enumerate(dict(enumerate(row)) for row in mat))
> [...]
>     starting_vertex='0'
>     T = [starting_vertex]
>     Q = [node for node in graphe if node!=starting_vertex]

Je n'ai pas regardé en détail mais je pense qu'il y a un problème ici et
ce que tu veux réellement est « starting_vertex = 0 » (l'entier, pas la
chaîne de caractère). Ou alors modifier la création de ton graphe pour
que les clés soient des chaîne de caractère :

graphe = {str(k): {str(x): y for x, y in enumerate(v)}
          for k, v in enumerate(mat)}

-- 
Benoit Izac

[toc] | [prev] | [standalone]

Back to top | Article view | fr.comp.lang.python

csiph-web