Categorie.py 28.2 KB
Newer Older
1
2
3
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

class Categorie:
14
15
16
17
    """Catégorie libre par défaut, on peut spécifier les contraintes
    de composition en ajoutant des diagrammes commutatifs.
    Les compositions de morphismes ne sont pas ajoutées par défaut,
    elles existent en potentialité."""
18
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
19
    nb_viz = 0 #nombre de graphes graphviz générés
20
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
21
22
    def __init__(self, nom = "CategorieFinie"):
        self.nom = nom
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
23
        self.objets = [] #les objets doivent être hashable
24
        self.morphismes = [] #liste des morphismes de base (pas les composes)
25
        self.identites = dict() # à chaque objet on associe son morphisme identité, ce dernier doit aussi être présent dans morphismes
26
27
        self.morph_sortants = defaultdict(list) #Liste des morphismes sortant non triviaux d'un objet
        self.morph_entrants = defaultdict(list) 
28
        self.diagrammes = [] #liste des diagrammes commutatifs
29
30
31
        class Composee(Composition):
            """La loi de composition est inclus dans la construction de la composee : 
            en construisant la composee de deux morphismes identifiés, le résultat sera le même."""
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
32
33
            loi_de_composition = {} #dico Composition:Composition
            ## /!\ La loi de composition doit être un graphe acyclique simplificateur /!\
34
            
35
            def verifier_coherence(noeuds_visites = tuple()):
36
37
                for noeud in Composee.loi_de_composition:
                    if noeud not in noeuds_visites:
38
39
                        if not noeud.is_identite and not Composee.loi_de_composition[noeud].is_identite and len(noeud.composee) == 1 and len(Composee.loi_de_composition[noeud]) == 1:
                            raise Exception("Loi de composition associe deux fleches elementaires")
40
41
42
                        if len(noeud) < len(Composee.loi_de_composition[noeud]):
                            raise Exception("Loi de composition pas simplificatrice (image d'une composition est une composition de taille superieure) : "+
                            str(Composition(*noeud))+" -> "+str(Composee.loi_de_composition[noeud]))
43
                        noeuds_visites += tuple([noeud])
44
                        if Composee.loi_de_composition[noeud] in noeuds_visites:
45
46
47
48
                            raise Exception("Loi de composition n'est pas acyclique : "+str(Composition(*noeud))+" -> "+str(Composee.loi_de_composition[noeud]))
                        Composee.verifier_coherence(noeuds_visites)
                
            
49
            def _simplifier_composee(morphismes):
50
                morphismes = [m for compo in morphismes for m in compo]
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
51
                for i in range(len(morphismes),1,-1):
52
53
                    for j in range(0,len(morphismes)-i+1):
                        sous_composee = Composition(*morphismes[j:j+i])
54
55
                        if sous_composee in self.Composee.loi_de_composition:
                            morphismes = morphismes[0:j]+[self.Composee.loi_de_composition[sous_composee]]+morphismes[j+i:]
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
                            return Composee._simplifier_composee(morphismes)
                return morphismes
            
            def __new__(cls,*morphismes):
                morphismes = Composee._simplifier_composee(morphismes)
                composition = Composition(*morphismes)
                if type(composition) is Composition: #si la composition n'est pas simplifiée en morphisme
                    instance = super(Composee, cls).__new__(cls,*morphismes)
                    return instance
                else: #si la composition est simplifiée en morphisme unitaire
                    return composition
                    
            def __init__(self,*morphismes):
                morphismes = Composee._simplifier_composee(morphismes)
                Composition.__init__(self,*morphismes)

        self.Composee = Composee
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
73
    
74
75
76
77
78
    def __copy__(self):
        newone = type(self)(self.nom)
        newone.objets = copy.copy(self.objets)
        newone.morphismes = copy.copy(self.morphismes)
        newone.identites = copy.copy(self.identites)
79
80
81
82
83
84
        newone.morph_sortants = defaultdict(list)
        newone.morph_entrants = defaultdict(list)
        for cle in self.morph_sortants:
            newone.morph_sortants[cle] = copy.copy(self.morph_sortants[cle])
        for cle in self.morph_entrants:
            newone.morph_entrants[cle] = copy.copy(self.morph_entrants[cle])
