GrapheDeComposition.py 10.9 KB
Newer Older
1
2
3
4
from Categorie import Categorie
from CategorieLibre import CategorieLibre
from Morphisme import Morphisme
from collections import defaultdict
5
from config import *
6

7
class MorphismeGrapheDeComposition(Morphisme):
8
    """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
9
    `MorphismeGrapheDeComposition` peut être abrégé en MGC
10
    Un morphisme dans un graphe de composition est un chemin dans ce graphe.
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
11
    Deux morphismes peuvent être identifiés dans le graphe de composition grâce à la loi de composition statique.
12
13
14
15
16
17
    Le chemin est représenté par un tuple de morphismes de graphe de composition.
    Si un morphisme appartient à deux catégories, les lois de composition des deux graphes de composition sont partagées.
    """
    loi_de_composition = dict() # on associe à certains chemins un autre chemin aussi long ou plus court
    #{tuple de morphismes : tuple de morphismes}
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
18
19
20
21
    def identifier_morphismes(morph1:'MorphismeGrapheDeComposition',morph2:'MorphismeGrapheDeComposition'):
        """Identifie le `morph1` au `morph2`.
        Cette fonction statique modifie la loi de composition de la classe `MorphismeGrapheDeComposition`.
        Les morphismes seront identifiés indépendamment des catégories auxquelles ils appartiennent."""
22
23
24
25
        MorphismeGrapheDeComposition.loi_de_composition[morph1.__chemin] = morph2.__chemin
        MorphismeGrapheDeComposition.verifier_coherence()
    
    def verifier_coherence():
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
26
        '''Vérifie la cohérence de la loi de composition de la classe `MorphismeGrapheDeComposition`.'''
27
28
29
30
        for chemin in MorphismeGrapheDeComposition.loi_de_composition:
            if chemin == MorphismeGrapheDeComposition.loi_de_composition[chemin]:
                raise Exception("Entree de la loi de composition inutile "+str(chemin))
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
31
    def __simplifier_chemin(morph1:'MorphismeGrapheDeComposition',morph2:'MorphismeGrapheDeComposition') -> tuple:
32
33
34
35
        """
        On simplifie le chemin défini par la composition des deux morphismes grâce à la loi de composition.
        On renvoie un tuple de morphismes.
        """
36
37
38
39
        chemin = tuple([morph for morph in morph1.__chemin+morph2.__chemin if not morph.is_identite])
        if len(chemin) == 0: #s'il n'y avait que des identités
            return (morph1.__chemin[0],) #on renvoie une des identités
        # on unpack les différents chemins en un seul chemin et on retire les identités
40
41
42
43
        while True: #on continue tant qu'on a simplifié le chemin
            for nb_morphismes_consideres in range(len(chemin), 1, -1):
                for offset in range(0, len(chemin) - nb_morphismes_consideres + 1):
                    sous_composee = chemin[offset:offset + nb_morphismes_consideres]
44
45
                    if sous_composee in MorphismeGrapheDeComposition.loi_de_composition: # si il y a une simplification dans la loi de composition
                        chemin = chemin[0:offset] + MorphismeGrapheDeComposition.loi_de_composition[sous_composee]\
46
47
48
49
50
51
52
                        + chemin[offset + nb_morphismes_consideres:]
                        break
                else:
                    continue
                break
            else:
                break #on quitte si on a jamais break avant (si on a jamais simplifié)
53
54
55
56
        chemin_resultat = tuple([morph for morph in chemin if not morph.is_identite])# on retire les identités
        if len(chemin_resultat) == 0: #s'il n'y avait que des identités
            return (chemin[0],) #on renvoie une des identités
        return chemin_resultat
57
58


Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
59
    def __init__(self, source:any, cible:any, representant:any=None, is_identite:bool = False):
60
61
        self.__chemin = (self,) # le chemin sera overwrite par matmul si le morphisme est une composition
        Morphisme.__init__(self, source, cible, representant, is_identite)
62
63
        if TOUJOURS_VERIFIER_COHERENCE:
            MorphismeGrapheDeComposition.verifier_coherence()
