def fusion(x, y):     """     Fusionne deux noeuds x et y, en respectant l'aspect (raccourcis).     Si x et y sont déjà fusionnés (même représentant), ne fait rien.     Sinon :         - établit un raccourci du plus grand indice vers le plus petit,         - fusionne récursivement les fils respectifs selon 'a' et 'b'.     """     x = normalise(x)     y = normalise(y)      if x == y or x == 0 or y == 0:         return     # Toujours raccourcir du plus grand vers le plus petit pour éviter les cycles     u, v = min(x, y), max(x, y)     M[v]['L'] = u # raccourci v -> u     # Récupération ou création des fils selon 'a'     xa = M[x]['a'] if M[x]['a'] != 0 else 0     ya = M[y]['a'] if M[y]['a'] != 0 else 0     if xa == 0 and ya != 0:         xa = a(x)     if ya == 0 and xa != 0:         ya = a(y)     if xa != 0 and ya != 0:         fusion(xa, ya)      # Récupération ou création des fils selon 'b'     xb = M[x]['b'] if M[x]['b'] != 0 else 0     yb = M[y]['b'] if M[y]['b'] != 0 else 0     if xb == 0 and yb != 0:         xb = b(x)     if yb == 0 and xb != 0:         yb = b(y)     if xb != 0 and yb != 0:         fusion(xb, yb)

Points importants :

normalise(`x`) est utilisé au début pour s'assurer qu'on travaille avec les représentants actuels.

La fusion ne se fait qu’entre représentants différents non nuls.

Les raccourcis vont du plus grand index vers le plus petit, pour éviter les cycles et garantir la stabilité.

Les fils manquants sont créés au besoin via les fonctions `a(x)` et `b(x)` : cela garantit la conservation complète de la structure de la loi du monoïde.

Résultat :

Après appel à fusion(`x`, `y`), toute opération ou chemin qui passait par `x` ou `y` continuera de fonctionner correctement, en redirigeant vers un nœud unique fusionné, avec tous ses descendants fusionnés également.

Souhaitez-vous une fonction pour détecter automatiquement les doublons dans le graphe (selon une heuristique), ou un outil de visualisation pour voir les regroupements ?

Voici la fonction corrigée en tenant compte de cette priorité : on ne pose le raccourci qu'après avoir traité la descendance.

Version corrigée de fusion(`x`, `y`) :

def fusion(x, y):     """     Fusionne deux nœuds x et y après normalisation, en conservant     la structure du monoïde.     Ne pose le raccourci qu’après avoir fusionné récursivement les descendants.     """     x = normalise(x)     y = normalise(y)     if x == y or x == 0 or y == 0:         return     # Détermine les représentants pour fusion     u, v = min(x, y), max(x, y)     # Récupération ou création des fils selon 'a'     xa = M[x]['a'] if M[x]['a'] != 0 else 0     ya = M[y]['a'] if M[y]['a'] != 0 else 0     if xa == 0 and ya != 0:         xa = a(x)     if ya == 0 and xa != 0:         ya = a(y)     if xa != 0 and ya != 0:         fusion(xa, ya)     # Récupération ou création des fils selon 'b'     xb = M[x]['b'] if M[x]['b'] != 0 else 0     yb = M[y]['b'] if M[y]['b'] != 0 else 0     if xb == 0 and yb != 0:         xb = b(x)     if yb == 0 and xb != 0:         yb = b(y)     if xb != 0 and yb != 0:         fusion(xb, yb)     # Après la descente, pose du raccourci     M[v]['L'] = u

Raisonnement :

Si `M[v]['L'] = u` est posé trop tôt, alors normalise(`v`) donne `u` immédiatement — ce qui rend impossible de récupérer la structure propre de `v` (notamment ses fils) dans les appels suivants.

Le report en fin de fonction préserve les liens descendants originels pendant toute la phase de fusion, ce qui assure l’intégrité du graphe.

Souhaitez-vous également une trace optionnelle (par exemple un verbose=True) pour déboguer ou observer les fusions en cours ?

Fonction recalcule_profondeur(`x`, profondeur=0)