85
86
87
        newone.diagrammes = copy.copy(self.diagrammes)
        return newone
        
Guillaume Sabbagh's avatar
Limite    
Guillaume Sabbagh committed
88
89
90
    def fleches_elem(self,source,cible):
        """Renvoie la liste de flèches élémentaires de source à cible."""
        return [morph for morph in self.morph_sortants[source] if morph.cible == cible]
91
    
92
93
94
95
96
    def verifier_coherence(self):
        """Vérifie la cohérence de la structure (tous les axiomes des catégories sont vérifiés)."""
        m = self.morphismes
        if len(self.objets) == 0:
            ## S'il n'y a aucun objet, on vérifie que tout le reste est vide aussi
97
            assert(len(m) == len(self.morph_sortants) == len(self.morph_entrants) == len(self.diagrammes) == len(self.Composee.loi_de_composition) == 0)
98
99
100
        else:
            ## On vérifie l'existence de l'identité pour tous les objets (O(n))
            for o in self.objets:
101
                if o not in self.identites:
102
103
                    raise Exception("Pas de morphisme identite pour l'objet "+str(o))
                    
104
105
            ## L'associativité est vérifiée par construction de la composee
            ## On vérifie que les morphismes identifiés ont les mêmes sources et cibles
106
107
            for morph in self.Composee.loi_de_composition:
                if morph.source != self.Composee.loi_de_composition[morph].source:
108
                    raise Exception("Morphismes identifies avec des sources differentes : "+''.join(map(str,m))+","+str(self.Composee.loi_de_composition[m]))
109
                if morph.cible != self.Composee.loi_de_composition[morph].cible:
110
                    raise Exception("Morphismes identifies avec des cibles differentes : "+''.join(map(str,m))+","+str(self.Composee.loi_de_composition[m]))
111
112
113
114
115
            
            ## L'axiome d'identité est vérifié par construction de la composee
            ## On vérifie qu'il n'y a pas trop d'identités
            ident = [morph for morph in m if morph.is_identite]
            if len(ident) > len(self.objets):
116
                raise Exception("Trop d'identites : "+','.join(map(str,ident)))
117

118
119
120
121
122
123
            ## On vérifie que la liste morph_sortants est correcte
            for obj in self.objets:
                for morph in m:
                    if not morph.is_identite:
                        if morph.source == obj:
                            if morph not in self.morph_sortants[obj]:
124
125
126
                                #print(' , '.join(map(str,self.morphismes)))
                                print(' , '.join(map(str,m)))
                                print(morph)
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
                                raise Exception("Erreur morph_sortants : morphisme manquant "+str(morph))
                        if morph.source != obj:
                            if morph in self.morph_sortants[obj]:
                                raise Exception("Erreur morph_sortants : morphisme en trop "+str(morph))
                            
            ## On vérifie que la liste morph_entrants est correcte
            for obj in self.objets:
                for morph in m:
                    if not morph.is_identite:
                        if morph.cible == obj:
                            if morph not in self.morph_entrants[obj]:
                                raise Exception("Erreur morph_entrants : morphisme manquant "+str(morph))
                        if morph.cible != obj:
                            if morph in self.morph_entrants[obj]:
                                raise Exception("Erreur morph_entrants : morphisme en trop "+str(morph))
142
143
                                
            self.Composee.verifier_coherence([])
144
145
                            
    def ajouter_objet(self, objet):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
146
147
148
149
150
        if objet in self.objets:
            raise Exception("Objet deja present dans la categorie : tentative d'ajout de "+str(objet)+" echoue")
        
        
        ##on ajoute l'objet et l'identité associée
151
        self.objets += [objet]
152
        self.identites[objet] = Morphisme(objet,objet, "Id"+str(objet),True)
153
        self.morphismes += [self.identites[objet]]
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
154
        
155
156
157
        if TOUJOURS_VERIFIER_COHERENCE:
            self.verifier_coherence()
    
158
    def ajouter_objets(self, objets):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
159
        for i in range(len(objets)):
