CategorieLibre.py 11.3 KB
Newer Older
1
from Categorie import Categorie, unique_generator
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
2
from Morphisme import Morphisme
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
3
from ProduitGenerateurs import produit_cartesien_generateurs
4
5
from copy import copy
import itertools
6
import functools
7
8
9
from config import *
if GRAPHVIZ_ENABLED:
    from graphviz import Digraph
10
from typing import *
11
12
13
14
15
16
17

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.
    
18
19
20
    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.
21
    """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
22
    __id = 0
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
23
24
    nb_viz = 0
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
25
26
27
28
    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)
29

30
31
32
33
34
35
36
37
    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.
38
        """
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
        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):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
61
                resultat = functools.reduce(lambda x,y:y@x,chemin)
62
63
64
65
66
67
                if resultat == morphisme:
                    for morph_elem in chemin:
                        yield morph_elem
                    break

            
68
69
70
71

    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
72
73
        Categorie.verifier_coherence(self)
        
74
75
        for morph in self(self.objets,self.objets):
            if len(morph) == 1:
76
                if morph not in self[{morph.source},self.objets]:
77
                    raise Exception("Incoherence CategorieLibre : le morphisme "+str(morph)+" ne sort pas de "+str(morph.source))
78
                if morph not in self[self.objets,{morph.cible}]:
79
80
                    raise Exception("Incoherence CategorieLibre : le morphisme "+str(morph)+" n'entre pas dans "+str(morph.cible))

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
81
    def enumerer_composees_sans_cycle(self, source:Any, cible:Any) -> Generator[Morphisme,None,None]:
82
        """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
83
        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).
84
        """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
85
86
87
88
89
90
91
92
93
94
95
        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]:
96
        """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
97
        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).
98
        """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
99
100
101
102
103
104
105
106
107
108
109
        # 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,)]
110
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
111
112
113
114
    @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é."""
115
        for morph_pred in self[self.objets,{objet}]:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
116
117
118
119
120
121
122
123
            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
124

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
125
    def enumerer_cycles(self, objet:Any, limite_profondeur:int = 10) -> Generator[Morphisme,None,None]:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
126
        """Enumère toutes les compositions de `objet` à `objet`.
127
128
129
130
131
        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.
        """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
132
        cycles = set(self.trouver_cycles_minimaux(objet))
133
134
135
        cycles_a_reduire = copy(cycles)
        cycles_minimaux = copy(cycles)
        cycles |= {self.identite(objet)}
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
136
137
        for cycle in cycles:
            yield cycle
138
139
140
141
        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:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
142
143
144
145
                        new_cycle = cycle_minimal@cycle_a_reduire
                        cycles_a_reduire |= {new_cycle}
                        cycles |= {new_cycle}
                        yield new_cycle
146
147
148
149
150
151
                    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)
    
152
    def enumerer_composees(self, source:Any, cible:Any) -> Generator[Morphisme,None,None]:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
153
        """Génère tous les morphismes composés allant de `source` à `cible`.
154
155
156
157
        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)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
158
        dict_noeuds_cycles = dict() #    {noeud : set(cycles)}
159
        for chemin in chemins_sans_cycles:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
            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()