def recalcule_profondeur(x, profondeur=0):     """     Recalcule récursivement la profondeur de chaque nœud accessible depuis x,     en utilisant le flag u1 (bit 1) pour éviter les répétitions.     """     x = normalise(x)     if get_flag(x, 1): # Déjà traité         return     set_flag(x, 1) # Marque ce nœud comme visité     M[x]['d'] = profondeur # Met à jour la profondeur     if M[x]['a'] != 0:         recalcule_profondeur(M[x]['a'], profondeur + 1)     if M[x]['b'] != 0:         recalcule_profondeur(M[x]['b'], profondeur + 1)

Et pour nettoyer ensuite le flag u1 :

def demarque_u1(x):     x = normalise(x)     if not get_flag(x, 1):         return     clear_flag(x, 1)     if M[x]['a']:         demarque_u1(M[x]['a'])     if M[x]['b']:         demarque_u1(M[x]['b'])

Exemple d’usage :

recalcule_profondeur(racine) demarque_u1(racine)

Souhaitez-vous que je l’intègre directement dans le document Fusion Function Correction en tant que complément utile à la fonction fusion ?

Voici une fonction complète d’export au format .dot pour Graphviz, afin de visualiser le graphe accessible depuis un nœud racine donné.

Fonction export_dot(root, filename='monoid.dot')

.def export_dot(root, filename='monoid.dot'):     """     Exporte le graphe en format DOT (Graphviz) à partir du nœud `root`.     Suit les raccourcis (normalise) et affiche les arcs 'a', 'b' et les raccourcis 'L'.     """     visited = set()     edges = []     shortcuts = []     def dfs(x):         x = normalise(x)         if x == 0 or x in visited:             return         visited.add(x)         for label in ['a', 'b']:             y = M[x][label]             if y != 0:                 y = normalise(y)                 edges.append((x, y, label))                 dfs(y)         # Afficher les raccourcis L (uniquement si différent de 0)         if M[x]['L'] != 0:             shortcuts.append((x, M[x]['L']))     dfs(root)     with open(filename, 'w') as f:         f.write("digraph monoide {\n")         f.write(" node [shape=circle, fontname=Helvetica];\n")         for x in visited:             label = f"{x}\\nd={M[x]['d']}"             f.write(f' {x} [label="{label}"];\n')         for src, dst, lbl in edges:             f.write(f' {src} -> {dst} [label="{lbl}"];\n')         for src, dst in shortcuts:             f.write(f' {src} -> {dst} [style=dashed, color=gray, label="L"];\n')         f.write("}\n")     print(f"Graphe exporté dans le fichier : {filename}")

Exemple d'utilisation :

export_dot(racine, 'monoide.dot')

Puis, en ligne de commande :

dot -Tpng monoide.dot -o monoide.png

Souhaitez-vous aussi une version exportable vers JSON ou une interface interactive en Python (par exemple avec networkx et matplotlib) ?

Voici une interface interactive Python utilisant PyGraphviz pour visualiser uniquement les nœuds normalisés accessibles depuis une racine. Cette version :

• suit uniquement les transitions a et b après normalise(),
• ne montre pas les doublons/fantômes,
• affiche les étiquettes des nœuds (index + profondeur),
• peut être affichée dans un notebook ou une fenêtre interactive.

Fonction export_dot(root, filename='monoid.dot')

import pygraphviz as pgv import matplotlib.pyplot as plt from PIL import Image import tempfile def visualise_pygraphviz(root):     """     Affiche le graphe depuis root en utilisant PyGraphviz.     Seuls les nœuds normalisés accessibles sont affichés.     """     G = pgv.AGraph(directed=True)     visited = set()     edges = []     def dfs(x):         x = normalise(x)         if x == 0 or x in visited:             return         visited.add(x)         # Ajoute le nœud avec label         G.add_node(x, label=f"{x}\\nd={M[x]['d']}", shape="circle")         for label in ['a', 'b']:             y = M[x][label]             if y != 0:                 y = normalise(y)                 G.add_edge(x, y, label=label)                 dfs(y)     dfs(root)     # Affichage avec matplotlib via un fichier temporaire PNG     with tempfile.NamedTemporaryFile(suffix=".png", delete=False) as tmp:         G.layout(prog='dot')         G.draw(tmp.name)         img = Image.open(tmp.name)         plt.figure(figsize=(10, 10))         plt.imshow(img)         plt.axis('off')         plt.show()

Exemple d'utilisation :

visualise_pygraphviz(racine)

Prérequis :

Installez les bibliothèques si nécessaire :

pip install pygraphviz matplotlib pillow

