EnsFinis.py 10.8 KB
Newer Older
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
1
from Morphisme import Morphisme
2
3
from Categorie import Categorie, mise_en_cache_getitem
from CategorieLibre import CategorieLibre
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
4
5
6
7
import itertools
from config import *
if GRAPHVIZ_ENABLED:
    from graphviz import Digraph
8
from typing import *
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
9
10
11
12
13
14
15
16
17
18
19
20

class Application(Morphisme):
    """Une application A de E vers F (A : E->F) est une relation binaire telle que pour tout x de E il existe un y de F tel que F(x) = y <=> (x,y) \in A.
    On représente l'application par un dictionnaire où les clés sont des éléments de E et les valeurs des éléments de F.
    """
    nb_viz = 0
    
    def __init__(self, source:frozenset, cible:frozenset, application:dict):
        Morphisme.__init__(self,source,cible,None, source==cible and application == {x:x for x in source})
        self._app = application
        if TOUJOURS_VERIFIER_COHERENCE:
            self.verifier_coherence()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
21
22
23
24
      
    def as_dict(self) -> dict:
        return self._app
      
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
25
26
27
28
29
30
31
32
    def verifier_coherence(self):
        if len(frozenset(self._app.keys())) != len(self._app.keys()):
            raise Exception("Incoherence Application : un element a plusieurs images "+str(self._app))
        if frozenset(self._app.keys()) != self.source:
            raise Exception("Incoherence Application : l'application n'a pas suffisament ou a trop d'antecedants\n"+str(self._app)+'\n'+str(self.source))
        
    def __eq__(self,other:'Application') -> bool:
        if not issubclass(type(other),Application):
33
34
            # raise TypeError("Tentative de comparaison avec un objet de type inconnu "+str(other))
            return False
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
35
36
37
38
39
40
41
42
43
44
        return self.source == other.source and self.cible == other.cible and self._app == other._app
        
    def __hash__(self) -> int:
        return hash((self.source,self.cible,frozenset(self._app.items())))
    
    def __call__(self, element:any) -> any:
        """Renvoie l'image de l'`element` par l'application."""
        return self._app[element]
    
    def __matmul__(self, other:'Application') -> 'Application':
45
        return Application(other.source,self.cible,{e:self(other(e)) for e in other.source})
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
46
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
47
    def __repr__(self):
48
        return "/".join(map(lambda x:str(x[0])+':'+str(x[1]),self._app.items()))+'\n'
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
49
50
            
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
51
52
53
    def transformer_graphviz(self, destination:any=None):
        Application.nb_viz += 1
        if destination == None:
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
54
            destination = "graphviz/"+type(self).__name__+str(Application.nb_viz)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
55
56
57
            
        graph = Digraph('application')
        graph.attr(concentrate="true" if GRAPHVIZ_CONCENTRATE_GRAPHS else "false")
58
        graph.attr(label="Application "+self.nom)
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
        with graph.subgraph(name='cluster_0') as cluster:
            cluster.attr(label=str(self.source))
            for o in self.source:
                cluster.node(str(o))

        with graph.subgraph(name='cluster_1') as cluster:
            cluster.attr(label=str(self.cible))
            for o in self.cible:
                cluster.node(str(o)+"'")
            
        for source in self._app:
                graph.edge(str(source),str(self(source))+"'")
                
        graph.render(destination)
        if CLEAN_GRAPHVIZ_MODEL:
            import os
            os.remove(destination) 
76
77


78
79
class CategorieEnsemblesFinis(Categorie):
    """CategorieEnsFinis peut être abrégé en EnsFinis
80
81
    Catégorie des ensembles finis, cette catégorie est infinie, on ajoute uniquement les ensembles dont on a besoin.
    /!\ __call__ n'appelle pas __getitem__ /!\ """
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
82
    
