Foncteur.py 16.8 KB
Newer Older
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
1
2
3
#!/usr/bin/env python
# -*- coding: utf-8 -*-

4
from config import *
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
5
6
7
if GRAPHVIZ_ENABLED:
    from graphviz import Digraph
import itertools
8
import Morphisme
9
import copy
10
import Diagramme
11
from collections import defaultdict
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
12
import Cone, Cocone
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
13

14
class Foncteur(Morphisme.Morphisme):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
15
16
    
    nb_viz = 0
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
17

18
    def __init__(self, categorie_source, categorie_cible, application_objets, application_morphismes, representant = None, is_identite = False):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
19
20
        """application_objets doit être complète, application_morphismes doit spécifier les images de chaque morphisme du squelette.
        L'image des composées est par construction la composée des images"""
21
22
        if representant == None:
            representant = str(categorie_source.representant)+'->'str(categorie_cible.representant)
23
        Morphisme.Morphisme.__init__(self,categorie_source,categorie_cible,representant,is_identite)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
24
25
26
27
28
29
30
31
32
33
        self.cat_source = categorie_source
        self.cat_cible = categorie_cible
        self.app_objets = application_objets
        self.app_morph = application_morphismes
        for obj in self.cat_source.objets:
            self.app_morph[self.cat_source.identites[obj]] = self.cat_cible.identites[self.app_objets[obj]]
        
        
        self.verifier_coherence()
        
34
35
36
37
    def as_diagram(self):
        import Diagramme
        return Diagramme.Diagramme(self.cat_source,self.cat_cible,self.app_objets,self.app_morph)
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
38
    def verifier_coherence(self):
39
40
        # self.transformer_graphviz("graphviz/ErreurFoncteur")
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
41
42
43
44
45
46
47
48
49
50
51
52
        for o in self.cat_source.objets:
            if o not in self.app_objets:
                raise Exception("Incoherence foncteur : l'application d'objet n'est pas une application, "+str(o)+" n'a pas d'image")
        for m in self.cat_source.morphismes:
            if m not in self.app_morph:
                raise Exception("Incoherence foncteur : l'application de morphismes n'est pas une application, "+str(m)+" n'a pas d'image")
       
        ##respect de l'identite
        for objet in self.cat_source.objets:
            if self.app_morph[self.cat_source.identites[objet]] != self.cat_cible.identites[self.app_objets[objet]]:
                raise Exception("Incoherence foncteur : l'image de l'identite de "+str(objet)+" ("+str(self.cat_source.identites[objet])+\
                ") n'est pas l'identite de l'image de l'objet ("+str(self.cat_cible.identites[self.app_objets[objet]])+")")
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
53
54
55
56
57
58
59
60
61
                
        ##Images de deux flèches composables sont composables
        for couple in itertools.combinations(self.app_morph,2):
            if couple[0].cible == couple[1].source:
                if self.app_morph[couple[0]].cible != self.app_morph[couple[1]].source:
                    raise Exception("Incoherence foncteur : deux fleches composables n'ont pas leur image composables : "+str(couple[0])+
                    " composable avec "+str(couple[1])+" mais "+str(self.app_morph[couple[0]])+" pas composable avec "+str(self.app_morph[couple[1]]))
            if couple[1].cible == couple[0].source:
                if self.app_morph[couple[1]].cible != self.app_morph[couple[0]].source:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
62
                    print(self.pretty_print())
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
63
64
                    raise Exception("Incoherence foncteur : deux fleches composables n'ont pas leur image composables : "+str(couple[1])+
                    " composable avec "+str(couple[0])+" mais "+str(self.app_morph[couple[1]])+" pas composable avec "+str(self.app_morph[couple[0]]))
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
65
        
66
67
68
69
70
71
72
    def __call__(self,param):
        if param in self.cat_source.objets:
            return self.app_objets[param]
        if param in self.cat_source.morphismes:
            return self.app_morph[param]
        return self.cat_cible.Composee(*[self.app_morph[morph] for morph in param])
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
73
74
75
76
    def pretty_print(self):
        result = "Categorie source\n ===========\n"+self.cat_source.pretty_print()+"Categorie cible\n ============ \n"+self.cat_cible.pretty_print()
        result += "Application objets\n===========\n"
        for obj in self.app_objets:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
77
            result += str(obj)+" => "+str(self.app_objets[obj])+"\n"
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
78
79
        result += "Application morphismes\n===========\n"
        for morph in self.app_morph:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
80
            result += str(morph)+" => "+str(self.app_morph[morph])+"\n"
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
81
82
        return result
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
83
    def transformer_graphviz(self, destination=None, afficher_identites = False):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