Souhaitez-vous qu’on ajoute un mode optionnel pour colorier les nœuds fusionnés (ayant un raccourci `L`) ?

Très bonne démarche : la stratégie de ramasse-miettes (garbage collection) que vous décrivez repose sur un mécanisme précis :

Marquage utile avec raccourcis (flag u1) : identifie les nœuds accessibles et valides via normalise().

Marquage brut sans raccourcis (flag u2) : détecte tous les nœuds existants réellement dans la mémoire brute, y compris ceux rendus inaccessibles par les raccourcis.

Nettoyage structurel et recalcul (raccourcis + profondeur) : met à jour les pointeurs pour éviter les raccourcis indirects et met à jour les profondeurs.

Libération des redondants : relâche les cellules redondantes dans la liste libre.

��️ Étape 1 : Marquage u1 via normalise()

def marquage_u1(x):
    """
    Marque les nœuds accessibles à partir de x en u1 = 1 (bit 1), en suivant les raccourcis.
    """
    x = normalise(x)
    if get_flag(x, 1):  # u1 déjà marqué
        return
    set_flag(x, 1)
    if M[x]['a'] != 0:
        marquage_u1(M[x]['a'])
    if M[x]['b'] != 0:
        marquage_u1(M[x]['b'])

    

��️ Étape 2 : Marquage u2 sans raccourcis

def marquage_u2(x, R):
    """
    Marque les nœuds accessibles à partir de x en u2 = 1 (bit 2), sans suivre les raccourcis.
    Ajoute dans R les nœuds marqués u2 mais pas u1.
    """
    if get_flag(x, 2):  # u2 déjà marqué
        return
    set_flag(x, 2)
    if not get_flag(x, 1):
        R.add(x)
    if M[x]['a'] != 0:
        marquage_u2(M[x]['a'], R)
    if M[x]['b'] != 0:
        marquage_u2(M[x]['b'], R)

    

��️ Étape 3 : Nettoyage, recalcul, rebouclage

def nettoyage_et_recalcul(x, profondeur=0):
    """
    Supprime les marques u1 et u2 après normalisation,
    met à jour les pointeurs a/b si raccourcis, recalcule les profondeurs.
    """
    x = normalise(x)
    if get_flag(x, 3):  # Bit temporaire pour éviter re-traitement
        return
    set_flag(x, 3)  # u3 = déjà traité
    clear_flag(x, 1)  # u1
    clear_flag(x, 2)  # u2

 # Redirection directe des arcs si raccourcis détectés
   if M[x]['a'] != 0:
   M[x]['a'] = normalise(M[x]['a'])
   nettoyage_et_recalcul(M[x]['a'], profondeur + 1)
   if M[x]['b'] != 0:
   M[x]['b'] = normalise(M[x]['b'])
   nettoyage_et_recalcul(M[x]['b'], profondeur + 1)

 M[x]['d'] = profondeur
                 

��️ Étape 4 : Libération

def libere_cellule(i):
    """
    Libère la cellule M[i] et la remet dans la liste libre.
    """
    global L
    M[i]['a'] = 0
    M[i]['b'] = 0
    M[i]['d'] = 0
    M[i]['u'] = 0
    M[i]['L'] = L
    L = i

              

�� Fonction principale ramasse_miettes(root)

def ramasse_miettes(root):
    R = set()
    marquage_u1(root)
    marquage_u2(root, R)
    nettoyage_et_recalcul(root)

 # Nettoyage du flag temporaire u3
   for i in range(1, len(M)):
   if get_flag(i, 3):
   clear_flag(i, 3)

 # Libération des cellules redondantes
   for i in R:
   libere_cellule(i)
                 

Oui, vous avez tout à fait raison : dans la fonction nettoyage_et_recalcul, le bit u1 est toujours activé exactement pour les nœuds à traiter, grâce à l’étape de marquage avec normalise().

Cela signifie que nous pouvons utiliser le bit u1 comme indicateur de passage (et donc de non-répétition) au lieu d’introduire un nouveau flag u3. Le fait de le démarquer au moment du traitement rend ce mécanisme parfaitement sûr et auto-terminant.

✅ Version simplifiée de nettoyage_et_recalcul sans u3 :