160
            self.ajouter_objet(objets[i])
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
            
    def supprimer_objet(self,objet):
        for morph in self.morph_entrants[objet]:
            self.supprimer_morphisme(morph)
        for morph in self.morph_sortants[objet]:
            self.supprimer_morphisme(morph)
        self.supprimer_morphisme(self.identites[objet])
        self.objets.remove(objet)
        if TOUJOURS_VERIFIER_COHERENCE:
            self.verifier_coherence()
            
    def supprimer_morphisme(self,morphisme):
        for elem_a_del in [e for e in self.Composee.loi_de_composition if morphisme in self.Composee.loi_de_composition[e]]:
            del self.Composee.loi_de_composition[elem_a_del]
        if morphisme in self.Composee.loi_de_composition:
            del self.Composee.loi_de_composition[morphisme]
        
        self.morphismes.remove(morphisme)
        if not morphisme.is_identite:
            self.morph_entrants[morphisme.cible].remove(morphisme)
            self.morph_sortants[morphisme.source].remove(morphisme)
            while len(self.diagrammes) > 0:
                for i in range(len(self.diagrammes)):
                    d = self.diagrammes[i]
                    if morphisme in [e for compo in d.app_morph.values() for e in compo]:
                        self.diagrammes.pop(i)
                        nouveau_sketch = Categorie()
                        nouveau_sketch.ajouter_objets(d.cat_source.objets)
                        nouveau_sketch.ajouter_morphismes([morph for morph in d.cat_source.morphismes if morphisme not in d.app_morph[morph] and not morph.is_identite])
                        nouveau_diagramme = Diagramme.Diagramme(nouveau_sketch,self,d.app_objets,{cle:d.app_morph[cle] for cle in nouveau_sketch.morphismes if not cle.is_identite})
                        nouveau_diagramme.faire_commuter()
                        break
                else:
                    break
        if TOUJOURS_VERIFIER_COHERENCE:
            self.verifier_coherence()
                
198
199
200
201
    def ajouter_morphisme(self, morphisme):
        self.morphismes += [morphisme]
        self.morph_entrants[morphisme.cible] += [morphisme]
        self.morph_sortants[morphisme.source] += [morphisme]
202
        self.verifier_coherence()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
203
    
204
205
206
    def ajouter_morphismes(self, morphismes):
        for m in morphismes:
            self.ajouter_morphisme(m)
207

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
208
    def enumerer_composees_sans_cycle(self,source,cible, noeuds_deja_visites = tuple()):
209
210
        """Renvoie tous les morphismes composés allant de source à cible ne contenant aucun cycle (on ne passe jamais deux fois par le même noeud).
        Si la loi de composition est mal définie pour un cycle de morphismes, cette fonction ne boucle pas à l'infini."""
211
        if source == cible:
212
213
            return [self.identites[source]]
        if source not in noeuds_deja_visites:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
214
            noeuds_deja_visites = noeuds_deja_visites+(source,)
215
216
217
218
219
220
221
222
            composees_resultat = []
            for morph in self.morph_sortants[source]:
                for composition_candidate in self.enumerer_composees_sans_cycle(morph.cible,cible,noeuds_deja_visites):
                    composee = self.Composee(morph,composition_candidate)
                    if composee not in composees_resultat:
                        composees_resultat += [composee]
            return composees_resultat
        return []
223
224
225
226
        
    def trouver_cycles_elementaires(self,objet):
        """Renvoie tous les cycles de morphismes élémentaires (qui ne contiennent aucun cycle) 
        de objet à objet qui n'est pas l'identité."""
227
228
229
        cycles = []
        for morph_pred in self.morph_entrants[objet]:
            pred = morph_pred.source
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
230
            cycles_tronques = self.enumerer_composees_sans_cycle(objet,pred)
231
232
233
234
            for cycle_tronque in cycles_tronques:
                cycle = self.Composee(cycle_tronque,morph_pred)
                if cycle not in cycles:
                    cycles += [cycle]
235
236
237
238
        return cycles
        
    
    def enumerer_cycles(self,objet):
239
        """Enumère toutes les compositions de objet à objet qui ne sont pas l'identité.
240
241
242
243
244
        Si f et g sont des cycles élémentaires, 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 avec un nombre de morphismes strictement inférieurs.
        Si f ne se réduit pas, on regarde ff et fg, puis si ceux là non plus fff, ffg, fgf,fgg etc récursivement.
        """
        cycles = self.trouver_cycles_elementaires(objet)
245
        
246
        def trouver_reductions(mot=[]):
