CategorieAleatoire.py 4.5 KB
Newer Older
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
1
from GrapheDeComposition import GC,MGC
2
from Monoide import MonoideAleatoire
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
3
4
5
import random
import copy
import itertools
6
from collections import defaultdict
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
7
from config import *
8
9
10
  
class GrapheCompositionAleatoire(GC):
    """Construit un graphe de composition aléatoire."""
11
    def __init__(self, nb_fleches:int = None, proba_arreter_generation_loi_de_compo:float = 1/100,nom:str = "Catégorie Aléatoire"):
12
        if nb_fleches == None:
13
            nb_fleches = random.randint(1,30)
14
        
15
        GC.__init__(self,nom=nom)
16
        
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
        table = defaultdict(lambda:None)
        i,j = random.randint(0,nb_fleches-1),random.randint(0,nb_fleches-1)
        cases_modifiees = set()
        while random.random() > proba_arreter_generation_loi_de_compo:
            cases_modifiees |= {(i,j)}
            if table[(i,j)] == None:
                table[(i,j)] = random.randint(0,nb_fleches-1)
                for a,b,c in itertools.product(range(nb_fleches),repeat=3):
                    if table[(table[(a,b)],c)] != table[(a,table[(b,c)])]:
                        # l'associativité n'est pas vérifiée
                        for case in cases_modifiees:
                            table[case] = None
                        cases_modifiees = set()
                        i,j = random.randint(0,nb_fleches-1),random.randint(0,nb_fleches-1)
                        break
                if cases_modifiees == set():
                    # l'associativité n'est pas vérifiée
                    continue
                for a,b in itertools.product(range(nb_fleches),repeat=2):
                    if table[(a,b)] != None:
                        for c in range(nb_fleches):
                            if table[(table[(a,b)],c)] != None and table[(b,c)] == None:
                                # les compositions ne sont pas respectées
                                i,j = b,c
                                break
                            if table[(table[(a,b)],c)] == None and table[(b,c)] != None:
                                # les compositions ne sont pas respectées
                                i,j = table[(a,b)],c
                                break
                        else:
                            continue
                        break
                else:
                    #il n'y a eu aucune erreur de composition on valide les changements
                    cases_modifiees = set()
                    i,j = random.randint(0,nb_fleches-1),random.randint(0,nb_fleches-1)                
53
                    
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
        #on a une table de loi de composition aléatoire
        graphe_equiv = defaultdict(set)
        #la source d'une flèche i est représentée par le nombre 2*i
        #la cible d'une flèche i est représentée par le nombre 2*i+1
        #on va faire le graphe d'équivalence entre ces nombres
        for a,b in itertools.product(range(nb_fleches),repeat=2):
            if table[(a,b)] != None:
                # b o a = talbe[(a,b)]
                graphe_equiv[2*b] |= {2*a+1}
                graphe_equiv[2*a+1] |= {2*b}
                graphe_equiv[2*a] |= {2*table[(a,b)]}
                graphe_equiv[2*table[(a,b)]] |= {2*a}
                graphe_equiv[2*b+1] |= {2*table[(a,b)]+1}
                graphe_equiv[2*table[(a,b)]+1] |= {2*b+1}
              
        elem_a_mapper = {i for i in range(nb_fleches*2)}
        application = dict()
        dernier_element = 0
        while len(elem_a_mapper) > 0:
            elem = elem_a_mapper.pop()
            dernier_element += 1
            self |= {dernier_element}
            elem_visites = set()
            file = {elem}
            while len(file) > 0:
                elem = file.pop()
                application[elem] = dernier_element
                elem_visites |= {elem}
                file |= graphe_equiv[elem]-elem_visites
            elem_a_mapper -= elem_visites
        
        fleches = {i:MGC(application[2*i],application[2*i+1]) for i in range(nb_fleches)}
        self |= set(fleches.values())
        for i,j in itertools.product(range(nb_fleches),repeat=2):
            if table[(i,j)] != None:
                MGC.identifier_morphismes(fleches[j]@fleches[i],fleches[table[(i,j)]])
            
        
        
        
Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
94
def test_GrapheCompositionAleatoire():
95
    random.seed(1)
96
97
98
99
    for i in range(20):
        GCA = GrapheCompositionAleatoire()
        GCA.transformer_graphviz()
        GCA.loi_de_composition_to_csv('lois de composition/loi_de_compo.csv')
100
    return GCA
101

Guillaume Sabbagh's avatar
Guillaume Sabbagh committed
102
103
104

            
if __name__ == '__main__':
105
    test_GrapheCompositionAleatoire()