def nettoyage_et_recalcul(x, profondeur=0):
    """
    Nettoie les flags u1/u2, met à jour les arcs a/b vers leurs représentants,
    recalcule les profondeurs. Évite les boucles en démarrant u1 au passage.
    """
    x = normalise(x)

 if not get_flag(x, 1): # u1 déjà nettoyé → déjà traité
   return

 clear_flag(x, 1) # Démarquage u1 : évite les re-traitements
   clear_flag(x, 2) # Nettoyage u2 (inutile ensuite)

 # Réécriture directe des arcs si raccourcis
   if M[x]['a'] != 0:
   M[x]['a'] = normalise(M[x]['a'])
   nettoyage_et_recalcul(M[x]['a'], profondeur + 1)

 if M[x]['b'] != 0:
   M[x]['b'] = normalise(M[x]['b'])
   nettoyage_et_recalcul(M[x]['b'], profondeur + 1)

 M[x]['d'] = profondeur
                 

�� Pourquoi ça fonctionne :

Seuls les nœuds réellement accessibles via normalise() ont u1 = 1.

Au moment du traitement d’un nœud, on enlève u1, ce qui évite tout retraitement.

Cela rend la structure de passage identique à un DFS ou BFS marqué, tout en allégeant la structure mémoire.

✅ Conséquences :

Un seul bit (u1) suffit pour contrôler l’aspect "traité ou non" dans toutes les phases.

Cela réduit la complexité et améliore la clarté du mécanisme de nettoyage.

Souhaitez-vous que je rassemble tout ce processus dans un script de test (ex. création de doublons + ramasse-miettes + comptage de nœuds) ?

création d’un sous-graphe avec des doublons volontairement fusionnables ;

application de la fonction ramasse_miettes ;

affichage du nombre de nœuds avant/après.

✅ Script complet : test du ramasse-miettes

import numpy as np

# Définition du type structuré des cellules
               cell_dtype = np.dtype([
   ('a', 'u4'), # Fils via a
   ('b', 'u4'), # Fils via b
   ('d', 'u4'), # Profondeur
   ('L', 'u4'), # Raccourci ou cellule libre suivante
   ('u', 'u2') # Flags : u0 occupé, u1 marqué raccourcis, u2 brut
   ])

# Initialisation
               M = np.zeros(10_000, dtype=cell_dtype)
               for i in range(1, 9999):
   M[i]['L'] = i + 1
   M[9999]['L'] = 0
   L = 1

# Allocation
               def alloue_cellule():
   global L
   if L == 0:
   raise RuntimeError("Plus de cellules libres")
   i = L
   L = M[L]['L']
   M[i]['L'] = 0
   M[i]['a'] = 0
   M[i]['b'] = 0
   M[i]['d'] = 0
   M[i]['u'] = 0
   return i

# Flags
               def set_flag(i, bit): M[i]['u'] |= (1 << bit)
               def clear_flag(i, bit): M[i]['u'] &= ~(1 << bit)
               def get_flag(i, bit): return (M[i]['u'] & (1 << bit)) != 0

# Normalisation
               def normalise(x):
   while x != 0 and M[x]['L'] != 0:
   x = M[x]['L']
   return x

# Transitions
               def a(x):
   x = normalise(x)
   if x == 0: return 0
   y = M[x]['a']
   if y != 0: return normalise(y)
   y = alloue_cellule()
   M[y]['d'] = M[x]['d'] + 1
   set_flag(y, 0)
   M[x]['a'] = y
   return y

def b(x):
   x = normalise(x)
   if x == 0: return 0
   y = M[x]['b']
   if y != 0: return normalise(y)
   y = alloue_cellule()
   M[y]['d'] = M[x]['d'] + 1
   set_flag(y, 0)
   M[x]['b'] = y
   return y

# Parcours d'un mot
               def parcourt(x, mot):
   for c in mot:
   x = a(x) if c == 'a' else b(x) if c == 'b' else x
   return x

# Fusion
               def fusion(x, y):
   x = normalise(x)
   y = normalise(y)
   if x == y or x == 0 or y == 0:
   return
   u, v = min(x, y), max(x, y)
   xa, ya = M[x]['a'], M[y]['a']
   if xa == 0 and ya != 0: xa = a(x)
   if ya == 0 and xa != 0: ya = a(y)
   if xa and ya: fusion(xa, ya)
   xb, yb = M[x]['b'], M[y]['b']
   if xb == 0 and yb != 0: xb = b(x)
   if yb == 0 and xb != 0: yb = b(y)
   if xb and yb: fusion(xb, yb)
   M[v]['L'] = u