84
85
        """Permet de visualiser la catégorie avec graphviz"""
        Foncteur.nb_viz += 1
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
86
87
        if destination == None:
            destination = "graphviz/foncteur"+str(Foncteur.nb_viz)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
            
        ##on determine s'il y a collision entre les noms des objets et morphismes des deux catégories
        collision = False
        for o in self.cat_source.objets:
            if o in self.cat_cible.objets:
                collision = True
                break
        if not collision:
            cat_cible_representants = list(map(lambda x:str(x.representant),self.cat_cible.morphismes))
            for morph in self.cat_source.morphismes:
                if not morph.is_identite or afficher_identites:
                    if str(morph.representant) in cat_cible_representants:
                        collision = True
                        break
        if collision:
            suffixe1 = "_1"
        else:
            suffixe1 = ""
            
        graph = Digraph('foncteur')
108
        graph.attr(concentrate="true" if GRAPHVIZ_CONCENTRATE_GRAPHS else "false")
109
        graph.attr(label="Foncteur "+self.representant)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
110
111
112
113
114
115
116
117
        with graph.subgraph(name='cluster_0') as cluster:
            cluster.attr(label=self.cat_source.nom)
            nodes = []
            for o in self.cat_source.objets:
                cluster.node(str(o)+suffixe1)
            for morph in self.cat_source.morphismes:
                if not morph.is_identite or afficher_identites:
                    cluster.node(str(morph.representant)+suffixe1,style="invis",shape="point")
118
                    graph.edge(str(morph.source)+suffixe1,str(morph.representant)+suffixe1,label=str(morph.representant)+suffixe1,headclip="False",arrowhead="none")
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
119
120
121
122
123
124
125
126
127
128
129
130
131
132
                    graph.edge(str(morph.representant)+suffixe1,str(morph.cible)+suffixe1,tailclip="false")
        
        if collision:
            suffixe2 = "_2"
        else:
            suffixe2 = ""
        with graph.subgraph(name='cluster_1') as cluster:
            cluster.attr(label=self.cat_cible.nom)
            nodes = []
            for o in self.cat_cible.objets:
                cluster.node(str(o)+suffixe2)
            for morph in self.cat_cible.morphismes:
                if not morph.is_identite or afficher_identites:
                    cluster.node(str(morph.representant)+suffixe2,style="invis",shape="point")
133
                    graph.edge(str(morph.source)+suffixe2,str(morph.representant)+suffixe2,label=str(morph.representant)+suffixe2,headclip="False",arrowhead="none")
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
134
135
                    graph.edge(str(morph.representant)+suffixe2,str(morph.cible)+suffixe2,tailclip="false")
            
136
137
138
139
140
141
142
143
            composees_ajoutees = []
            for source in self.app_morph:
                if not source.is_identite or afficher_identites:
                    if self.app_morph[source] in self.cat_cible.morphismes:
                        graph.edge(str(source.representant)+suffixe1,str(self.app_morph[source].representant)+suffixe2,color="cyan")
                    elif self.app_morph[source] not in composees_ajoutees:
                        cluster.node(str(self.app_morph[source].representant)+suffixe2,style="invis",shape="point")
                        composees_ajoutees += [self.app_morph[source]]
144
                        graph.edge(str(self.app_morph[source].source)+suffixe2,str(self.app_morph[source].representant)+suffixe2,label=str(self.app_morph[source].representant)+suffixe2,headclip="False",arrowhead="none",color="grey77")
145
146
147
148
                        graph.edge(str(self.app_morph[source].representant)+suffixe2,str(self.app_morph[source].cible)+suffixe2,tailclip="false",color="grey77")
                        graph.edge(str(source.representant)+suffixe1,str(self.app_morph[source].representant)+suffixe2,color="cyan")
        
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
149
150
151
152
153
        for source in self.app_objets:
            graph.edge(str(source)+suffixe1,str(self.app_objets[source])+suffixe2,color="blue")
        
        
        graph.render(destination)
154
155
156
157
158
159
160
161
162
163
164
165
166
    
    def categorie_image(self):
        """Renvoie la sous-catégorie image du foncteur."""
        c = copy.copy(self.cat_cible)
        for o in copy.copy(c.objets):
            if o not in self.app_objets.values():
                c.supprimer_objet(o)
        for m in copy.copy(c.morphismes):
            if m not in self.app_morph.values():
                c.supprimer_morphisme(m)
        return c
    
    
