Categorie.py 10.9 KB
Newer Older
1
2
#!/usr/bin/env python
# -*- coding: utf-8 -*-
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
3
import types
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
4
from collections import defaultdict
5
6
import itertools
from Morphisme import Morphisme
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
7
8
9
10
from config import *
import typing
if GRAPHVIZ_ENABLED:
    from graphviz import Digraph
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
11

12
class Categorie:
13
14
15
    """Classe abstraite qui définit ce qu'est une catégorie.
    Toutes les catégories qui héritent de Categorie doivent surcharger :
        - l'opérateur __call__ tel que si C est une catégorie :
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
16
            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}.
17
18
19
20
21
22
23
24
        - la méthode identite(self,objet) qui renvoie l'identité de l'objet.
        
    On reprend la notation classique C(a,b) pour les flèches de a à b
    et abs(C) = |C| pour les objets de C.
    
    Pour récapituler :
        - abs(C) opérateur pour obtenir les objets
        - C(_,_) opérateur pour obtenir des morphismes
25
26
        - |= opérateur pour ajouter des objets
        - -= opérateur pour supprimer des objets
27
28
29
30
31
32
        
    Pour toutes les catégories on peut :
        - vérifier sa cohérence avec la méthode verifier_coherence
        - visualiser son graphe sous-jacent avec la méthode transformer_graphviz
        - exporter sa loi de composition en csv avec loi_de_composition_to_csv
    """
33
    _id = 0
34
35
    nb_viz = 0  # nombre de graphes graphviz générés    
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
36
    def __init__(self, objets:set = set(), nom:str = None):
37
38
39
        Categorie._id += 1
        self._id = Categorie._id
        self.nom = "Categorie "+str(self._id) if nom == None else nom
40
        self.objets = frozenset()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
41
        self |= objets
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
42
43
44
    
    def __hash__(self) -> int:
        return hash(self.objets)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
45

46
    def __call__(self, sources: any, cibles: any) -> set:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
47
48
49
        """
        Cette méthode est virtuelle pure.
        Les classes filles doivent l'implémenter tel que si C est une catégorie :
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
50
            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}.
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
51
        """
52
53
        raise NotImplementedError("Les categories filles doivent implementer cette methode pour renvoyer les morphismes C(a,b) (fleches de a vers b) et C(a) (identite de a)")
     
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
54
55
56
57
58
59
    def identite(self,objet: any) -> Morphisme:
        """
        Cette méthode est virtuelle pure.
        Les classes filles doivent l'implémenter tel que si C est une catégorie,
        C.identite(objet) renvoie l'identité de l'`objet`.
        """
60
        NotImplementedError("Les categories filles doivent implementer cette methode.")
61

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
62
    def __eq__(self,other: 'Categorie') -> bool:
63
        return issubclass(type(other),Categorie) and self.nom == other.nom and self.objets == other.objets and type(self) == type(other)
64

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
65
    def __hash__(self) -> int:
66
        return hash((self.nom,self.objets))
67

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
68
    def __str__(self) -> str:
69
70
        return self.nom
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
71
72
73
74
75
    def __abs__(self) -> frozenset:
        """
        Renvoie les objets de la catégorie.
        Cette syntaxe suit la convention mathématiques |C| = objets de C.
        """
76
77
        return self.objets
        
78
    def __ior__(self,other:set):
79
80
        """
        Soit C une catégorie.
81
            C |= {a_1,a_2,...} ajoute les objets a_i à la catégorie C.
82
        """
83
        self.objets |= other
84
85
        return self
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
86
    def __isub__(self,other:any):
87
88
        """
        Soit C une catégorie.
89
            C -= {a_1,a_2,...} supprime les objets a_i de la catégorie C.
90
        """
91
        self.objets -= other
92
        return self
93
        
94
95
    def verifier_coherence(self):
        """Vérifie la cohérence de la structure (tous les axiomes des catégories sont vérifiés)."""
96

97
        ## On vérifie que les identités sont neutres
98
        for morphisme in self(self.objets,self.objets):
99
            if not (morphisme@self.identite(morphisme.source) == self.identite(morphisme.cible)@morphisme == morphisme):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