83
    def __init__(self, objets:set = set(), nom:str = "Catégorie d'ensembles finis"):
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
84
85
        Categorie.__init__(self,objets,nom)
    
86
87
    def identite(self, ensemble:frozenset) -> Application:
        return Application(ensemble,ensemble,{e:e for e in ensemble})
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
88
        
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
    def __call__(self, sources:set, cibles:set) -> Generator[Application,None,None]:
        '''/!\ __call__ n'appelle pas __getitem__ /!\ '''
        for source in sources:
            for cible in cibles:
                if not issubclass(type(source),frozenset):
                    raise Exception("On s'attend à avoir des frozenset dans l'ensemble source, pas un "+str(type(source))+'\n'+str(sources))
                if not issubclass(type(cible),frozenset):
                    raise Exception("On s'attend à avoir des frozenset dans l'ensemble cible, pas un "+str(type(cible))+'\n'+str(cibles))
                for prod in itertools.product(cible,repeat=len(source)):
                    yield Application(source,cible,dict(zip(source,prod)))
    
    @mise_en_cache_getitem
    def __getitem__(self, couple_sources_cibles:tuple) -> Generator[Application,None,None]:
        '''/!\ __call__ n'appelle pas __getitem__ /!\ '''
        sources,cibles = couple_sources_cibles
        for source in sources:
            for cible in cibles:
                if not issubclass(type(source),frozenset):
                    raise Exception("On s'attend à avoir des frozenset dans l'ensemble source, pas un "+str(type(source))+'\n'+str(sources))
                if not issubclass(type(cible),frozenset):
                    raise Exception("On s'attend à avoir des frozenset dans l'ensemble cible, pas un "+str(type(cible))+'\n'+str(cibles))
                source_liste = list(source)
                cible_liste = list(cible)
                if len(source) == len(cible):
                    cat_bij = CategorieBijections()
                    cat_bij |= {source,cible}
                    for bij in cat_bij[{source},{cible}]:
                        yield bij
                    if len(source) > 0:
                        source_liste, cible_liste = list(source),list(cible)
                        projection = {source_liste[i]:cible_liste[i] for i in range(len(cible)-1)}
                        projection[source_liste[-1]] = cible_liste[0]
                        yield Application(source,cible,projection)
                elif len(source) > len(cible):
                    if len(cible) > 0:
                        yield Application(source,cible,{source_liste[i]:cible_liste[min(i,len(cible)-1)] for i in range(len(source))})
                else:
                    yield Application(source,cible,{source_liste[i]:cible_liste[i] for i in range(len(source))})
                    
                    
                
130
131
        
EnsFinis = CategorieEnsemblesFinis
132
133
134
135
136
137
138
139
140

class CategorieEnsembleParties(EnsFinis):
    """CategorieEnsembleParties peut être abrégé en EnsParties
    Catégorie de l'ensemble des parties d'un ensemble, les morphismes sont des applications."""
    
    def __init__(self, ensemble:set, nom:str = None):
        EnsFinis.__init__(self,{frozenset(ens) for i in range(len(ensemble)+1) for ens in itertools.combinations(ensemble,i)},"Catégorie des parties de "+str(ensemble) if nom == None else nom)
            
EnsParties = CategorieEnsembleParties
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
141
    
142
143
144
145
146
147
148
149
class Bijection(Application):
    def __init__(self, source:frozenset, cible:frozenset, application:dict):
        Application.__init__(self,source,cible,application)
        if TOUJOURS_VERIFIER_COHERENCE:
            self.verifier_coherence()

    def verifier_coherence(self):
        Application.verifier_coherence(self)
150
        if len(self.source) != len(self.cible):
151
            raise Exception("Incoherence Bijection : il n'y a pas autant d'element au depart qu'a l'arrivee.")
152
        if {self(x) for x in self.source} != set(self.cible):
153
154
155
156
            raise Exception("Incoherence Bijection : toute l'image n'est pas atteinte.")

