Foncteur.py 11.9 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 functools
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
9
10
from Morphisme import Morphisme
from Categorie import Categorie
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
11

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
12
13
14

class Foncteur(Morphisme):
    """Un `Foncteur` est un morphisme de catégorie."""
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
15
16
    
    nb_viz = 0
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
17

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
18
19
    def __init__(self, categorie_source:Categorie, categorie_cible:Categorie,
    application_objets:dict, application_morphismes:dict, representant:str = None):
20
        """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
21
22
23
        `application_objets` doit être complète,
        `application_morphismes` doit spécifier les images de chaque morphisme générateur (pas besoin de spécifier les images des identités).
        L'image des composées est par construction la composée des images.
24
25
26
27
        """
        is_identite = categorie_cible == categorie_source and\
                      all([obj == application_objets[obj] for obj in application_objets]) and\
                      all([morph == application_morphismes[morph] for morph in application_morphismes])
28
29
        Morphisme.__init__(self,categorie_source,categorie_cible
        ,representant if representant != None else 'Foncteur '+str(Morphisme._id),is_identite)
30
31
32
33
34
35
        self._app_objets = application_objets
        self._app_morph = application_morphismes
        for obj in self.source.objets:
            self._app_morph[self.source.identite(obj)] = self.cible.identite(self._app_objets[obj])
        if TOUJOURS_VERIFIER_COHERENCE:
            self.verifier_coherence()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
36
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
37
38
    def __eq__(self,other:'Foncteur') -> bool:
        if not issubclass(type(other),Foncteur):
39
            return False
40
41
42
        return self.source == other.source and self.cible == other.cible\
        and self._app_objets == other._app_objets and self._app_morph == other._app_morph
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
43
    def __hash__(self) -> int:
44
        return hash((self.source,self.cible,frozenset(self._app_objets.items()),frozenset(self._app_morph.items())))
45
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
46
    def __matmul__(self,other:'Foncteur') -> 'Foncteur':
47
        """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
48
49
            `self` @ `other` <=> `self` o `other`
            On compose les foncteurs en appliquant le premier puis le deuxième.
50
51
52
53
54
55
        """
        if not issubclass(type(other),Foncteur):
            raise Exception("Composition d'un foncteur avec un morphisme de type different : "+str(self)+" o "+str(other))
        return Foncteur(other.source,self.cible,{obj:self(other(obj)) for obj in other.source.objets},\
        {morph:self(other(morph)) for morph in other._app_morph},representant=str(self)+'o'+str(other))
        
56
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
57
58
    def as_diagram(self) -> 'Diagramme':
        '''Renvoie le foncteur en tant que `Diagramme`'''
59
        import Diagramme
60
        return Diagramme.Diagramme(self.source,self.cible,self._app_objets,self._app_morph)
61
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
62
    def verifier_coherence(self):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
63
        '''Vérifie la cohérence du foncteur.'''
64
65
        for obj in self._app_objets:
            if obj in self._app_morph:
66
                raise Exception("Incoherence foncteur : "+str(obj)+" est a la fois un objet et un morphisme de la categorie source")
67
        
68
69
        for o in self.source.objets:
            if o not in self._app_objets:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
70
                raise Exception("Incoherence foncteur : l'application d'objet n'est pas une application, "+str(o)+" n'a pas d'image")
71

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
72
        ##respect de l'identite
73
74
75
76
        for objet in self.source.objets:
            if self._app_morph[self.source.identite(objet)] != self.cible.identite(self._app_objets[objet]):
                raise Exception("Incoherence foncteur : l'image de l'identite de "+str(objet)+" ("+str(self.source.identite(objet))+\
                ") n'est pas l'identite de l'image de l'objet ("+str(self.cible.identite(self._app_objets[objet]))+")")
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
77
78
                
        ##Images de deux flèches composables sont composables
79
80
81
82
83
84
        for m1,m2 in itertools.product(self._app_morph,repeat=2):
            if m1.cible == m2.source:
                if self._app_morph[m1].cible != self._app_morph[m2].source:
                    raise Exception("Incoherence foncteur : deux fleches composables n'ont pas leur image composables : "+str(m1)+
                    " composable avec "+str(m2)+" mais "+str(self._app_morph[m1])+" pas composable avec "+str(self._app_morph[m2]))
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
85
86
    def __call__(self,param:any)->any:
        '''Applique le foncteur à un objet ou un morphisme de la catégorie source.'''
87
88
89
90
91
        if param in self._app_objets:
            return self._app_objets[param]
        if param in self._app_morph:
            return self._app_morph[param]
        return functools.reduce(lambda x,y:x@y,[self._app_morph[morph] for morph in param])
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
92
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
93
    def transformer_graphviz(self, destination:any=None, afficher_identites:bool = False):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
94
        Foncteur.nb_viz += 1
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
95
96
        if destination == None:
            destination = "graphviz/foncteur"+str(Foncteur.nb_viz)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
97
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
98
99
        suffixe1_objet = "_1"
        suffixe1_morph = "-1"
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
100
101
            
        graph = Digraph('foncteur')
102
        graph.attr(concentrate="true" if GRAPHVIZ_CONCENTRATE_GRAPHS else "false")
103
        graph.attr(label="Foncteur "+self.representant)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
104
        with graph.subgraph(name='cluster_0') as cluster:
105
            cluster.attr(label=self.source.nom)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
106
            nodes = []
107
            for o in self.source.objets:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