247
            if DEBUG_LOI_DE_COMPOSITION:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
248
                print(' , '.join(map(str,mot)))
249
                print(list(map(lambda x:cycles.index(x),mot)))
250
            if len(mot) > 0:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
251
                # composition = Composition(*mot)
252
                composee = self.Composee(*mot)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
253
                if len(composee) < len(mot) or composee.is_identite: #l'identité est une composition de 0 morphisme
254
255
256
257
258
259
260
261
262
                    return [composee]
                resultat = [composee]
            else:
                resultat = []
            for c in cycles:
                reductions = trouver_reductions(mot+[c])
                resultat += [e for e in reductions if e not in resultat]
            return resultat
        
263
        return [morph for morph in trouver_reductions() if not morph.is_identite]
264
        
265
266
267
268
269
270
    def enumerer_composees(self, source,cible):
        """Renvoie tous les morphismes composés allant de source à cible.
        Si la loi de composition est mal définie pour un cycle de morphismes, cette fonction boucle à l'infini.
        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."""
271
        chemins_sans_cycles = self.enumerer_composees_sans_cycle(source,cible)
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
        noeuds = list(set([e for c in chemins_sans_cycles for e in c.objets_traverses()]))
        cycles = list(map(lambda x:self.enumerer_cycles(x),noeuds))
        tous_les_chemins = []
            
        for c in chemins_sans_cycles:
            noeuds_impliques = []
            cycles_impliques = []
            for noeud in c.objets_traverses():
                if len(cycles[noeuds.index(noeud)]) > 0:
                    noeuds_impliques += [noeud]
                    cycles_impliques += [[self.identites[noeud]]+cycles[noeuds.index(noeud)]] #on rajoute une identité pour la possibilité de pas rajouter le cycle
            if len(cycles_impliques) > 0:
                for prod in itertools.product(*cycles_impliques):
                    morphismes = []
                    k = 0
                    for i in range(len(noeuds_impliques)):
                        noeud = noeuds_impliques[i]
289
290
                        while k < len(c) and c[k].source != noeud:
                            morphismes += [c[k]]
291
292
                            k+=1
                        morphismes += [prod[i]]
293
                    while k < len(c):
294
                        morphismes += [c[k]]
295
                        k+=1
296
297
298
299
300
301
302
                    comp = self.Composee(*morphismes)
                    if comp not in tous_les_chemins:
                        tous_les_chemins += [comp]
            else:
                tous_les_chemins += [c] 
        return tous_les_chemins

303
304
305
    def enumerer_composees_sortantes(self, source):
        return [morph for cible in self.objets for morph in self.enumerer_composees(source,cible)]
        
306
307
308
309
310
311
    def enumerer_toutes_composees(self):
        """Renvoie un dictionnaire de la forme (source,cible):[composees]."""
        result = dict()
        cycles_noeuds = {noeud:[self.identites[noeud]]+self.enumerer_cycles(noeud) for noeud in self.objets}
        for couple in itertools.product(self.objets,repeat=2):
            source,cible = couple
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
312
            chemins_sans_cycles = self.enumerer_composees_sans_cycle(source,cible)
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
            noeuds = list(set([e for c in chemins_sans_cycles for e in c.objets_traverses()]))
            tous_les_chemins = []
                
            for c in chemins_sans_cycles:
                noeuds_impliques = []
                cycles_impliques = []
                for noeud in c.objets_traverses():
                    if len(cycles_noeuds[noeud]) > 0:
                        noeuds_impliques += [noeud]
                        cycles_impliques += [cycles_noeuds[noeud]] #on rajoute une identité pour la possibilité de pas rajouter le cycle
                if len(cycles_impliques) > 0:
                    for prod in itertools.product(*cycles_impliques):
                        morphismes = []
                        k = 0
                        for i in range(len(noeuds_impliques)):
                            noeud = noeuds_impliques[i]
329
330
                            while k < len(c) and c[k].source != noeud:
                                morphismes += [c[k]]
331
332
                                k+=1
                            morphismes += [prod[i]]
333
                        while k < len(c):
334
                            morphismes += [c[k]]