class CategorieBijections(EnsFinis):
    """Sous-catégorie d'`EnsFinisCatégorie`.
157
158
    Les objets sont des ensembles et les morphismes sont des applications bijectives.
    /!\ __call__ n'appelle pas __getitem__ /!\ """
159
160
161

    def __init__(self, objets:set = set(), nom:str = "Catégorie des bijections"):
        EnsFinis.__init__(self,objets,nom)
162
163
164
165
    
    def __call__(self, sources:set, cibles:set) -> Generator[Bijection,None,None]:
        '''/!\ __call__ n'appelle pas __getitem__ /!\ '''
        for source in sources:
166
            for cible in cibles:
167
168
169
170
171
                if not issubclass(type(source),frozenset):
                    raise Exception("On s'attend à avoir des frozenset dans l'ensemble source, pas un "+str(type(source))+'\n'+str(sources))
                if not issubclass(type(cible),frozenset):
                    raise Exception("On s'attend à avoir des frozenset dans l'ensemble cible, pas un "+str(type(cible))+'\n'+str(cibles))
                source_liste,cible_liste = list(source),list(cible)
172
173
                if len(source) != len(cible):
                    continue
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
                for prod in itertools.permutations(cible_liste):
                    yield Bijection(source,cible,dict(zip(source_liste,prod)))
    
    def __getitem__(self, couple_sources_cibles:tuple) -> Generator[Bijection,None,None]:
        '''/!\ __call__ n'appelle pas __getitem__ /!\ '''
        sources,cibles = couple_sources_cibles
        for source in sources:
            for cible in cibles:
                if len(source) != len(cible):
                    continue
                if len(source) == len(cible) == 0:
                    yield Bijection(source,cible,dict())
                    continue
                if len(source) == len(cible) == 1:
                    yield Bijection(source,cible,{list(source)[0]:list(cible)[0]})
                    continue
190
                source_liste = list(source)
191
192
193
194
195
196
                cible_liste = list(cible)
                transposition = [cible_liste[1],cible_liste[0]]+cible_liste[2:]
                rotation = [cible_liste[-1]]+cible_liste[:-1]
                yield Bijection(source,cible,{source_liste[j]:transposition[j] for j in range(len(source_liste))})
                yield Bijection(source,cible,{source_liste[j]:rotation[j] for j in range(len(source_liste))})
                
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
197
def test_EnsFinis():
198
    cat = EnsFinis(set(map(frozenset,[{},{1,2},{3,4,5}])))
199
    cat.transformer_graphviz(limite_fleches=243,complet=False)
200
    cat.transformer_graphviz(limite_fleches=243,complet=True)
201
202
203
204
205
206
    # for source,cible in itertools.product(cat.objets,repeat=2):
        # print(source,cible)
        # print(len(list(cat({source},{cible}))))
        # print()
    # for fleche in cat({frozenset({1,2})},{frozenset({3,4,5})}):
        # fleche.transformer_graphviz()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
207
        
208
209
210
    # for fleche in cat({frozenset({1,2})},{frozenset({})}):
        # print("fleche de {1,2} vers {}")
        # fleche.transformer_graphviz()
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
211

212
213
def test_EnsParties():
    cat = EnsParties({1,2,3})
214
215
216
    cat.transformer_graphviz(complet=False)
    for app in cat({frozenset({1,2,3})},{frozenset({1,2})}):
        app.transformer_graphviz()
217
218

def test_CategorieBijections():
219
220
221
    cat = EnsParties({1,2,3})
    cat = CategorieBijections(cat.objets)
    for bij in cat[{frozenset({1,2,3})},{frozenset("123")}]:
222
        bij.transformer_graphviz()
223
    cat.transformer_graphviz(limite_fleches=27)
224

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
225
if __name__ == '__main__':
226
227
    test_EnsFinis()
    # test_EnsParties()
228
    # test_CategorieBijections()