Categorie.py 10 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
33
34
        
    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
    """
    nb_viz = 0  # nombre de graphes graphviz générés    
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
35
    def __init__(self, objets:set = set(), nom:str = "Catégorie"):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
36
        self.nom = nom
37
        self.objets = frozenset()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
38
        self |= objets
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
39
40
41
    
    def __hash__(self) -> int:
        return hash(self.objets)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
42

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
43
44
45
46
    def __call__(self, source: any, cible: any) -> set:
        """
        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
47
            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
48
        """
49
50
        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
51
52
53
54
55
56
    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`.
        """
57
        NotImplementedError("Les categories filles doivent implementer cette methode.")
58

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

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
62
    def __hash__(self) -> int:
63
        return hash((self.nom,self.objets))
64

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

94
        ## On vérifie que les identités sont neutres
95
        for morphisme in self(self.objets,self.objets):
96
97
98
99
            if not (morphisme@self.identite(morphisme.source) == self.identite(morphisme.cible)@morphisme == morphisme):
                raise Exception("Incoherence Categorie : le morphisme "+str(morphisme)+" est modifie par une identite.")
        
        ## On vérifie l'associativité
100
        for m1,m2,m3 in itertools.product(sorted(self(self.objets,self.objets)),repeat=3):
101
102
            if m1.source == m2.cible and m2.source == m3.cible:
                if (m1@m2)@m3 != m1@(m2@m3):
103
104
105
                    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))
106
107
108
109
110
111
112
    
    def est_isomorphe_a(self, objet1:any, objet2:any) -> set:
        """Trouve les isomorphismes entre `objet1` et `objet2`.
        Renvoie un ensemble de couple (f,g) tels que gof = Id1 et fog = Id2.
        """
        return {(f,g) for f in self({objet1},{objet2}) for g in self({objet2},{objet1}) if (f@g).is_identite and (g@f).is_identite}
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
113
    def table_loi_de_composition(self):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
114
        """
115
        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
116
        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
117
118
        O(m²)
        """
119
        table = defaultdict(dict)
120
121
122
        for A,B in itertools.product(abs(self), repeat=2):
            for f in self(A,B):
                for g in self(B,abs(self)):
123
                    table[g][f] = g@f
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
124
        return table
125
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
126
127
128
129
130
131
    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.
        """
132
        fleches = list(self(self.objets,self.objets))
133
134
135
136
137
138
139
        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:
140
                    result += str(g@f)+sep
141
142
143
                else:
                    result += "X"+sep
            result = result[:-1]+'\n'
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
144
145
146
147
148
149
        if destination != None:
            with open(destination, 'w') as f:
                f.write(result)
        else:
            print(result)

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
150
    def transformer_graphviz(self, destination:str=None, afficher_identites:bool=False):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
151
152
        """Permet de visualiser la catégorie avec graphviz"""
        Categorie.nb_viz += 1
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
153
        if destination == None:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
154
            destination = "graphviz/categorie" + str(Categorie.nb_viz)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
155

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
156
        graph = Digraph('categorie')
157
        graph.attr(concentrate="true" if GRAPHVIZ_CONCENTRATE_GRAPHS else "false")
158
        graph.attr(label=self.nom)
159
160
        
        for o in self.objets:
161
            graph.node(str(o))
162
163
164
165
        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")
        
166
        graph.render(destination)
167
168
        if CLEAN_GRAPHVIZ_MODEL:
            import os
169
            os.remove(destination)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
170

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
171
172
def test_Categorie():
    from GrapheDeComposition import GC,MGC
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
173
    GC = GC({'A','B','C'})
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
174
    morphismes = [MGC('A','B','f'),MGC('B','C','g')]
175
    GC |= morphismes
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
176
177
178
    GC.transformer_graphviz()
    GC.loi_de_composition_to_csv()

179
class SousCategoriePleine(Categorie):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
180
181
182
183
184
    """
    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.
    """
185
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
186
187
    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
188
        Categorie.__init__(self,objets,"Sous-catégorie pleine de "+str(categorie_originelle)+ " ayant pour objets "+str(objets))
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
189
190
        self.categorie_originelle = categorie_originelle
       
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
191
    def __call__(self, source:set, cible:set) -> set:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
192
193
194
195
196
197
198
        return self.categorie_originelle(source,cible)
    
    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
199
    GC = GC(set("ABCDE"))
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
200
    morphismes = [MGC('A','B','f'),MGC('B','C','g'),MGC('A','D','h'),MGC('D','E','i'),MGC('C','E','j')]
201
    GC |= morphismes
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
202
203
204
205
206
    GC.transformer_graphviz()
    
    sous_cat_pleine = SousCategoriePleine(GC,set("ADE"))
    sous_cat_pleine.transformer_graphviz()
    
207
208
209
210
211
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
212
213
214
215
        """
        Tous les morphismes de la catégorie discrète sont des identités.
        """
        def __init__(self,objet:any):
216
217
            Morphisme.__init__(self,objet,objet,"Id"+str(objet),True)
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
218
219
220
221
        def __matmul__(self,other:'CategorieDiscrete.Identite') -> 'CategorieDiscrete.Identite':
            """
            On peut composer uniquement une identité avec elle même.
            """
222
223
224
225
226
227
            if type(other) != Identite:
                raise Exception("Composition d'un morphisme de type inconnu avec une Identite")
            if self.source != other.source:
                raise Exception("Composition incoherente d'Identites")
            return self
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
228
        def __eq__(self,other:'CategorieDiscrete.Identite') -> bool:
229
230
            return type(other) == CategorieDiscrete.Identite and self.source == other.source
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
231
        def __hash__(self) -> int:
232
233
            return hash(self.source)
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
234
    def __call__(self,source:set,cible:set) -> set():
235
236
        return {CategorieDiscrete.Identite(a) for a in source for b in cible if a == b}
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
237
    def identite(self,objet:any) -> 'CategorieDiscrete.Identite':
238
        return CategorieDiscrete.Identite(objet)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
239
240

def test_CategorieDiscrete():
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
241
    cat_discrete = CategorieDiscrete(set("ABCDE"))
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
242
243
244
245
    cat_discrete.transformer_graphviz(afficher_identites=True)
    
    
if __name__ == '__main__':
246
247
248
    test_Categorie()
    test_CategorieDiscrete()
    test_SousCategoriePleine()