100
101
102
103
                raise Exception("Incoherence Categorie : le morphisme "+str(morphisme)+" est modifie par une identite.\n"\
                +repr(morphisme)+" o "+repr(self.identite(morphisme.source))+" = "+repr(morphisme@self.identite(morphisme.source))+"\n"\
               +repr(self.identite(morphisme.cible))+" o "+repr(morphisme)+" = "+repr(self.identite(morphisme.cible)@morphisme)+"\n"+\
               repr(morphisme))
104
105
        
        ## On vérifie l'associativité
106
        for m1,m2,m3 in itertools.product(sorted(self(self.objets,self.objets)),repeat=3):
107
108
            if m1.source == m2.cible and m2.source == m3.cible:
                if (m1@m2)@m3 != m1@(m2@m3):
109
110
111
                    raise Exception("Incoherence Categorie : associativite pas respectee pour "+str(m1)+", "+str(m2)+", "+str(m3)+\
                    "\n(m1@m2)@m3 = "+str((m1@m2)@m3)+"  m1@(m2@m3) = "+str(m1@(m2@m3))+
                    "\nm1@m2 = "+str(m1@m2)+"  m2@m3 = "+str(m2@m3))#+"\nm2@m1 = "+str(m2@m1)+"  m3@m2 = "+str(m3@m2))
112
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
113
114
    def isomorphismes(self, source:any, cible:any) -> set:
        """Trouve les isomorphismes entre `source` et `cible`.
115
116
        Renvoie un ensemble de couple (f,g) tels que gof = Id1 et fog = Id2.
        """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
117
        return {(f,g) for f in self({source},{cible}) for g in self({cible},{source}) if (f@g).is_identite and (g@f).is_identite}
118
    
119
120
121
122
123
124
    def existe_morphisme(self, source:any, cible:any) -> Morphisme:
        """Renvoie True s'il existe un morphisme de `source` à `cible`, renvoie False sinon.
         Cette fonction peut-être redéfinie pour accélérer les temps de calcul
         (pour ne pas avoir besoin de calculer toutes les flèches de source à cible.)"""
        return len(self(source,cible)) > 0
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
125
    def table_loi_de_composition(self):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
126
        """
127
        Renvoie un dico de dico tel que table[f][g] = f o g, table[f][g] = None si f et g ne sont pas composables.
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
128
        La table contient les compositions triviales f o Id = f, f o g = f o g, f o (g o h) = (f o g) o h etc.
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
129
130
        O(m²)
        """
131
        table = defaultdict(dict)
132
133
134
        for A,B in itertools.product(abs(self), repeat=2):
            for f in self(A,B):
                for g in self(B,abs(self)):
135
                    table[g][f] = g@f
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
136
        return table
137
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
138
139
140
141
142
143
    def loi_de_composition_to_csv(self, destination:str=None, sep: str=','):
        """
        Exporte la loi de composition de la catégorie en csv.
        Si destination == None, alors on le print sinon on l'écrit dans un fichier à la destination.
        `sep` est le séparateur.
        """
144
        fleches = list(self(self.objets,self.objets))
145
146
147
148
149
150
151
        fleches.sort(key = str)
        fleches.sort(key = lambda x:len(str(x)))
        result = sep+sep.join(map(str,fleches))+"\n"
        for f in fleches:
            result += str(f)+sep
            for g in fleches:
                if f.cible == g.source:
152
                    result += str(g@f)+sep
153
154
155
                else:
                    result += "X"+sep
            result = result[:-1]+'\n'
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
156
157
158
159
        if destination != None:
            with open(destination, 'w') as f:
                f.write(result)
        else:
160
            result = result.replace(',','\t,')
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
161
162
            print(result)

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
163
    def transformer_graphviz(self, destination:str=None, afficher_identites:bool=False):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
164
165
        """Permet de visualiser la catégorie avec graphviz"""
        Categorie.nb_viz += 1
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
166
        if destination == None:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
167
            destination = "graphviz/"+type(self).__name__+ str(Categorie.nb_viz)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
168

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
169
        graph = Digraph('categorie')
170
        graph.attr(concentrate="true" if GRAPHVIZ_CONCENTRATE_GRAPHS else "false")
171
        graph.attr(label=self.nom)