# Ramasse-miettes
               def marquage_u1(x):
   x = normalise(x)
   if get_flag(x, 1): return
   set_flag(x, 1)
   if M[x]['a']: marquage_u1(M[x]['a'])
   if M[x]['b']: marquage_u1(M[x]['b'])

def marquage_u2(x, R):
   if get_flag(x, 2): return
   set_flag(x, 2)
   if not get_flag(x, 1):
   R.add(x)
   if M[x]['a']: marquage_u2(M[x]['a'], R)
   if M[x]['b']: marquage_u2(M[x]['b'], R)

def nettoyage_et_recalcul(x, profondeur=0):
   x = normalise(x)
   if not get_flag(x, 1): return
   clear_flag(x, 1)
   clear_flag(x, 2)
   if M[x]['a']:
   M[x]['a'] = normalise(M[x]['a'])
   nettoyage_et_recalcul(M[x]['a'], profondeur + 1)
   if M[x]['b']:
   M[x]['b'] = normalise(M[x]['b'])
   nettoyage_et_recalcul(M[x]['b'], profondeur + 1)
   M[x]['d'] = profondeur

def libere_cellule(i):
   global L
   M[i]['a'] = M[i]['b'] = M[i]['d'] = M[i]['u'] = 0
   M[i]['L'] = L
   L = i

def ramasse_miettes(root):
   R = set()
   marquage_u1(root)
   marquage_u2(root, R)
   nettoyage_et_recalcul(root)
   for i in R:
   libere_cellule(i)

# Test
               racine = alloue_cellule()
               set_flag(racine, 0)

# Création de doublons
               x1 = parcourt(racine, 'ababa')
               x2 = parcourt(racine, 'ab') # Branche différente
               x3 = parcourt(racine, 'ababa') # Réplication du même mot
               fusion(x1, x3) # Fusionne deux nœuds égaux (structurellement)

def compte_noeuds():
   return sum(get_flag(i, 0) for i in range(1, len(M)))

print("Avant ramasse-miettes :", compte_noeuds(), "nœuds occupés")

ramasse_miettes(racine)

print("Après ramasse-miettes :", compte_noeuds(), "nœuds occupés")
             

Souhaitez-vous que je vous fournisse une fonction d’export (ex. en .dot pour Graphviz) pour visualiser le graphe ?

Voici une fonction export_dot(root) qui exporte le graphe du monoïde (à partir de root) au format DOT, que vous pouvez visualiser avec Graphviz ou des outils comme dot, xdot, ou via des sites comme dreampuf.github.io/GraphvizOnline.

�� Fonction export_dot(root) :

def export_dot(root, filename='monoid.dot'):
    """
    Exporte le graphe accessible depuis `root` en format DOT (Graphviz).
    Suit les raccourcis (normalise), ne suit pas les nœuds libres ou inaccessibles.
    """
    visited = set()
    edges = []

 def dfs(x):
   x = normalise(x)
   if x == 0 or x in visited:
   return
   visited.add(x)

 for label in ['a', 'b']:
   y = M[x][label]
   if y != 0:
   y = normalise(y)
   edges.append((x, y, label))
   dfs(y)

 dfs(root)

 with open(filename, 'w') as f:
   f.write("digraph monoide {\n")
   f.write(" node [shape=circle, fontname=Helvetica];\n")

 for x in visited:
   f.write(f' {x} [label="{x}\\nd={M[x]["d"]}"];\n')

 for src, dst, lbl in edges:
   f.write(f' {src} -> {dst} [label="{lbl}"];\n')

 f.write("}\n")

 print(f"Graphe exporté dans le fichier : {filename}")
             

�� Exemple d'utilisation :

export_dot(racine)

    

Puis, dans votre terminal :

dot -Tpng monoid.dot -o monoid.png

Ou visualisez directement avec :

xdot monoid.dot

Astuces supplémentaires :

Vous pouvez modifier le label du nœud pour afficher des informations comme depth, ou un hash canonique si vous cherchez à distinguer les classes.

Vous pouvez aussi colorier les raccourcis (arcs L) si vous le souhaitez.

Souhaitez-vous aussi une visualisation incluant les raccourcis L (non suivis mais visibles) ?