64

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
65
66
    def __getitem__(self,entier:int) -> Morphisme:
        '''Renvoie un morphisme du chemin.'''
67
68
69
        return self.__chemin[entier]
    
    def __iter__(self):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
70
        '''On peut itérer sur les morphismes du chemin.'''
71
72
73
        for morph in self.__chemin:
            yield morph
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
74
75
    def __len__(self) -> int:
        '''Taille du chemin.'''
76
77
        return len(self.__chemin)
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
78
    def __matmul__(self,other:'MorphismeGrapheDeComposition') -> 'MorphismeGrapheDeComposition':
79
        """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
80
81
            `self` @ `other` <=> `self` o `other`
            On compose les morphismes en concaténant les chemins et en simplifiant le résultat avec la loi de composition.
82
        """
83
84
85
        if TOUJOURS_VERIFIER_COHERENCE_COMPOSEE:
            MorphismeGrapheDeComposition.verifier_coherence()
        if not issubclass(type(other),MorphismeGrapheDeComposition):
86
87
88
89
90
91
92
93
            raise Exception("Composition d'un morphisme de graphe de composition avec un morphisme de type different : "+str(self)+" o "+str(other))
        if self.source != other.cible:
            raise Exception("Composition de morphismes pas composables : "+str(self)+" o "+str(other))
        if self.is_identite:
            return other
        if other.is_identite:
            return self
        # à partir d'ici on doit instancier un nouveau morphisme
94
        chemin_simplifie = MorphismeGrapheDeComposition.__simplifier_chemin(self,other)
95
96
97
        if len(chemin_simplifie) == 1: # si on a simplifié à un morphisme on le renvoie
            return chemin_simplifie[0]
        else: #sinon on doit créer un morphisme dont le chemin est celui qu'on a trouvé
98
            nouveau_morph = MorphismeGrapheDeComposition(other.source,self.cible,representant=str(self)+'o'+str(other),is_identite=False)
99
100
101
            nouveau_morph.__chemin = chemin_simplifie
            return nouveau_morph
            
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
102
103
104
    def __eq__(self,other:'MorphismeGrapheDeComposition') -> bool:
        if not issubclass(type(other),MorphismeGrapheDeComposition):
            return False
105
106
        if len(self.__chemin) == 1:
            return len(other.__chemin) == 1 and self.__chemin[0] is other.__chemin[0]
107
108
        return self.__chemin == other.__chemin
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
109
    def __hash__(self) -> int:
110
111
112
        if len(self.__chemin) == 1:
            return super().__hash__()
        return hash(self.__chemin)
113
114
        
MGC = MorphismeGrapheDeComposition
115

116
class GrapheDeComposition(CategorieLibre):
117
    """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
118
119
    `GrapheDeComposition` peut être abrégé en `GC`.
    Un graphe de composition pour nous est un graphe muni d'une loi de composition et d'identités.
120
    Un modèle de graphe de composition est la catégorie libre engendrée par ce graphe de composition.
121
    Cette classe implémente les deux concepts ci-dessus, on peut modifier le graphe de composition et obtenir les morphismes du modèle.
122
    Concrètement, pour un modèle de graphe de composition, on peut :
123
        - ajouter un objet ou un morphisme avec |=
124
125
126
        - faire commuter un diagramme qui a pour cible ce modèle pour identifier des flèches
    """
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
127
    def __init__(self,nom:str = 'Graphe de composition'):
128
129
        CategorieLibre.__init__(self,nom)
        self.__identites = dict()
130
131
        self.__morph_entrants = defaultdict(frozenset)
        self.__morph_sortants = defaultdict(frozenset)
132
133
134
135
136
137
     
    def verifier_coherence(self):
        CategorieLibre.verifier_coherence(self)
        if self.objets != set(self.__identites.keys()):
            raise Exception("Incohérence GrapheDeComposition : il n'y a pas correspondance entre identités et objets : "+str(self.objets)+"\n"+str(self.__identites))
     
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
138
    def __eq__(self,other:'GrapheDeComposition') -> bool:
