Foncteur.py

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

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

class Foncteur(Morphisme.Morphisme):
    
    nb_viz = 0

    def __init__(self, categorie_source, categorie_cible, application_objets, application_morphismes, representant = None, is_identite = False):
        """application_objets doit être complète, application_morphismes doit spécifier les images de chaque morphisme du squelette.
        L'image des composées est par construction la composée des images"""
        if representant == None:
            representant = str(categorie_source.representant)+'->'str(categorie_cible.representant)
        Morphisme.Morphisme.__init__(self,categorie_source,categorie_cible,representant,is_identite)
        self.cat_source = categorie_source
        self.cat_cible = categorie_cible
        self.app_objets = application_objets
        self.app_morph = application_morphismes
        for obj in self.cat_source.objets:
            self.app_morph[self.cat_source.identites[obj]] = self.cat_cible.identites[self.app_objets[obj]]
        
        
        self.verifier_coherence()
        
    def as_diagram(self):
        import Diagramme
        return Diagramme.Diagramme(self.cat_source,self.cat_cible,self.app_objets,self.app_morph)
        
    def verifier_coherence(self):
        # self.transformer_graphviz("graphviz/ErreurFoncteur")
        
        for o in self.cat_source.objets:
            if o not in self.app_objets:
                raise Exception("Incoherence foncteur : l'application d'objet n'est pas une application, "+str(o)+" n'a pas d'image")
        for m in self.cat_source.morphismes:
            if m not in self.app_morph:
                raise Exception("Incoherence foncteur : l'application de morphismes n'est pas une application, "+str(m)+" n'a pas d'image")
       
        ##respect de l'identite
        for objet in self.cat_source.objets:
            if self.app_morph[self.cat_source.identites[objet]] != self.cat_cible.identites[self.app_objets[objet]]:
                raise Exception("Incoherence foncteur : l'image de l'identite de "+str(objet)+" ("+str(self.cat_source.identites[objet])+\
                ") n'est pas l'identite de l'image de l'objet ("+str(self.cat_cible.identites[self.app_objets[objet]])+")")
                
        ##Images de deux flèches composables sont composables
        for couple in itertools.combinations(self.app_morph,2):
            if couple[0].cible == couple[1].source:
                if self.app_morph[couple[0]].cible != self.app_morph[couple[1]].source:
                    raise Exception("Incoherence foncteur : deux fleches composables n'ont pas leur image composables : "+str(couple[0])+
                    " composable avec "+str(couple[1])+" mais "+str(self.app_morph[couple[0]])+" pas composable avec "+str(self.app_morph[couple[1]]))
            if couple[1].cible == couple[0].source:
                if self.app_morph[couple[1]].cible != self.app_morph[couple[0]].source:
                    print(self.pretty_print())
                    raise Exception("Incoherence foncteur : deux fleches composables n'ont pas leur image composables : "+str(couple[1])+
                    " composable avec "+str(couple[0])+" mais "+str(self.app_morph[couple[1]])+" pas composable avec "+str(self.app_morph[couple[0]]))
        
    def __call__(self,param):
        if param in self.cat_source.objets:
            return self.app_objets[param]
        if param in self.cat_source.morphismes:
            return self.app_morph[param]
        return self.cat_cible.Composee(*[self.app_morph[morph] for morph in param])
        
    def pretty_print(self):
        result = "Categorie source\n ===========\n"+self.cat_source.pretty_print()+"Categorie cible\n ============ \n"+self.cat_cible.pretty_print()
        result += "Application objets\n===========\n"
        for obj in self.app_objets:
            result += str(obj)+" => "+str(self.app_objets[obj])+"\n"
        result += "Application morphismes\n===========\n"
        for morph in self.app_morph:
            result += str(morph)+" => "+str(self.app_morph[morph])+"\n"
        return result
        
    def transformer_graphviz(self, destination=None, afficher_identites = False):
        """Permet de visualiser la catégorie avec graphviz"""
        Foncteur.nb_viz += 1
        if destination == None:
            destination = "graphviz/foncteur"+str(Foncteur.nb_viz)
            
        ##on determine s'il y a collision entre les noms des objets et morphismes des deux catégories
        collision = False
        for o in self.cat_source.objets:
            if o in self.cat_cible.objets:
                collision = True
                break
        if not collision:
            cat_cible_representants = list(map(lambda x:str(x.representant),self.cat_cible.morphismes))
            for morph in self.cat_source.morphismes:
                if not morph.is_identite or afficher_identites:
                    if str(morph.representant) in cat_cible_representants:
                        collision = True
                        break
        if collision:
            suffixe1 = "_1"
        else:
            suffixe1 = ""
            
        graph = Digraph('foncteur')
        graph.attr(concentrate="true" if GRAPHVIZ_CONCENTRATE_GRAPHS else "false")
        graph.attr(label="Foncteur "+self.representant)
        with graph.subgraph(name='cluster_0') as cluster:
            cluster.attr(label=self.cat_source.nom)
            nodes = []
            for o in self.cat_source.objets:
                cluster.node(str(o)+suffixe1)
            for morph in self.cat_source.morphismes:
                if not morph.is_identite or afficher_identites:
                    cluster.node(str(morph.representant)+suffixe1,style="invis",shape="point")
                    graph.edge(str(morph.source)+suffixe1,str(morph.representant)+suffixe1,label=str(morph.representant)+suffixe1,headclip="False",arrowhead="none")
                    graph.edge(str(morph.representant)+suffixe1,str(morph.cible)+suffixe1,tailclip="false")
        
        if collision:
            suffixe2 = "_2"
        else:
            suffixe2 = ""
        with graph.subgraph(name='cluster_1') as cluster:
            cluster.attr(label=self.cat_cible.nom)
            nodes = []
            for o in self.cat_cible.objets:
                cluster.node(str(o)+suffixe2)
            for morph in self.cat_cible.morphismes:
                if not morph.is_identite or afficher_identites:
                    cluster.node(str(morph.representant)+suffixe2,style="invis",shape="point")
                    graph.edge(str(morph.source)+suffixe2,str(morph.representant)+suffixe2,label=str(morph.representant)+suffixe2,headclip="False",arrowhead="none")
                    graph.edge(str(morph.representant)+suffixe2,str(morph.cible)+suffixe2,tailclip="false")
            
            composees_ajoutees = []
            for source in self.app_morph:
                if not source.is_identite or afficher_identites:
                    if self.app_morph[source] in self.cat_cible.morphismes:
                        graph.edge(str(source.representant)+suffixe1,str(self.app_morph[source].representant)+suffixe2,color="cyan")
                    elif self.app_morph[source] not in composees_ajoutees:
                        cluster.node(str(self.app_morph[source].representant)+suffixe2,style="invis",shape="point")
                        composees_ajoutees += [self.app_morph[source]]
                        graph.edge(str(self.app_morph[source].source)+suffixe2,str(self.app_morph[source].representant)+suffixe2,label=str(self.app_morph[source].representant)+suffixe2,headclip="False",arrowhead="none",color="grey77")
                        graph.edge(str(self.app_morph[source].representant)+suffixe2,str(self.app_morph[source].cible)+suffixe2,tailclip="false",color="grey77")
                        graph.edge(str(source.representant)+suffixe1,str(self.app_morph[source].representant)+suffixe2,color="cyan")
        
        
        for source in self.app_objets:
            graph.edge(str(source)+suffixe1,str(self.app_objets[source])+suffixe2,color="blue")
        
        
        graph.render(destination)
    
    def categorie_image(self):
        """Renvoie la sous-catégorie image du foncteur."""
        c = copy.copy(self.cat_cible)
        for o in copy.copy(c.objets):
            if o not in self.app_objets.values():
                c.supprimer_objet(o)
        for m in copy.copy(c.morphismes):
            if m not in self.app_morph.values():
                c.supprimer_morphisme(m)
        return c
    
    
    def enumerer_cones(self,apex):
        """Renvoie une liste de cônes.
        1) On considère les cônes du diagramme trivial où toutes les flèches de la catégorie source ont été retirées.
        2) Pour chaque flèche de la catégorie source, on retire les cônes qui ne commutent pas correctement avec l'image de la flèche.
        On a besoin de faire cette suppression uniquement pour les flèches du squelette et pas pour les composées.
        Preuve : soit F un foncteur de C1 vers C2, soient f : A->B et g : B->C deux morphismes de C1
        soient pA, pB et pC trois jambes d'un cône candidat associées respectivement aux images F(A), F(B) et F(C).
        On suppose que la propriété de commutativité du cône est respectée pour les flèches élémentaires f et g : 
        F(f) o pA = pB et F(g) o pB = pC
        on a alors F(g) o F(f) o pA = pC
        puis F(g o f) o pA = pC           car F est un foncteur
        on en déduit que la propriété du cône est respectée pour la composée de f et g cqfd.
        """  
        import Cone
        if apex not in self.cat_cible.objets:
            raise Exception("Apex pas dans la categorie indexee.")
        composees = [self.cat_cible.enumerer_composees(apex,self(objet)) for objet in self.cat_source.objets]
        tous_les_cones = [{self.cat_source.objets[i]:liste[i] for i in range(len(liste))} for liste in itertools.product(*composees)]
        for morph in self.cat_source.morphismes:
            if not morph.is_identite:
                tous_les_cones = [cone for cone in tous_les_cones if self.cat_cible.Composee(cone[morph.source],self(morph)) == cone[morph.cible]]
        return [Cone.Cone(self,apex,famille) for famille in tous_les_cones]
        
    def enumerer_cocones(self,nadir):
        """Voir enumerer_cones."""  
        if nadir not in self.cat_cible.objets:
            raise Exception("Nadir pas dans la categorie indexee.")
        composees = [self.cat_cible.enumerer_composees(self(objet),nadir) for objet in self.cat_source.objets]
        tous_les_cocones = [{self.cat_source.objets[i]:liste[i] for i in range(len(liste))} for liste in itertools.product(*composees)]
        for morph in self.cat_source.morphismes:
            if not morph.is_identite:
                tous_les_cocones = [cocone for cocone in tous_les_cocones if self.cat_cible.Composee(self(morph),cocone[morph.cible]) == cocone[morph.source]]
        return [Cocone.Cocone(self,nadir,famille) for famille in tous_les_cocones]
   
    def trouver_limite(self):
        """Renvoie la limite du foncteur s'il y en a une, None sinon."""
        cones = [c for o in self.cat_cible.objets for c in self.enumerer_cones(o)]
        for lim_candidate in cones:
            for cone in cones:
                fleches = self.cat_cible.enumerer_composees(cone.apex,lim_candidate.apex)
                for pied in self.cat_source.objets:
                    fleches = [f for f in fleches if cone.jambes[pied] == self.cat_cible.Composee(f,lim_candidate.jambes[pied])]
                if len(fleches) == 1:
                    return lim_candidate
        return None
        
    def trouver_colimite(self):
        """Renvoie la colimite du foncteur s'il y en a une, None sinon."""
        cocones = [c for o in self.cat_cible.objets for c in self.enumerer_cocones(o)]
        for colim_candidate in cocones:
            for cocone in cocones:
                fleches = self.cat_cible.enumerer_composees(colim_candidate.nadir,cocone.nadir)
                for pied in self.cat_source.objets:
                    fleches = [f for f in fleches if cocone.jambes[pied] == self.cat_cible.Composee(colim_candidate.jambes[pied],f)]
                if len(fleches) == 1:
                    return colim_candidate
        return None
    
    def categorie_cones(self):
        import Categorie
        cat_cones = Categorie.Categorie("Categorie de cones")
        cones = [e for apex in self.cat_cible.objets for e in self.enumerer_cones(apex)]
        cat_cones.ajouter_objets(cones)
        app_obj_cones = {obj:[c for c in cones if c.apex==obj] for obj in self.cat_cible.objets} #utile pour faire commuter les diagrammes après
        app_morph_fleche_cone = dict() #associe à chaque nouvelle flèche dans la cat_cone la flèche de laquelle elle vient
        for cone1,cone2 in itertools.product(cones,repeat=2):
            fleches_potentielles = [fleche for fleche in self.cat_cible.morph_sortants[cone1.apex] if fleche.cible == cone2.apex]
            # if cone1.apex == cone2.apex and cone1 != cone2:
                # fleches_potentielles += [self.cat_cible.identites[cone1.apex]]
            
            for obj in self.cat_source.objets:
                fleches_potentielles = [fleche for fleche in fleches_potentielles if cone1.jambes[obj] == self.cat_cible.Composee(fleche,cone2.jambes[obj])]
            for fleche in fleches_potentielles:
                f = Morphisme.Morphisme(cone1,cone2,fleche.representant)
                cat_cones.ajouter_morphisme(f)
                app_morph_fleche_cone[f] = fleche
                if cone1 == cone2:
                    diag = Diagramme.Triangle(cat_cones,[cone1]*3,[f,f,f])
                    diag.faire_commuter()
        ## on doit faire commuter les diagrammes de la catégorie cible dans la catégorie des cônes
        ## un noeud de la catégorie cible peut être l'apex de plusieurs noeuds (ou aucun) dans la catégorie des cônes
        ## on considère la catégorie cible réduite où tous les noeuds et les morphismes qui n'ont aucun enfant dans la cat des cônes ont été supprimés
        ## Pour tout diagramme D
        ## Soient P, Q, ... des objets de l'image diagramme D, Pi les objets de la catégorie des cônes d'apex P, etc...
        ## Pour tout élément (Pk,Ql,...) du produit cartésien {Pi}x{Qi}x...
        ## 
        cat_cible_reduite = copy.copy(self.cat_cible)
        for obj_a_suppr in [o for o in cat_cible_reduite.objets if o not in app_obj_cones]:
            cat_cible_reduite.supprimer_objet(obj_a_suppr)
        for morph_a_suppr in [m for m in cat_cible_reduite.morphismes if m not in app_morph_fleche_cone]:
            cat_cible_reduite.supprimer_morphisme(morph_a_suppr)
        for prod in itertools.product(*[app_obj_cones[o] for o in cat_cible_reduite.objets]):
            foncteur = Foncteur(cat_cible_reduite,cat_cones,{cat_cible_reduite.objets[i]:prod[i] for i in range(len(prod))},{morph:app_morph_fleche_cone[morph][0] for morph in app_morph_fleche_cone})
        
        # for morph in cat_cones.morphismes:
            # if morph.source == morph.cible:
                # diag = Diagramme.Triangle(cat_cones,[morph.source]*3,[morph]*3)
                # diag.faire_commuter()
        return cat_cones
    
