Categorie.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from Morphisme import Morphisme, Composition
from config import *
if GRAPHVIZ_ENABLED:
    from graphviz import Digraph
from collections import defaultdict 
import itertools
import Diagramme
import copy

class Categorie:
    """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é."""
    
    nb_viz = 0 #nombre de graphes graphviz générés
    
    def __init__(self, nom = "CategorieFinie"):
        self.nom = nom
        self.objets = [] #les objets doivent être hashable
        self.morphismes = [] #liste des morphismes de base (pas les composes)
        self.identites = dict() # à chaque objet on associe son morphisme identité, ce dernier doit aussi être présent dans morphismes
        self.morph_sortants = defaultdict(list) #Liste des morphismes sortant non triviaux d'un objet
        self.morph_entrants = defaultdict(list) 
        self.diagrammes = [] #liste des diagrammes commutatifs
        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."""
            loi_de_composition = {} #dico Composition:Composition
            ## /!\ La loi de composition doit être un graphe acyclique simplificateur /!\
            
            def verifier_coherence(noeuds_visites = tuple()):
                for noeud in Composee.loi_de_composition:
                    if noeud not in noeuds_visites:
                        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")
                        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]))
                        noeuds_visites += tuple([noeud])
                        if Composee.loi_de_composition[noeud] in noeuds_visites:
                            raise Exception("Loi de composition n'est pas acyclique : "+str(Composition(*noeud))+" -> "+str(Composee.loi_de_composition[noeud]))
                        Composee.verifier_coherence(noeuds_visites)
                
            
            def _simplifier_composee(morphismes):
                morphismes = [m for compo in morphismes for m in compo]
                for i in range(len(morphismes),1,-1):
                    for j in range(0,len(morphismes)-i+1):
                        sous_composee = Composition(*morphismes[j:j+i])
                        if sous_composee in self.Composee.loi_de_composition:
                            morphismes = morphismes[0:j]+[self.Composee.loi_de_composition[sous_composee]]+morphismes[j+i:]
                            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
    
    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)
        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])
        newone.diagrammes = copy.copy(self.diagrammes)
        return newone
        
    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]
    
    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
            assert(len(m) == len(self.morph_sortants) == len(self.morph_entrants) == len(self.diagrammes) == len(self.Composee.loi_de_composition) == 0)
        else:
            ## On vérifie l'existence de l'identité pour tous les objets (O(n))
            for o in self.objets:
                if o not in self.identites:
                    raise Exception("Pas de morphisme identite pour l'objet "+str(o))
                    
            ## 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
            for morph in self.Composee.loi_de_composition:
                if morph.source != self.Composee.loi_de_composition[morph].source:
                    raise Exception("Morphismes identifies avec des sources differentes : "+''.join(map(str,m))+","+str(self.Composee.loi_de_composition[m]))
                if morph.cible != self.Composee.loi_de_composition[morph].cible:
                    raise Exception("Morphismes identifies avec des cibles differentes : "+''.join(map(str,m))+","+str(self.Composee.loi_de_composition[m]))
            
            ## 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):
                raise Exception("Trop d'identites : "+','.join(map(str,ident)))

            ## 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]:
                                #print(' , '.join(map(str,self.morphismes)))
                                print(' , '.join(map(str,m)))
                                print(morph)
                                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))
                                
            self.Composee.verifier_coherence([])
                            
    def ajouter_objet(self, objet):
        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
        self.objets += [objet]
        self.identites[objet] = Morphisme(objet,objet, "Id"+str(objet),True)
        self.morphismes += [self.identites[objet]]
        
        if TOUJOURS_VERIFIER_COHERENCE:
            self.verifier_coherence()
    
    def ajouter_objets(self, objets):
        for i in range(len(objets)):
            self.ajouter_objet(objets[i])
            
    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()
                
    def ajouter_morphisme(self, morphisme):
        self.morphismes += [morphisme]
        self.morph_entrants[morphisme.cible] += [morphisme]
        self.morph_sortants[morphisme.source] += [morphisme]
        self.verifier_coherence()
    
    def ajouter_morphismes(self, morphismes):
        for m in morphismes:
            self.ajouter_morphisme(m)

    def enumerer_composees_sans_cycle(self,source,cible, noeuds_deja_visites = tuple()):
        """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."""
        if source == cible:
            return [self.identites[source]]
        if source not in noeuds_deja_visites:
            noeuds_deja_visites = noeuds_deja_visites+(source,)
            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 []
        
    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é."""
        cycles = []
        for morph_pred in self.morph_entrants[objet]:
            pred = morph_pred.source
            cycles_tronques = self.enumerer_composees_sans_cycle(objet,pred)
            for cycle_tronque in cycles_tronques:
                cycle = self.Composee(cycle_tronque,morph_pred)
                if cycle not in cycles:
                    cycles += [cycle]
        return cycles
        
    
    def enumerer_cycles(self,objet):
        """Enumère toutes les compositions de objet à objet qui ne sont pas l'identité.
        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)
        
        def trouver_reductions(mot=[]):
            if DEBUG_LOI_DE_COMPOSITION:
                print(' , '.join(map(str,mot)))
                print(list(map(lambda x:cycles.index(x),mot)))
            if len(mot) > 0:
                # composition = Composition(*mot)
                composee = self.Composee(*mot)
                if len(composee) < len(mot) or composee.is_identite: #l'identité est une composition de 0 morphisme
                    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
        
        return [morph for morph in trouver_reductions() if not morph.is_identite]
        
    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."""
        chemins_sans_cycles = self.enumerer_composees_sans_cycle(source,cible)
        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]
                        while k < len(c) and c[k].source != noeud:
                            morphismes += [c[k]]
                            k+=1
                        morphismes += [prod[i]]
                    while k < len(c):
                        morphismes += [c[k]]
                        k+=1
                    comp = self.Composee(*morphismes)
                    if comp not in tous_les_chemins:
                        tous_les_chemins += [comp]
            else:
                tous_les_chemins += [c] 
        return tous_les_chemins

    def enumerer_composees_sortantes(self, source):
        return [morph for cible in self.objets for morph in self.enumerer_composees(source,cible)]
        
    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
            chemins_sans_cycles = self.enumerer_composees_sans_cycle(source,cible)
            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]
                            while k < len(c) and c[k].source != noeud:
                                morphismes += [c[k]]
                                k+=1
                            morphismes += [prod[i]]
                        while k < len(c):
                            morphismes += [c[k]]
                            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 
        
    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
        
    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
    
    def compter_toutes_composees(self):
        """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)]))
        
    def pretty_print(self):
        result = "Objets de la categorie : \n"+', '.join(map(str,self.objets))+"\n\nMorphismes de la categorie : \n"
        result += '\n'.join(map(str,self.morphismes))+"\n\n"
        return result
        
    def transformer_graphviz(self, complet = True, objets = None, destination=None, afficher_identites = False):
        """Permet de visualiser la catégorie avec graphviz"""
        Categorie.nb_viz += 1
        if destination == None:
            destination = "graphviz/categorie"+str(Categorie.nb_viz)

        graph = Digraph('categorie')
        graph.attr(concentrate="true" if GRAPHVIZ_CONCENTRATE_GRAPHS else "false")
        graph.attr(label=self.nom)
        if objets == None:
            objets = self.objets
            
        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:
                    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")
        else:
            for morphisme in self.morphismes:
                if afficher_identites or not c.is_identite:
                    graph.edge(str(morphisme.source),str(morphisme.cible),label=str(morphisme.representant))
        graph.render(destination)
    
    
def main():
    # 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()))
    
    # 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()
    # t = Diagramme.Triangle(cat,"ACA",[h,i,cat.identites['A']])
    # t.faire_commuter()
    # 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()))
    
    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])
    
    print("est_cyclique : "+str(cat.est_cyclique()))
    print(cat.compter_toutes_composees())
    print(sum(map(len,cat.enumerer_toutes_composees().values())))
    
    # 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()
    
    # 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])
    cat.transformer_graphviz()
    print(cat.compter_toutes_composees())
    print(sum(map(len,cat.enumerer_toutes_composees().values())))
        
    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())))
    
if __name__ == '__main__':
    main()