139
140
141
        return CategorieLibre.__eq__(self,other) and self.__identites == other.__identites and\
        self.__morph_entrants == other.__morph_entrants and self.__morph_sortants == other.__morph_sortants
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
142
    def __hash__(self) -> int:
143
144
145
        return hash((CategorieLibre.__hash__(self),frozenset(self.__identites.items()),\
        frozenset(self.__morph_entrants.items()),frozenset(self.__morph_sortants.items())))
    
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
146
    def identite(self,objet:any) -> MorphismeGrapheDeComposition:
147
148
149
        if objet not in self.__identites:
            print(objet)
            print(self.__identites)
150
151
        return self.__identites[objet]
            
152
    def __ior__(self,ensemble_objet_ou_morphisme:set):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
153
        """
154
155
156
157
        `objet_ou_morphisme` est considéré comme un morphisme s'il hérite de MorphismeGrapheDeComposition, c'est un objet sinon.
        Si on veut ajouter un morphisme en tant qu'objet, appeler Categorie.__ior__(cat,morphisme).
        Si le `morphisme` n'appartient pas déjà à la catégorie :
            on met à jour le graphe de composition en mettant à jour les dictionnaires morph_entrants et morph_sortants.
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
158
159
160
161
162
        Si l'`objet` n'appartient pas déjà à la catégorie :
            on ajoute l'`objet`,
            on créé une identité,
            on met à jour le graphe de composition en mettant à jour les dictionnaires morph_entrants et morph_sortants.
        """
163
164
165
166
167
168
169
170
171
172
173
174
175
        for objet_ou_morphisme in ensemble_objet_ou_morphisme:
            if issubclass(type(objet_ou_morphisme), MorphismeGrapheDeComposition):
                if not objet_ou_morphisme.is_identite:
                    self.__morph_entrants[objet_ou_morphisme.cible] |= {objet_ou_morphisme}
                    self.__morph_sortants[objet_ou_morphisme.source] |= {objet_ou_morphisme}
            elif objet_ou_morphisme not in self.objets:
                self.objets |= {objet_ou_morphisme}
                self.__identites[objet_ou_morphisme] = MorphismeGrapheDeComposition(objet_ou_morphisme,objet_ou_morphisme,'Id'+str(objet_ou_morphisme),True)
                self.__morph_entrants[objet_ou_morphisme] |= {self.__identites[objet_ou_morphisme]}
                self.__morph_sortants[objet_ou_morphisme] |= {self.__identites[objet_ou_morphisme]}
        if TOUJOURS_VERIFIER_COHERENCE:
            self.verifier_coherence()
        return self
176
        
177
178
179
180
181
182
183
184
185
186
187
188
189
190
    def __isub__(self, ensemble_objet_ou_morphisme:set):
        '''
        On supprime l'`objet` et son identité.
        On supprime le `morphisme` et on met à jour le graphe de composition.'''
        for objet_ou_morphisme in ensemble_objet_ou_morphisme:
            if issubclass(type(objet_ou_morphisme),MorphismeGrapheDeComposition):
                self.__morph_entrants[objet_ou_morphisme.cible] -= {objet_ou_morphisme}
                self.__morph_sortants[objet_ou_morphisme.source] -= {objet_ou_morphisme}
            else:
                self.objets -= {objet}
                del self.__identites[objet]
        if TOUJOURS_VERIFIER_COHERENCE:
            self.verifier_coherence()
        return self
191
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
192
    def morph_entrants(self,objet:any) -> frozenset():
193
194
        return self.__morph_entrants[objet]
       
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
195
    def morph_sortants(self,objet:any) -> frozenset:
196
197
        return self.__morph_sortants[objet]
    
198
199
200
201
GC = GrapheDeComposition

def test_GrapheDeComposition():
    GC = GrapheDeComposition()
202
203
204
    GC |= {'A','B','C'}
    morphismes = [MGC('A','B','f'),MGC('B','C','g')]
    GC |= morphismes
205
206
    GC.transformer_graphviz()

207
208
    
if __name__ == '__main__':
209
    test_GrapheDeComposition()