Bonjour,
Je suis étudiante et dans le cadre d'un projet d'informatique je dois implémenter l'abre couvrant minimal de Kruskal. Mais dans les questions préliminaires je dois calculer le produit de deux matrices représentant 2 graphes. J'ai une erreur d'index que je n'arrive pas a resoudre.
Quelqu'un pourrait m'aider s'il vous plaît?
class Arete:
def __init__(self, initial, final, cout):
self.sommet_initial=initial
self.sommet_final=final
self.cout_arrete=cout
def saisie_arete():
print("Veuillez saisir une arrête: ")
si=int(input("Sommet initial: "))
sf=int(input("Sommet final: "))
cout=float(input("Cout: "))
a = Arete (si,sf,cout)
return a
class Graphe:
def __init__(self,nbsommets,listearetes):
self.nbsommets=nbsommets
self.listearetes=listearetes
def saisie_graphe():
listearetes=[]
nbsommets=int(input("Nombre de sommets: "))
nbaretes=int(input("Nombre d'aretes: "))
for i in range(0, nbaretes):
arete =[]
print("Saisissez l'arete numero ", i+1)
a=saisie_arete()
arete.append(a.sommet_initial)
arete.append(a.sommet_final)
arete.append(a.cout_arrete)
listearetes.append(arete)
g = Graphe (nbsommets,listearetes)
return g
def adjacence(g):
mat = [[0 for i in range(g.nbsommets)]for i in range(g.nbsommets)]
for i in range(len(g.listearetes)):
mat[g.listearetes[i][0]][g.listearetes[i][1]] = g.listearetes[i][2]
mat[g.listearetes[i][1]][g.listearetes[i][0]] = g.listearetes[i][2]
return mat
g = saisie_graphe()
h= saisie_graphe()
print (adjacence(g))
print(adjacence(h))
M1=np.array(adjacence(g))
M2=np.array(adjacence(h))
def produit(M1,M2):
M3=[0][0]
if len(M1)==len(M1[0])==len(M2)==len(M2[0]):
np.dot(M1,M2)
else:
print("Erreur de dimensions")
return M3
1 Construction d'un graphe et de sa matrice d'adjacence
a) Ecrire une fonction qui permet de construire une arête à partir d'informations saisies au clavier def saisie_arete()
b) En déduire une fonction qui permet de construire un graphe à partir d'informations saisies au clavier def saisie_graphe()
c) Ecrire une fonction qui prend en entrée un graphe et qui renvoie sa matrice d'adjacence def adjacence(g)
d) Ecrire une fonction qui prend en entrée une matrice d'adjacence et qui l'affiche sous sa forme matricielle (affichage ligne par ligne) def affichermatrice(matrice)
Ecrire un programme principal permettant de tester les fonctions ci dessus
2 – Calcul de la puissance d'une matrice
a) Ecrire une fonction qui prend en entrée deux matrices M1 et M2 de réels et qui renvoie la matrice M1*M2 (ps : M1 et M2 sont supposées être des matrices carrées de mêmes dimensions) def produit (M1, M2)
b) Ecrire une fonction qui prend en entrée une matrice M et un entier n et qui renvoie la matrice Mn =M*M*...M def puissance (M, n)
c) En déduire une fonction qui prend en entrée une matrice M, un entier n, deux sommets i et j puis qui renvoie le nombre de chemins de longueur n entre i et j. def nbchemins( M, n, i, j)
Ecrire un programme principal permettant de tester les fonctions ci dessus
Voici le début de la partie commune aux sujets du projet. J'ai essayé de faire le début, jusqu'à la question 2 a).
as-tu expliqué quelles réponses donner pour obtenir l'erreur?
ne penses-tu pas qu'il serait préférable de partager un programme qui ne pose pas de question?
Vu que tu utilises numpy, pourquoi n'utilise-tu pas directement le produit matriciel de numpy ?
Sinon comme le dit yg_be, quand tu partages ton code le mieux serait d'enlever la partie interactive et de hardcoder les paramètres qui lèvent le problème.
Bonjour, finalement j'ai réussi à faire la question avec un autre programme, qui fonctionne bien normalement.
def produit(M1, M2):
M3 = []
if len(M1[0]) != len(M2):
print("Erreur de dimension")
return False
for i in range(len(M1)):
ligne = []
for j in range(len(M2[0])):
element = 0
for k in range(len(M1[0])):
element = element + M1[i][k] * M2[k][j]
ligne.append(element)
M3.append(ligne)
return M3
print("M1*M2 = ",produit(M1,M2))
Pense bien à sélectionner le bout de code à mettre en forme avant de cliquer sur le bouton des balises de code, de sorte à ce que le code soit encadré par les balises insérées.
Sinon plus simplement :
import numpy as np
def produit(M1, M2):
return np.matmul(M1, M2)
