Documentation technique

graphes_matrices.py

3 min de lecture

graphes_matrices.py

Note de lecture générée automatiquement

Le vrai fichier est scripts/maths/graphes_matrices.py (Obsidian n’affiche pas les scripts eux-mêmes). Ne modifie pas cette note : modifie le script, puis relance python3 generer_vues_obsidian.py dans le dossier scripts.

Code

#!/usr/bin/env python3
"""
graphes_matrices.py — Graphe orienté : matrice d'adjacence, puissances M^k
(nombre de chemins de longueur k), circuits, fermeture transitive, niveaux.
 
Utilisation :
    python3 graphes_matrices.py "A>B A>C B>D D>A D>E E>D"
    python3 graphes_matrices.py "A>B A>C B>D C>E D>E D>F E>F" 3     (puissances jusqu'à M^3)
 
Chaque arc s'écrit Origine>Destination, séparés par des espaces.
"""
import sys
 
 
def produit(m1: list, m2: list) -> list:
    taille = len(m1)
    return [[sum(m1[i][k] * m2[k][j] for k in range(taille)) for j in range(taille)]
            for i in range(taille)]
 
 
def ou_booleen(m1: list, m2: list) -> list:
    return [[1 if (a or b) else 0 for a, b in zip(l1, l2)] for l1, l2 in zip(m1, m2)]
 
 
def afficher(nom: str, matrice: list, sommets: list) -> None:
    print(f"\n{nom} :")
    print("     " + "  ".join(f"{s:>2}" for s in sommets))
    for sommet, ligne in zip(sommets, matrice):
        print(f"{sommet:>3} [" + "  ".join(f"{v:>2}" for v in ligne) + " ]")
 
 
def niveaux(sommets: list, arcs: list) -> dict:
    # Méthode des niveaux : on retire successivement les sommets sans prédécesseur
    restants = set(sommets)
    niveau_de = {}
    numero = 0
    while restants:
        sans_pred = [s for s in sorted(restants)
                     if not any(o in restants and d == s for o, d in arcs)]
        if not sans_pred:
            print("\nLe graphe contient un circuit : pas de niveaux possibles.")
            return {}
        for s in sans_pred:
            niveau_de[s] = numero
        restants -= set(sans_pred)
        numero += 1
    return niveau_de
 
 
if __name__ == "__main__":
    if len(sys.argv) < 2:
        sys.exit(__doc__)
    arcs = [tuple(arc.split(">")) for arc in sys.argv[1].split()]
    puissance_max = int(sys.argv[2]) if len(sys.argv) > 2 else 3
    sommets = sorted(set(s for arc in arcs for s in arc))
    index = {s: i for i, s in enumerate(sommets)}
    n = len(sommets)
 
    adjacence = [[0] * n for _ in range(n)]
    for origine, destination in arcs:
        adjacence[index[origine]][index[destination]] = 1
    afficher("Matrice d'adjacence M (ligne = origine, colonne = destination)", adjacence, sommets)
 
    for s in sommets:
        succ = [d for o, d in arcs if o == s]
        pred = [o for o, d in arcs if d == s]
        print(f"  {s} : successeurs {succ or '∅'}, prédécesseurs {pred or '∅'}")
 
    puissance = adjacence
    for k in range(2, puissance_max + 1):
        puissance = produit(puissance, adjacence)
        afficher(f"M^{k} (nombre de chemins de longueur {k})", puissance, sommets)
        print(f"  Circuits de longueur {k} (somme de la diagonale) : {sum(puissance[i][i] for i in range(n))}")
 
    # Fermeture transitive : M ∨ M^2 ∨ … ∨ M^n  (en booléen)
    fermeture = adjacence
    courante = adjacence
    for _ in range(2, n + 1):
        courante = [[1 if v else 0 for v in ligne] for ligne in produit(courante, adjacence)]
        fermeture = ou_booleen(fermeture, courante)
    afficher("Fermeture transitive M̂ (1 = il existe un chemin)", fermeture, sommets)
    if any(fermeture[i][i] for i in range(n)):
        print("  => 1 sur la diagonale : le graphe contient AU MOINS UN CIRCUIT.")
    else:
        print("  => Diagonale nulle : AUCUN circuit.")
        print(f"  Niveaux : {niveaux(sommets, arcs)}")

Vue Graphique

Liens retour