108
109
                cluster.node(str(o)+suffixe1_objet)
            
110
            for morph in self.source(self.source.objets,self.source.objets):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
111
                if not morph.is_identite or afficher_identites:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
112
                    couleur = 'black' if len(morph) == 1 else 'grey70'
113
                    cluster.node(str(morph)+suffixe1_morph,style="invis",shape="point")
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
114
115
                    graph.edge(str(morph.source)+suffixe1_objet,str(morph)+suffixe1_morph,color=couleur,label=str(morph)+suffixe1_morph,headclip="False",arrowhead="none")
                    graph.edge(str(morph)+suffixe1_morph,str(morph.cible)+suffixe1_objet,color=couleur,tailclip="false")
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
116
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
117
118
119
        suffixe2_objet = "_2"
        suffixe2_morph = "-2"

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
120
        with graph.subgraph(name='cluster_1') as cluster:
121
            cluster.attr(label=self.cible.nom)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
122
            nodes = []
123
            for o in self.cible.objets:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
124
                cluster.node(str(o)+suffixe2_objet)
125
            for morph in self.cible(self.cible.objets,self.cible.objets):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
126
                if not morph.is_identite or afficher_identites:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
127
                    couleur = 'black' if len(morph) == 1 else 'grey70'
128
                    cluster.node(str(morph)+suffixe2_morph,style="invis",shape="point")
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
129
130
                    graph.edge(str(morph.source)+suffixe2_objet,str(morph)+suffixe2_morph,color=couleur,label=str(morph)+suffixe2_morph,headclip="False",arrowhead="none")
                    graph.edge(str(morph)+suffixe2_morph,str(morph.cible)+suffixe2_objet,color=couleur,tailclip="false")
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
131
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
132
133
134
        for source in self._app_morph:
            if not source.is_identite or afficher_identites:
                graph.edge(str(source)+suffixe1_morph,str(self(source))+suffixe2_morph,color="cyan")
135
136

        for source in self._app_objets:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
137
            graph.edge(str(source)+suffixe1_objet,str(self(source))+suffixe2_objet,color="blue")
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
138
139
        
        graph.render(destination)
140
141
        if CLEAN_GRAPHVIZ_MODEL:
            import os
142
            os.remove(destination) 
143
    
144
145
146
147
    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.
148
        On a besoin de faire cette suppression uniquement pour les flèches du graphe de composition et pas pour les composées.
149
150
151
152
153
154
155
156
157
        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
158
        if apex not in self.cat_cible.objets:
159
            raise Exception("Apex pas dans la categorie indexee.")
160
        composees = [self.cat_cible.enumerer_composees(apex,self(objet)) for objet in self.cat_source.objets]
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
161
        tous_les_cones = [dict(zip(self.cat_source.objets,liste)) for liste in itertools.product(*composees)]
162
        for morph in self.cat_source.morphismes:
163
            if not morph.is_identite:
164
                tous_les_cones = [cone for cone in tous_les_cones if self.cat_cible.Composee(cone[morph.source],self(morph)) == cone[morph.cible]]
165
        return [Cone.Cone(self,apex,famille) for famille in tous_les_cones]
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
166
167
168
        
    def enumerer_cocones(self,nadir):
        """Voir enumerer_cones."""  
169
        import Cocone
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
170
171
172
        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]
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
173
        tous_les_cocones = [dict(zip(self.cat_source.objets,liste)) for liste in itertools.product(*composees)]
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
174
175
176
177
        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]
178
   
Guillaume Sabbagh's avatar
Limite    
Guillaume Sabbagh committed
179
180
181
182
183
184
185
186
187
188
189
    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
190
191
192
193
194
195
196
197
198
199
200
201
        
    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
202
203
204
205
206
        
def test_Foncteur():
    from GrapheDeComposition import GC,MGC
    triangle = GC()
    triangle+= {'A','B','C'}
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
207
    
208
209
    f1,g1= [MGC('A','B','f'),MGC('B','C','g')]
    triangle += {f1,g1}
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
210
    
211
212
    carre = GC()
    carre += {1,2,3,4}
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
213

214
215
216
217
218
219
220
221
222
    f,g,h,i = [MGC(1,2,'f'),MGC(2,4,'g'),MGC(1,3,'h'),MGC(3,4,'i')]
    morphismes_carre = {f,g,h,i}
    carre += morphismes_carre
    
    pentagone = GC()
    pentagone += set("VWXYZ")
    a,b,c,d,e = [MGC('X','Y','a'),MGC('Y','Z','b'),MGC('W','V','c'),MGC('W','X','d'),MGC('V','Z','e')]
    pentagone += {a,b,c,d,e}
    pentagone.transformer_graphviz()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
223
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
224
225
    app_obj = {'A':1,'B':2,'C':4}
    app_morph = {f1:f,g1:g}
226
227
    fonct1 = Foncteur(triangle, carre, app_obj, app_morph)
    fonct1.transformer_graphviz()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
228
    
229
230
231
232
    app_obj = {1:'W',2:'V',3:'Y',4:'Z'}
    app_morph = {f:c,g:e,h:a@d,i:b}
    fonct2 = Foncteur(carre,pentagone,app_obj,app_morph)
    fonct2.transformer_graphviz()
233
    
234
    (fonct2@fonct1).transformer_graphviz()
235
    
236

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
237
if __name__ == '__main__':
238
    test_Foncteur()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
239