335
336
337
338
339
340
341
342
343
                            k+=1
                        comp = self.Composee(*morphismes)
                        if comp not in tous_les_chemins:
                            tous_les_chemins += [comp]
                else:
                    tous_les_chemins += [c] 
            result[couple] = tous_les_chemins
        return result 
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
    def est_cyclique(self):
        """Renvoie un booléen qui indique si le graphe sous-jacent est cyclique"""
        noeuds_suspects = []
        noeuds_safe = []
        def marquer_descendants(noeud):
            """Renvoie true si cycle trouvé, false sinon.
            Ajoute le noeud aux noeuds suspects et étend la liste des noeuds suspects en propageant aux descendants."""
            nonlocal noeuds_suspects
            nonlocal noeuds_safe
            if noeud in noeuds_suspects:
                return True
            if noeud in noeuds_safe:
                return False
            noeuds_suspects += [noeud]
            for morph in self.morph_sortants[noeud]:
                succ = morph.cible
                if marquer_descendants(succ):
                    return True
            noeuds_suspects.remove(noeud)
            noeuds_safe += [noeud]
        
        noeuds_non_visites = [e for e in self.objets if e not in noeuds_safe]
        while len(noeuds_non_visites) > 0:
            noeud = noeuds_non_visites[0]
            if marquer_descendants(noeud):
                return True
            noeuds_safe += noeuds_suspects
            noeuds_suspects = []
            noeuds_non_visites = [e for e in self.objets if e not in noeuds_safe]
        
        return False
        
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
    def nb_composees_borne_sup(self,source,cible,noeuds_deja_visites=tuple()):
        """Renvoie une borne sup du nombre de composées entre source et cible.
        Dans le cas acyclique, borne_inf = borne_sup.
        Boucle à l'infini si la loi de composition est mal définie."""
        if source in noeuds_deja_visites:
            return 0
        noeuds_deja_visites += tuple([source])
        if source == cible:
            return 1+len(self.enumerer_cycles(source))
        if len(self.morph_sortants[source]) > 0:
            result = sum([self.nb_composees_borne_sup(morph.cible,cible,noeuds_deja_visites) for morph in self.morph_sortants[source]])
            for c in self.enumerer_cycles(source):
                noeuds_deja_visites2 = noeuds_deja_visites+tuple([m.cible for m in c])
                result += sum([self.nb_composees_borne_sup(morph.cible,cible,noeuds_deja_visites2) for morph in self.morph_sortants[source]])
            return result
        return 0
        
    def nb_composees_borne_inf(self,source,cible,noeuds_deja_visites=tuple()):
        """Renvoie une borne inf du nombre de composées entre source et cible.
        Dans le cas acyclique, borne_inf = borne_sup."""
        if source in noeuds_deja_visites:
            return 0
        noeuds_deja_visites += tuple([source])
        if source == cible:
            return 1
        if len(self.morph_sortants[source]) > 0:
            return sum([self.nb_composees_borne_inf(morph.cible,cible,noeuds_deja_visites) for morph in self.morph_sortants[source]])
        return 0
404
405
    
    def compter_toutes_composees(self):
406
407
408
409
        """Renvoie un intervalle qui contient le nombre de composées de toute la catégorie.
        Dans le cas acyclique, borne_inf = borne_sup.
        Boucle à l'infini si la loi de composition est mal définie."""
        return (sum([self.nb_composees_borne_inf(a,b) for a,b in itertools.product(self.objets,repeat=2)]),sum([self.nb_composees_borne_sup(a,b) for a,b in itertools.product(self.objets,repeat=2)]))
410
        
411
412
    def pretty_print(self):
        result = "Objets de la categorie : \n"+', '.join(map(str,self.objets))+"\n\nMorphismes de la categorie : \n"
413
        result += '\n'.join(map(str,self.morphismes))+"\n\n"
414
415
        return result
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
416
    def transformer_graphviz(self, complet = True, objets = None, destination=None, afficher_identites = False):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
417
418
        """Permet de visualiser la catégorie avec graphviz"""
        Categorie.nb_viz += 1
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
419
420
        if destination == None:
            destination = "graphviz/categorie"+str(Categorie.nb_viz)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
421

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
422
        graph = Digraph('categorie')
423
        graph.attr(concentrate="true" if GRAPHVIZ_CONCENTRATE_GRAPHS else "false")
424
        graph.attr(label=self.nom)