167
168
169
170
171
172
173
174
175
176
177
178
179
180
    def enumerer_cones(self,apex):
        """Renvoie une liste de cônes.
        1) On considère les cônes du diagramme trivial où toutes les flèches de la catégorie source ont été retirées.
        2) Pour chaque flèche de la catégorie source, on retire les cônes qui ne commutent pas correctement avec l'image de la flèche.
        On a besoin de faire cette suppression uniquement pour les flèches du squelette et pas pour les composées.
        Preuve : soit F un foncteur de C1 vers C2, soient f : A->B et g : B->C deux morphismes de C1
        soient pA, pB et pC trois jambes d'un cône candidat associées respectivement aux images F(A), F(B) et F(C).
        On suppose que la propriété de commutativité du cône est respectée pour les flèches élémentaires f et g : 
        F(f) o pA = pB et F(g) o pB = pC
        on a alors F(g) o F(f) o pA = pC
        puis F(g o f) o pA = pC           car F est un foncteur
        on en déduit que la propriété du cône est respectée pour la composée de f et g cqfd.
        """  
        import Cone
181
        if apex not in self.cat_cible.objets:
182
            raise Exception("Apex pas dans la categorie indexee.")
183
        composees = [self.cat_cible.enumerer_composees(apex,self(objet)) for objet in self.cat_source.objets]
184
        tous_les_cones = [{self.cat_source.objets[i]:liste[i] for i in range(len(liste))} for liste in itertools.product(*composees)]
185
        for morph in self.cat_source.morphismes:
186
            if not morph.is_identite:
187
                tous_les_cones = [cone for cone in tous_les_cones if self.cat_cible.Composee(cone[morph.source],self(morph)) == cone[morph.cible]]
188
        return [Cone.Cone(self,apex,famille) for famille in tous_les_cones]
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
189
190
191
192
193
194
195
196
197
198
199
        
    def enumerer_cocones(self,nadir):
        """Voir enumerer_cones."""  
        if nadir not in self.cat_cible.objets:
            raise Exception("Nadir pas dans la categorie indexee.")
        composees = [self.cat_cible.enumerer_composees(self(objet),nadir) for objet in self.cat_source.objets]
        tous_les_cocones = [{self.cat_source.objets[i]:liste[i] for i in range(len(liste))} for liste in itertools.product(*composees)]
        for morph in self.cat_source.morphismes:
            if not morph.is_identite:
                tous_les_cocones = [cocone for cocone in tous_les_cocones if self.cat_cible.Composee(self(morph),cocone[morph.cible]) == cocone[morph.source]]
        return [Cocone.Cocone(self,nadir,famille) for famille in tous_les_cocones]
200
   
Guillaume Sabbagh's avatar
Limite    
Guillaume Sabbagh committed
201
202
203
204
205
206
207
208
209
210
211
    def trouver_limite(self):
        """Renvoie la limite du foncteur s'il y en a une, None sinon."""
        cones = [c for o in self.cat_cible.objets for c in self.enumerer_cones(o)]
        for lim_candidate in cones:
            for cone in cones:
                fleches = self.cat_cible.enumerer_composees(cone.apex,lim_candidate.apex)
                for pied in self.cat_source.objets:
                    fleches = [f for f in fleches if cone.jambes[pied] == self.cat_cible.Composee(f,lim_candidate.jambes[pied])]
                if len(fleches) == 1:
                    return lim_candidate
        return None
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
212
213
214
215
216
217
218
219
220
221
222
223
        
    def trouver_colimite(self):
        """Renvoie la colimite du foncteur s'il y en a une, None sinon."""
        cocones = [c for o in self.cat_cible.objets for c in self.enumerer_cocones(o)]
        for colim_candidate in cocones:
            for cocone in cocones:
                fleches = self.cat_cible.enumerer_composees(colim_candidate.nadir,cocone.nadir)
                for pied in self.cat_source.objets:
                    fleches = [f for f in fleches if cocone.jambes[pied] == self.cat_cible.Composee(colim_candidate.jambes[pied],f)]
                if len(fleches) == 1:
                    return colim_candidate
        return None
Guillaume Sabbagh's avatar
Limite    
Guillaume Sabbagh committed
224
    
225
    def categorie_cones(self):
226
227
228
229
        import Categorie
        cat_cones = Categorie.Categorie("Categorie de cones")
        cones = [e for apex in self.cat_cible.objets for e in self.enumerer_cones(apex)]
        cat_cones.ajouter_objets(cones)
230
        app_obj_cones = {obj:[c for c in cones if c.apex==obj] for obj in self.cat_cible.objets} #utile pour faire commuter les diagrammes après
Guillaume Sabbagh's avatar
Limite    
Guillaume Sabbagh committed
231
        app_morph_fleche_cone = dict() #associe à chaque nouvelle flèche dans la cat_cone la flèche de laquelle elle vient
232
233
        for cone1,cone2 in itertools.product(cones,repeat=2):
            fleches_potentielles = [fleche for fleche in self.cat_cible.morph_sortants[cone1.apex] if fleche.cible == cone2.apex]
234
235
236
            # if cone1.apex == cone2.apex and cone1 != cone2:
                # fleches_potentielles += [self.cat_cible.identites[cone1.apex]]
            
