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):
                morphismes2 = [m for compo in morphismes for m in compo]
                for i in range(len(morphismes2), 1, -1):
                    for j in range(0, len(morphismes2) - i + 1):
                        sous_composee = Composition(*morphismes2[j:j + i])
                        if sous_composee in self.Composee.loi_de_composition:
                            morphismes2 = morphismes2[0:j] + [
                                self.Composee.loi_de_composition[sous_composee]] + morphismes2[j + i:]
                            return Composee._simplifier_composee(morphismes2)
                return morphismes2

            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 = Categorie(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)
        newone.Composee.loi_de_composition = copy.copy(self.Composee.loi_de_composition)
        return newone

    def __eq__(self, other):
        return self.objets == other.objets and self.morphismes == other.morphismes and \
               self.identites == other.identites and self.morph_sortants == other.morph_sortants \
               and self.morph_entrants == other.morph_entrants and self.diagrammes == other.diagrammes \
               and self.Composee.loi_de_composition == other.Composee.loi_de_composition

    def __hash__(self):
        return super().__hash__()
        
    def __str__(self):
        return str(self.nom)

    def fleches_elem(self, source, cible, inclure_id = True):
        """Renvoie la liste de flèches élémentaires de source à cible."""
        return [morph for morph in self.morph_sortants[source] if morph.cible == cible and (inclure_id or not morph.is_identite)]

    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 copy.copy(self.morph_entrants[objet]):
            self.supprimer_morphisme(morph)
        for morph in copy.copy(self.morph_sortants[objet]):
            self.supprimer_morphisme(morph)
        self.supprimer_morphisme(self.identites[objet])
        self.objets.remove(objet)
        del self.morph_entrants[objet]
        del self.morph_sortants[objet]
        del self.identites[objet]
        for d in self.diagrammes:
            if objet in d.cat_source.objets:
                if len(d.cat_source.morph_entrants[objet]) == len(d.cat_source.morph_sortants[objet]) == 0:
                    d.cat_source.supprimer_objet(objet)
                else:
                    d.transformer_graphviz()
                    d.cat_source.transformer_graphviz(destination="graphviz/debug",complet=False)
                    raise Exception("Il reste des morphismes sortants ou entrants d'un objet supprime "+str(objet))
        if TOUJOURS_VERIFIER_COHERENCE:
            self.verifier_coherence()
            
    def supprimer_objets(self,objets):
        for obj in copy.copy(objets):
            self.supprimer_objet(obj)

    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 supprimer_morphismes(self, morphismes):
        for morph in copy.copy(morphismes):
            self.supprimer_morphisme(morph)

    def ajouter_morphisme(self, morphisme):
        self.morphismes += [morphisme]
        self.morph_entrants[morphisme.cible] += [morphisme]
        self.morph_sortants[morphisme.source] += [morphisme]
        if morphisme.is_identite:
            self.remplacer_identite(morphisme)
        self.verifier_coherence()

    def ajouter_morphismes(self, morphismes):
        for m in morphismes:
            self.ajouter_morphisme(m)

    def remplacer_identite(self, morphisme):
        """Remplace l'identité d'un objet par le morphisme."""
        if not morphisme.is_identite:
            raise Exception(
                "Tentative de remplacer une identite par un morphisme qui n'est pas une identite " + str(morphisme))
        objet = morphisme.source
        if objet != morphisme.cible:
            raise Exception(
                "Tentative de remplacer une identite par un morphisme qui n'est pas une identite." + str(morphisme))
        self.morphismes.remove(self.identites[objet])
        self.identites[objet] = morphisme
        self.morph_sortants[objet].remove(morphisme)
        self.morph_entrants[objet].remove(morphisme)

    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=tuple()):
            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 table_loi_de_composition(self):
        """Renvoie un dico de dico tel que table[f][g] = g o f, table[f][g] = None si f et g ne sont pas composables.
        La table contient les compositions triviales f o Id = f, f o g = f o g, f o (g o h) = (f o g) o h etc.
        Appel à  enumerer_toutes_composees, préferer accéder au dico Composee.loi_de_composition si possible."""
        table = defaultdict(defaultdict)
        composees = self.enumerer_toutes_composees()
        fleches = list(set([e for liste in composees.values() for e in liste]))
        print(fleches)
        for f,g in itertools.product(fleches, repeat=2):
            if f.cible == g.source:
                table[f][g] = self.Composee(f,g)
        return table

    def pretty_print_loi_de_composition(self,destination=None):
        """Si destination == None, alors on le print sinon on l'écrit dans un fichier"""
        composees = self.enumerer_toutes_composees()
        fleches = list(set([e for liste in composees.values() for e in liste]))
        fleches.sort(key = str)
        fleches.sort(key = lambda x:len(str(x)))
        result = "\t"+'\t'.join(map(lambda x:str(x).replace(' >> ','>'),fleches))+"\n"
        for f in fleches:
            result += str(f).replace(' >> ','>')+"\t"
            for g in fleches:
                if f.cible == g.source:
                    result += str(self.Composee(f, g)).replace(' >> ','>')+"\t"
                else:
                    result += "X\t"
            result += '\n'
        if destination != None:
            with open(destination, 'w') as f:
                f.write(result)
        else:
            print(result)

    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(lambda x: x.pretty_print(), 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 morphisme.is_identite:
                    graph.edge(str(morphisme.source), str(morphisme.cible), label=str(morphisme.representant))
        graph.render(destination)
        if CLEAN_GRAPHVIZ_MODEL:
            import os
            os.remove(destination)


def main():
    cat = Categorie("Catégorie acyclique")
    cat.ajouter_objets("ABCDEF")
    f,g,h,i,j,k = [Morphisme('A','B','f'),Morphisme('A','C','g'),Morphisme('B','D','h'),Morphisme('B','E','i'),
                       Morphisme('C','E','j'),Morphisme('C','F','k')]
    cat.ajouter_morphismes([f,g,h,i,j,k])
    cat.transformer_graphviz()
    cat4 = cat.__copy__()

    diag = Diagramme.Carre(cat,"ABCE",[f,i,g,j])
    diag.faire_commuter()
    diag.transformer_graphviz()
    cat.transformer_graphviz()

    m = Morphisme('B', 'C', 'm')
    cat4.ajouter_morphisme(m)
    import CategoriePreordre
    cat4 = CategoriePreordre.CategoriePreordre(cat4)

    a = Morphisme('A','A','a')
    cat.ajouter_morphisme(a)
    cat4.ajouter_morphisme(a)
    diag = Diagramme.Triangle(cat,"AAA",[a,a,a])
    diag2 = Diagramme.Triangle(cat4,"AAA",[a,a,a])
    diag.faire_commuter()
    diag2.faire_commuter()
    cat.nom = "Catégorie"
    cat4.nom = "Catégorie"
    cat.transformer_graphviz()

    b = Morphisme('E','A','b')
    cat.ajouter_morphisme(b)
    diag = Diagramme.Triangle(cat, "AAA", [cat.Composee(f,i,b), cat.Composee(f,i,b), cat.Composee(f,i,b)])
    diag.faire_commuter()
    diag = Diagramme.Triangle(cat, "AAA", [cat.Composee(f,i,b), a, cat.identites['A']])
    diag.faire_commuter()
    cat.transformer_graphviz()

    cat.transformer_graphviz(False)
    import CategoriePreordre
    cat = CategoriePreordre.CategoriePreordre(cat)
    cat.transformer_graphviz()

    cat.diagrammes[-1].transformer_graphviz()

    cat2 = Categorie("1 flèche")
    cat2.ajouter_objets("XY")
    z = Morphisme('X','Y','z')
    cat2.ajouter_morphisme(z)

    import Foncteur
    cat4.transformer_graphviz()
    fonct = Foncteur.Foncteur(cat2,cat4,{'X':'C','Y':'F'},{z:k})
    fonct.transformer_graphviz()

    for obj in cat.objets:
        cones = fonct.enumerer_cones(obj)
        for c in cones:
            c.transformer_graphviz()
    from CategorieCones import CategorieCones
    cat3 = CategorieCones(fonct)
    cat3.transformer_graphviz()

    cat = Categorie("Test table loi de composition")
    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()
    import CategoriePreordre
    cat2 = CategoriePreordre.CategoriePreordre(cat)
    cat2.transformer_graphviz()
    n = Morphisme('A', 'A', 'n')
    cat2.ajouter_morphisme(n)
    diag = Diagramme.Triangle(cat2, "AAA", [Composition(n,n), n, n])
    diag.faire_commuter()
    cat2.transformer_graphviz()


    # 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("ABCDE")
    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')]
    cat.ajouter_morphismes([a1, a2, a3, b1, b2, b3])
    a = cat.Composee(a1, a2, a3)
    b = cat.Composee(b1, b2, b3)
    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), cat.Composee(f), cat.Composee(f)])
    diag.faire_commuter()
    diag = Diagramme.Triangle(cat, "BBB", [cat.Composee(h), cat.Composee(h), cat.Composee(h)])
    diag.faire_commuter()
    diag = Diagramme.Triangle(cat, "CCC", [cat.Composee(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())))

    cat = Categorie("Test cycles")
    cat.ajouter_objets("ABC")
    a1, a2 = [Morphisme('A', 'B', 'a1'), Morphisme('B', 'A', 'a2')]
    b1, b2 = [Morphisme('A', 'C', 'b1'), Morphisme('C', 'A', 'b2')]
    cat.ajouter_morphismes([a1, a2, b1, b2])
    a = cat.Composee(a1, a2)
    b = cat.Composee(b1, b2)
    t = Diagramme.Triangle(cat, "AAA", [a, a, cat.identites['A']])
    t.faire_commuter()
    t = Diagramme.Triangle(cat, "AAA", [b, b, 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.nb_composees_borne_sup("A", "A"))
    print(len(cat.enumerer_toutes_composees()[("A", "A")]))

if __name__ == '__main__':
    main()