172
173
        
        for o in self.objets:
174
            graph.node(str(o))
175
176
177
178
        for fleche in self(self.objets,self.objets):
            if afficher_identites or not fleche.is_identite:
                graph.edge(str(fleche.source), str(fleche.cible), label=str(fleche), weight="1000")
        
179
        graph.render(destination)
180
181
        if CLEAN_GRAPHVIZ_MODEL:
            import os
182
            os.remove(destination)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
183

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
184
185
def test_Categorie():
    from GrapheDeComposition import GC,MGC
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
186
    GC = GC({'A','B','C'})
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
187
    morphismes = [MGC('A','B','f'),MGC('B','C','g')]
188
    GC |= morphismes
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
189
190
191
    GC.transformer_graphviz()
    GC.loi_de_composition_to_csv()

192
class SousCategoriePleine(Categorie):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
193
194
195
196
197
    """
    Sous-catégorie pleine d'une catégorie.
    Une sous-catégorie pleine est constituée d'un sous-ensemble d'objets de la catégorie initiale
    et de tous les morphismes entre ces objets.
    """
198
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
199
200
    def __init__(self, categorie_originelle:Categorie, objets:set):
        """On construit la sous-catégorie pleine de `categorie_originelle` qui contient l'ensemble des `objets`."""
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
201
        Categorie.__init__(self,objets,"Sous-catégorie pleine de "+str(categorie_originelle)+ " ayant pour objets "+str(objets))
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
202
203
        self.categorie_originelle = categorie_originelle
       
204
205
    def __call__(self, sources:set, cibles:set) -> set:
        return self.categorie_originelle(sources,cibles)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
206
207
208
209
210
211
    
    def identite(self,objet:any) -> Morphisme:
        return self.categorie_originelle.identite(objet)
    
def test_SousCategoriePleine():
    from GrapheDeComposition import GC,MGC
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
212
    GC = GC(set("ABCDE"))
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
213
    morphismes = [MGC('A','B','f'),MGC('B','C','g'),MGC('A','D','h'),MGC('D','E','i'),MGC('C','E','j')]
214
    GC |= morphismes
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
215
216
217
218
219
    GC.transformer_graphviz()
    
    sous_cat_pleine = SousCategoriePleine(GC,set("ADE"))
    sous_cat_pleine.transformer_graphviz()
    
220
221
222
223
224
class CategorieDiscrete(Categorie):
    """
    Catégorie discrète : catégorie dont les seuls morphismes sont des identités.
    """
    class Identite(Morphisme):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
225
226
227
228
        """
        Tous les morphismes de la catégorie discrète sont des identités.
        """
        def __init__(self,objet:any):
229
230
            Morphisme.__init__(self,objet,objet,"Id"+str(objet),True)
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
231
232
233
234
        def __matmul__(self,other:'CategorieDiscrete.Identite') -> 'CategorieDiscrete.Identite':
            """
            On peut composer uniquement une identité avec elle même.
            """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
235
236
            if type(other) != CategorieDiscrete.Identite:
                raise Exception("Composition d'un morphisme de type inconnu avec une Identite\n"+repr(self)+'\n'+repr(other))
237
238
239
240
            if self.source != other.source:
                raise Exception("Composition incoherente d'Identites")
            return self
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
241
        def __eq__(self,other:'CategorieDiscrete.Identite') -> bool:
242
243
            return type(other) == CategorieDiscrete.Identite and self.source == other.source
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
244
        def __hash__(self) -> int:
245
246
            return hash(self.source)
        
247
248
    def __call__(self,sources:set,cibles:set) -> set():
        return {CategorieDiscrete.Identite(a) for a in sources for b in cibles if a == b}
249
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
250
    def identite(self,objet:any) -> 'CategorieDiscrete.Identite':
251
        return CategorieDiscrete.Identite(objet)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
252
253

def test_CategorieDiscrete():
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
254
    cat_discrete = CategorieDiscrete(set("ABCDE"))
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
255
256
257
258
    cat_discrete.transformer_graphviz(afficher_identites=True)
    
    
if __name__ == '__main__':
259
260
261
    test_Categorie()
    test_CategorieDiscrete()
    test_SousCategoriePleine()