urgence! lire une matrice en graphe

Le
Student14 offline Hors ligne
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!
  • Partager ce contenu :
Vos réponses
Trier par : date / pertinence
Benoit Izac
Le #26563213
Bonjour,
Le 19/12/2020 Í  19:09, Student a écrit dans le message
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
Poster une réponse
Anonyme