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

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

urgence! lire une matrice en graphe

Show all headers | View raw

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!

Back to fr.comp.lang.python | Previous | Next — Next in thread | Find similar

Thread

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

csiph-web