425
426
        if objets == None:
            objets = self.objets
427
428
429
430
431
432
433
434
            
        for o in objets:
            graph.node(str(o))
        if complet : 
            fleches = self.enumerer_toutes_composees()
            for couple in itertools.product(objets,objets):
                composees = fleches[couple]
                for c in composees:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
435
436
437
438
439
                    if afficher_identites or not c.is_identite:
                        if c in self.morphismes:
                            graph.edge(str(couple[0]),str(couple[1]),label=str(c.representant), weight="1000")
                        else:
                            graph.edge(str(couple[0]),str(couple[1]),label=str(c.representant),color="grey77")
440
441
        else:
            for morphisme in self.morphismes:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
442
                if afficher_identites or not c.is_identite:
443
                    graph.edge(str(morphisme.source),str(morphisme.cible),label=str(morphisme.representant))
444
        graph.render(destination)
445
446
    
    
447
def main():
448
449
450
451
452
453
454
455
456
457
458
459
    # cat = Categorie("Acyclique")
    # cat.ajouter_objets("ABCDEF")
    # f,g,h,i,j,k,l = [Morphisme('A','B','f'),Morphisme('A','C','g'),Morphisme('A','E','h'),Morphisme('B','D','i'),Morphisme('B','E','j'),Morphisme('C','E','k'),Morphisme('C','F','l')]
    # cat.ajouter_morphismes([f,g,h,i,j,k,l])
    # cat.transformer_graphviz()
    # t = Diagramme.Triangle(cat,"ABE",[f,j,h])
    # t.faire_commuter()
    # cat.transformer_graphviz()
    # t = Diagramme.Triangle(cat,"ACE",[g,k,h])
    # t.faire_commuter()
    # cat.transformer_graphviz()
    # print("est_cyclique : "+str(cat.est_cyclique()))
460
    
461
462
463
464
465
466
    # cat = Categorie("Test Isomorphisme")
    # cat.ajouter_objets("ABC")
    # f,g,h,i = [Morphisme('A','B','f'),Morphisme('B','A','g'),Morphisme('A','C','h'),Morphisme('C','A','i')]
    # cat.ajouter_morphismes([f,g,h,i])
    # t = Diagramme.Triangle(cat,"ABA",[f,g,cat.identites['A']])
    # t.faire_commuter()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
467
468
    # t = Diagramme.Triangle(cat,"ACA",[h,i,cat.identites['A']])
    # t.faire_commuter()
469
470
471
472
473
474
475
    # t = Diagramme.Triangle(cat,"BAB",[g,f,cat.identites['B']])
    # t.faire_commuter()
    # t = Diagramme.Triangle(cat,"CAC",[cat.Composee(i,h,i),h,cat.Composee(i,h)])
    # t.faire_commuter()
    # cat.transformer_graphviz()
    # t.transformer_graphviz()
    # print("est_cyclique : "+str(cat.est_cyclique()))
476
    
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
    cat = Categorie("Test cycles")
    cat.ajouter_objets("ABCDEFG")
    a1,a2,a3 = [Morphisme('A','B','a1'),Morphisme('B','C','a2'),Morphisme('C','A','a3')]
    b1,b2,b3 = [Morphisme('A','D','b1'),Morphisme('D','E','b2'),Morphisme('E','A','b3')]
    c1,c2,c3 = [Morphisme('A','F','c1'),Morphisme('F','G','c2'),Morphisme('G','A','c3')]
    cat.ajouter_morphismes([a1,a2,a3,b1,b2,b3,c1,c2,c3])
    a = cat.Composee(a1,a2,a3)
    b = cat.Composee(b1,b2,b3)
    c = cat.Composee(c1,c2,c3)
    t = Diagramme.Triangle(cat,"AAA",[a,cat.identites['A'],cat.identites['A']])
    t.faire_commuter()
    t = Diagramme.Triangle(cat,"AAA",[b,cat.identites['A'],cat.identites['A']])
    t.faire_commuter()
    t = Diagramme.Triangle(cat,"AAA",[c,cat.identites['A'],cat.identites['A']])
    t.faire_commuter()
    t = Diagramme.Triangle(cat,"AAA",[a,c,cat.identites['A']])
    t.faire_commuter()
    t = Diagramme.Triangle(cat,"AAA",[a,b,cat.identites['A']])
    t.faire_commuter()
    t = Diagramme.Triangle(cat,"AAA",[b,a,cat.identites['A']])
    t.faire_commuter()
    t = Diagramme.Triangle(cat,"AAA",[c,a,cat.identites['A']])
    t.faire_commuter()
    t = Diagramme.Triangle(cat,"AAA",[b,c,cat.identites['A']])
    t.faire_commuter()
    t = Diagramme.Triangle(cat,"AAA",[c,b,cat.identites['A']])
    t.faire_commuter()
    cat.transformer_graphviz()
    print(cat.enumerer_cycles('D')[0])
