from Categorie import Categorie, unique_generator from Morphisme import Morphisme from ProduitGenerateurs import produit_cartesien_generateurs from copy import copy import itertools import functools from config import * if GRAPHVIZ_ENABLED: from graphviz import Digraph from typing import * class CategorieLibre(Categorie): """ Classe abstraite qui définit ce qu'est une catégorie libre engendrée par un graphe de composition. Cette classe surcharge l'opérateur __call__, pour calculer C(a,b), on fait tous les chemins de a vers b et on renvoie l'ensemble de ces composées. Les classes filles doivent implémenter (en plus de la méthode identite) la méthode __getitem__ qui renvoie les flèches élémentaires entre des sources et des cibles. Cette méthode définit le graphe sous-jacent. """ __id = 0 nb_viz = 0 def __init__(self, objets:set = set(), nom:str = None): CategorieLibre.__id += 1 self.__id = CategorieLibre.__id Categorie.__init__(self,objets,"Categorie libre "+str(self.__id) if nom == None else nom) def __getitem__(self, couple_sources_cibles:tuple) -> Generator[Morphisme,None,None]: raise NotImplementedError("Les classes filles doivent implementer cette methode.") @unique_generator # on ne doit renvoyer qu'une fois chaque flèche def __call__(self, sources:set, cibles:set) -> Generator[Morphisme,None,None]: """Soit C est une catégorie: C({a_i},{b_i}) renvoie l'ensemble des flèches d'un élément de {a_i} vers un élément de {b_i}. Pour la catégorie libre, on doit énumérer tous les chemins et les composer. """ for source in sources: for cible in cibles: for morph in self.enumerer_composees(source,cible): yield morph def decomposition_morphisme(self, morphisme:Morphisme) -> Generator[Morphisme,None,None]: '''Renvoie un générateur de morphismes élémentaires qui composés donnent le `morphisme`.''' if morphisme in self[{morphisme.source},{morphisme.cible}]: yield morphisme else: def enumerer_chemin_elem_sans_cycle(source:Any, cible:Any, noeuds_deja_visites:tuple=tuple()) -> frozenset(): if source == cible: return frozenset({(self.identite(source),)}) if source not in noeuds_deja_visites: noeuds_deja_visites = noeuds_deja_visites + (source,) composees_resultat = frozenset() for morph in self[{source},self.objets]: for composition_candidate in enumerer_chemin_elem_sans_cycle(morph.cible, cible, noeuds_deja_visites): composees_resultat |= {composition_candidate+(morph,)} return composees_resultat return frozenset() for chemin in enumerer_chemin_elem_sans_cycle(morphisme.source,morphisme.cible): resultat = functools.reduce(lambda x,y:y@x,chemin) if resultat == morphisme: for morph_elem in chemin: yield morph_elem break def verifier_coherence(self): """Vérifie la cohérence de la structure du graphe de composition sous-jacent.""" # on vérifie que tous les morphismes de la catégorie sont dans les morph_entrants et morph_sortants Categorie.verifier_coherence(self) for morph in self(self.objets,self.objets): if len(morph) == 1: if morph not in self[{morph.source},self.objets]: raise Exception("Incoherence CategorieLibre : le morphisme "+str(morph)+" ne sort pas de "+str(morph.source)) if morph not in self[self.objets,{morph.cible}]: raise Exception("Incoherence CategorieLibre : le morphisme "+str(morph)+" n'entre pas dans "+str(morph.cible)) def enumerer_composees_sans_cycle(self, source:Any, cible:Any) -> Generator[Morphisme,None,None]: """ Génère tous les morphismes composés allant de `source` à `cible` ne contenant aucun cycle (on ne passe jamais deux fois par le même noeud). """ for chemin in self.enumerer_chemins_sans_cycle(source,cible): if len(chemin) == 1: for e in self[{chemin[0]},{chemin[0]}]: yield e else: generateurs = [self[{chemin[i]},{chemin[i+1]}] for i in range(len(chemin)-1)] for prod in produit_cartesien_generateurs(*generateurs): yield functools.reduce(lambda x,y : y@x, prod) def enumerer_chemins_sans_cycle(self, source:Any, cible:Any) -> Generator[tuple,None,None]: """ Génère tous les chemins (liste de noeuds) allant de `source` à `cible` ne contenant aucun cycle (on ne passe jamais deux fois par le même noeud). """ # on fait un parcours en largeur file_chemins = [(source,)] while len(file_chemins) > 0: chemin = file_chemins.pop(0) if chemin[-1] == cible: yield chemin else: for obj in self.objets: if obj not in chemin: if self.existe_morphisme_elementaire(chemin[-1],obj): file_chemins += [chemin+(obj,)] @unique_generator def trouver_cycles_minimaux(self, objet:Any) -> Generator[Morphisme,None,None]: """Génère tous les cycles minimaux de morphismes élémentaires (qui ne contiennent aucun cycle) de `objet` à `objet` différent de l'identité.""" for morph_pred in self[self.objets,{objet}]: if morph_pred.source == objet: yield morph_pred else: pred = morph_pred.source for cycle_tronque in self.enumerer_composees_sans_cycle(objet, pred): cycle = morph_pred@cycle_tronque if not cycle.is_identite: yield cycle def enumerer_cycles(self, objet:Any, limite_profondeur:int = 10) -> Generator[Morphisme,None,None]: """Enumère toutes les compositions de `objet` à `objet`. Si f et g sont des cycles minimaux, on doit énumérer tous les mots d'alphabet {f,g}. Pour ça on s'intéresse aux compositions qui se réduisent en composition déjà générées. Si f ne se réduit pas, on regarde ff et fg, puis si ceux là non plus fff, ffg, fgf,fgg etc. On s'arrête à la limite de profondeur spécifiée. """ cycles = set(self.trouver_cycles_minimaux(objet)) cycles_a_reduire = copy(cycles) cycles_minimaux = copy(cycles) cycles |= {self.identite(objet)} for cycle in cycles: yield cycle for profondeur in range(limite_profondeur): for cycle_a_reduire in copy(cycles_a_reduire): for cycle_minimal in cycles_minimaux: if cycle_minimal@cycle_a_reduire not in cycles: new_cycle = cycle_minimal@cycle_a_reduire cycles_a_reduire |= {new_cycle} cycles |= {new_cycle} yield new_cycle cycles_a_reduire -= {cycle_a_reduire} if len(cycles_a_reduire) > 0: print("Warning CategorieLibre : limite de profondeur atteinte dans l'enumeration des cycles") if DEBUG_LOI_DE_COMPOSITION: print(cycles_a_reduire) def enumerer_composees(self, source:Any, cible:Any) -> Generator[Morphisme,None,None]: """Génère tous les morphismes composés allant de `source` à `cible`. 1) On trouve les chemins sans cycle. 2) Pour tous les noeuds U du chemin on énumère les cycles de U à U. 3) Pour chaque chemin sans cycle, pour chaque noeud qui a au moins un cycle, on duplique le chemin d'autant de cycles que nécessaires.""" chemins_sans_cycles = self.enumerer_chemins_sans_cycle(source, cible) dict_noeuds_cycles = dict() # {noeud : set(cycles)} for chemin in chemins_sans_cycles: cycles_concernes = [] for noeud in chemin: if noeud not in dict_noeuds_cycles: dict_noeuds_cycles[noeud] = set(self.enumerer_cycles(noeud)) cycles_concernes += [dict_noeuds_cycles[noeud]] if len(chemin) >= 2: fleches_concernees = [self[{chemin[i]},{chemin[i+1]}] for i in range(len(chemin)-1)] for combinaison_fleches in produit_cartesien_generateurs(*fleches_concernees): for combinaison_cycle in itertools.product(*cycles_concernes): composee = combinaison_cycle[0] for i in range(len(combinaison_fleches)): composee = combinaison_cycle[i+1]@combinaison_fleches[i]@composee yield composee else: # taille du chemin == 1 for e in cycles_concernes[0]: yield e def test_enumerer_chemins_sans_cycle(): from GrapheDeComposition import GC,MGC GC = GC({'A','B','C','D','E','F'}) f,g,h,i,j,k,l,m,n = [MGC('A','B','f'),MGC('B','C','g'),MGC('A','A','h'),MGC('C','D','i'), MGC('C','E','j'),MGC('E','F','k'),MGC('D','F','l'),MGC('D','D','m'),MGC('C','D','n')] MGC.identifier_morphismes(h@h@h,h) MGC.identifier_morphismes(m@m,m) GC |= {f,g,h,i,j,k,l,m,n} GC.transformer_graphviz() for composee in GC.enumerer_chemins_sans_cycle('A','F'): print(composee) print() def test_enumerer_composees_sans_cycle(): from GrapheDeComposition import GC,MGC GC = GC({'A','B','C','D','E','F'}) f,g,h,i,j,k,l,m,n = [MGC('A','B','f'),MGC('B','C','g'),MGC('A','A','h'),MGC('C','D','i'), MGC('C','E','j'),MGC('E','F','k'),MGC('D','F','l'),MGC('D','D','m'),MGC('C','D','n')] MGC.identifier_morphismes(h@h@h,h) MGC.identifier_morphismes(m@m,m) GC |= {f,g,h,i,j,k,l,m,n} GC.transformer_graphviz() for composee in GC.enumerer_composees_sans_cycle('A','F'): print(composee) print() def test_trouver_cycles_minimaux(): from GrapheDeComposition import GC,MGC GC = GC({'A','B','C','D','E','F'}) f,g,h,i,j,k,l,m,n,o = [MGC('A','B','f'),MGC('B','C','g'),MGC('A','A','h'),MGC('C','D','i'), MGC('C','E','j'),MGC('E','F','k'),MGC('D','F','l'),MGC('D','D','m'),MGC('C','D','n'),MGC('D','A','o')] MGC.identifier_morphismes(h@h@h,h) MGC.identifier_morphismes(m@m,m) MGC.identifier_morphismes(o@i@g@f@o@i@g@f,o@i@g@f) MGC.identifier_morphismes(o@i@g@f@o@n@g@f,o@i@g@f) MGC.identifier_morphismes(o@n@g@f@o@i@g@f,o@n@g@f) MGC.identifier_morphismes(o@n@g@f@o@n@g@f,o@n@g@f) GC |= {f,g,h,i,j,k,l,m,n,o} GC.transformer_graphviz(complet=False) for composee in GC.trouver_cycles_minimaux('D'): print(composee) print() def test_enumerer_composees(): from EnsFinis import EnsFinis cat = EnsFinis({frozenset("ABCD"),frozenset("ABC")}) print(len(list(cat({frozenset("ABCD")},{frozenset("ABC")})))) cat.transformer_graphviz() if __name__ == '__main__': test_enumerer_chemins_sans_cycle() test_enumerer_composees_sans_cycle() test_trouver_cycles_minimaux() test_enumerer_composees()