237
238
239
            for obj in self.cat_source.objets:
                fleches_potentielles = [fleche for fleche in fleches_potentielles if cone1.jambes[obj] == self.cat_cible.Composee(fleche,cone2.jambes[obj])]
            for fleche in fleches_potentielles:
240
                f = Morphisme.Morphisme(cone1,cone2,fleche.representant)
241
                cat_cones.ajouter_morphisme(f)
Guillaume Sabbagh's avatar
Limite    
Guillaume Sabbagh committed
242
243
244
245
                app_morph_fleche_cone[f] = fleche
                if cone1 == cone2:
                    diag = Diagramme.Triangle(cat_cones,[cone1]*3,[f,f,f])
                    diag.faire_commuter()
246
247
248
        ## on doit faire commuter les diagrammes de la catégorie cible dans la catégorie des cônes
        ## un noeud de la catégorie cible peut être l'apex de plusieurs noeuds (ou aucun) dans la catégorie des cônes
        ## on considère la catégorie cible réduite où tous les noeuds et les morphismes qui n'ont aucun enfant dans la cat des cônes ont été supprimés
Guillaume Sabbagh's avatar
Limite    
Guillaume Sabbagh committed
249
250
        ## Pour tout diagramme D
        ## Soient P, Q, ... des objets de l'image diagramme D, Pi les objets de la catégorie des cônes d'apex P, etc...
251
        ## Pour tout élément (Pk,Ql,...) du produit cartésien {Pi}x{Qi}x...
Guillaume Sabbagh's avatar
Limite    
Guillaume Sabbagh committed
252
        ## 
253
254
255
256
257
258
259
260
261
262
263
264
        cat_cible_reduite = copy.copy(self.cat_cible)
        for obj_a_suppr in [o for o in cat_cible_reduite.objets if o not in app_obj_cones]:
            cat_cible_reduite.supprimer_objet(obj_a_suppr)
        for morph_a_suppr in [m for m in cat_cible_reduite.morphismes if m not in app_morph_fleche_cone]:
            cat_cible_reduite.supprimer_morphisme(morph_a_suppr)
        for prod in itertools.product(*[app_obj_cones[o] for o in cat_cible_reduite.objets]):
            foncteur = Foncteur(cat_cible_reduite,cat_cones,{cat_cible_reduite.objets[i]:prod[i] for i in range(len(prod))},{morph:app_morph_fleche_cone[morph][0] for morph in app_morph_fleche_cone})
        
        # for morph in cat_cones.morphismes:
            # if morph.source == morph.cible:
                # diag = Diagramme.Triangle(cat_cones,[morph.source]*3,[morph]*3)
                # diag.faire_commuter()
265
        return cat_cones
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
266
    
267
268
269
270
271
272
273
274
275
class Composition(Foncteur):
    """Le foncteur composition vu comme un foncteur et non comme un morphisme."""
    def __init__(self,*foncteurs):
        if len(foncteurs) == 0:
            raise Exception("Composition de 0 foncteurs.")
        compo_morph = Morphisme.Composition(*foncteurs)
        s,c = compo_morph.source,compo_morph.cible
        Foncteur.__init__(self,s,c,{e:compo_morph(e) for e in s.objets},{e:compo_morph(e) for e in s.morphismes})
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
276
277
278
279
280
281
def main():
    from Categorie import Categorie
    
    triangle = Categorie()
    triangle.ajouter_objets(['A','B','C'])
    
282
    f1,g1= [Morphisme.Morphisme('A','B','f'),Morphisme.Morphisme('B','C','g')]
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
283
284
    morphismes_triangle = f1,g1
    triangle.ajouter_morphismes(morphismes_triangle)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
285
286
287
288
    
    carre = Categorie()
    carre.ajouter_objets([1,2,3,4])

289
    f,g,h,i = [Morphisme.Morphisme(1,2,'f'),Morphisme.Morphisme(2,4,'g'),Morphisme.Morphisme(1,3,'h'),Morphisme.Morphisme(3,4,'i')]
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
290
291
    morphismes_carre = [f,g,h,i]
    carre.ajouter_morphismes(morphismes_carre)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
292
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
293
294
    app_obj = {'A':1,'B':2,'C':4}
    app_morph = {f1:f,g1:g}
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
295
296
    diagramme = Foncteur(triangle, carre, app_obj, app_morph)
    
297
298
299
300
301
302
    print("F(A) = "+str(diagramme('A')))
    print("F(B) = "+str(diagramme('B')))
    print("F(C) = "+str(diagramme('C')))
    print("F(f1) = "+str(diagramme(f1)))
    print("F(g1of1) = "+str(diagramme(triangle.Composee(f1,g1))))
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
303
    print(diagramme.pretty_print())
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
304
    diagramme.transformer_graphviz()
305
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
306
307
308
if __name__ == '__main__':
    main()