506
    
507
508
509
    print("est_cyclique : "+str(cat.est_cyclique()))
    print(cat.compter_toutes_composees())
    print(sum(map(len,cat.enumerer_toutes_composees().values())))
510
    
511
512
513
514
515
    # cat = Categorie("Test")
    # cat.ajouter_objets("AB")
    # f,g = [Morphisme('A','B','f'),Morphisme('A','B','g')]
    # cat.ajouter_morphismes([f,g])
    # cat.transformer_graphviz()
516
    
517
518
519
520
521
522
523
524
525
526
    # diag = Diagramme.DiagrammeIdentite(cat)
    # diag.faire_commuter()
    # print(cat.morph_sortants)
    # cat.transformer_graphviz()
    
    cat = Categorie("Test comptage composees")
    cat.ajouter_objets("ABCDE")
    f,g,h,i,j,k,l,m = [Morphisme('A','B','f'),Morphisme('A','E','g'),Morphisme('A','E','h'),Morphisme('B','E','i'),
    Morphisme('C','D','j'),Morphisme('B','E','k'),Morphisme('C','A','l'),Morphisme('D','E','m')]
    cat.ajouter_morphismes([f,g,h,i,j,k,l,m])
527
    cat.transformer_graphviz()
528
529
530
    print(cat.compter_toutes_composees())
    print(sum(map(len,cat.enumerer_toutes_composees().values())))
        
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
    cat = Categorie("Test comptage composees")
    cat.ajouter_objets("ABCD")
    f,g,h,i,j,k = [Morphisme('A','B','f'),Morphisme('B','A','g'),Morphisme('A','C','h'),Morphisme('C','B','i'),
    Morphisme('B','D','j'),Morphisme('C','D','k')]
    cat.ajouter_morphismes([f,g,h,i,j,k])
    diag = Diagramme.Triangle(cat,"AAA",[cat.Composee(f,g),cat.Composee(f,g),cat.Composee(f,g)])
    diag.faire_commuter()
    diag = Diagramme.Triangle(cat,"AAA",[cat.Composee(h,i,g),cat.identites['A'],cat.identites['A']])
    diag.faire_commuter()
    
    cat.transformer_graphviz()
    print(cat.compter_toutes_composees())
    print(sum(map(len,cat.enumerer_toutes_composees().values())))
    
    cat = Categorie("Test comptage composees borne sup atteinte")
    cat.ajouter_objets("ABC")
    f,g,h,i,j = [Morphisme('A','A','f'),Morphisme('A','B','g'),Morphisme('B','B','h'),Morphisme('B','C','i'),Morphisme('C','C','j')]
    cat.ajouter_morphismes([f,g,h,i,j])
    diag = Diagramme.Triangle(cat,"AAA",[cat.Composee(f,f,f,f),cat.Composee(f),cat.Composee(f,f)])
    diag.faire_commuter()
    diag = Diagramme.Triangle(cat,"BBB",[cat.Composee(h,h,h,h,h,h,h,h),cat.Composee(h),cat.Composee(h,h,h,h)])
    diag.faire_commuter()
    diag = Diagramme.Triangle(cat,"CCC",[cat.Composee(j,j,j),cat.Composee(j),cat.Composee(j)])
    diag.faire_commuter()
    
    cat.transformer_graphviz()
    print(cat.compter_toutes_composees())
    print(sum(map(len,cat.enumerer_toutes_composees().values())))
    
    
    cat.transformer_graphviz()
    print(cat.compter_toutes_composees())
    print(sum(map(len,cat.enumerer_toutes_composees().values())))
564
    
565
566
if __name__ == '__main__':
    main()