class Composition(Foncteur):
    """Le foncteur composition vu comme un foncteur et non comme un morphisme."""
    def __init__(self,*foncteurs):
        if len(foncteurs) == 0:
            raise Exception("Composition de 0 foncteurs.")
        compo_morph = Morphisme.Composition(*foncteurs)
        s,c = compo_morph.source,compo_morph.cible
        Foncteur.__init__(self,s,c,{e:compo_morph(e) for e in s.objets},{e:compo_morph(e) for e in s.morphismes})
    
def main():
    from Categorie import Categorie
    
    triangle = Categorie()
    triangle.ajouter_objets(['A','B','C'])
    
    f1,g1= [Morphisme.Morphisme('A','B','f'),Morphisme.Morphisme('B','C','g')]
    morphismes_triangle = f1,g1
    triangle.ajouter_morphismes(morphismes_triangle)
    
    carre = Categorie()
    carre.ajouter_objets([1,2,3,4])

    f,g,h,i = [Morphisme.Morphisme(1,2,'f'),Morphisme.Morphisme(2,4,'g'),Morphisme.Morphisme(1,3,'h'),Morphisme.Morphisme(3,4,'i')]
    morphismes_carre = [f,g,h,i]
    carre.ajouter_morphismes(morphismes_carre)
    
    app_obj = {'A':1,'B':2,'C':4}
    app_morph = {f1:f,g1:g}
    diagramme = Foncteur(triangle, carre, app_obj, app_morph)
    
    print("F(A) = "+str(diagramme('A')))
    print("F(B) = "+str(diagramme('B')))
    print("F(C) = "+str(diagramme('C')))
    print("F(f1) = "+str(diagramme(f1)))
    print("F(g1of1) = "+str(diagramme(triangle.Composee(f1,g1))))
    
    print(diagramme.pretty_print())
    diagramme.transformer_graphviz()
    
if __name__ == '__main__':
    main()