Projet informatique L3A : Abel Douzal et Charles Schwing

Introduction

On travaille sur les quatre recollements du carré suivants : T^2 (tore), K^2 (bouteille de Klein) et P^2 (surface de Boy)

Ci après les quatre différents recollements du carré :

Ci-après, des représentation (plongements) des surfaces susmentionnées :

S^2 est la sphère de dimension 2, T^2 est le tore de dimension 2, K^2 est la bouteille de Klein, P^2 est la surface de Boy (ou le plan projectif) (que l'on appellera Charlie dans les algorithmes par souci de concision)

Ce travail se décompose en deux parties -relativement- indépendantes : La première traite de différents jeux de la vie sur des grilles recollées selon les trois surfaces susmentionnées. La seconde consiste en la création de labyrinthes sur ces surfaces, et de leur résolution. Quelques références sont présentées en fin de document.

On importe quelques modules nécessaires au fonctionnement des fonctions qui suivent :

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
%matplotlib notebook

1 JEU DE LA VIE

Un jeu de la vie est une règle d'évolution sur une grille pouvant prendre seulement deux états : vie ou mort. La vie d'une case ne dépendant que des états de ses voisins.

On cherche à créer des jeux de la vie selon les règles : conway, day & night, highlife et life 3 4. Ces règles servent à déterminer l'évolution des cellules de la grille, recollée selon les surfaces : tore, klein et charlie.

L'objectif est de réaliser une fonction d'animation des évolutions possibles. On cherche en plus à avoir une idée de l'évolution de la population totale avec le temps.

Ci dessous la fonction init_grille initialisant une grille noire (toutes les cases sont mortes), et la fonction aleat_grille initialisant une grille aléatoire peuplée selon une loi uniforme. Toutes les deux sont de taille n * m.

def init_grille(n,m):
    return([[0 for i in range (m)] for j in range(n)])

def aleat_grille(n,m):
    array = np.random.randint(0, high=2, size=(n,m), dtype=int)
    return array

On définit trois fonctions de voisinage pour une case de coordonnées (i,j) de la grille selon le type de surface (tore, klein ou charlie).

def voisin_tore(grille, i, j):
    n=len(grille)
    m=len(grille[0])
    return( [[grille[k%n][l%m] for l in range(j-1,j+2)] for k in range(i-1,i+2)])

def voisin_klein(grille,i,j):
    n=len(grille)
    m=len(grille[0])
    g= voisin_tore (grille,i,j)
    
    if i == 0:
        g[0][0]=grille[n-1][(m-j)%m]
        g[0][1]=grille[n-1][(m-j-1)%m]
        g[0][2]=grille[n-1][(m-j-2)%m]
        
    if i == n-1:
        g[2][0]=grille[0][(m-j)%m]
        g[2][1]=grille[0][(m-j-1)%m]
        g[2][2]=grille[0][(m-j-2)%m]
        
    return(g)

def voisin_charlie(grille,i,j):
    n=len(grille)
    m=len(grille[0])
    g= voisin_klein (grille,i,j)        
    
    if j==0: 
        g[0][0]=grille[(n-i)%n][m-1]
        g[1][0]=grille[(n-i-1)%n][m-1]
        g[2][0]=grille[(n-i-2)%n][m-1]
       
    if j==m-1:     
        g[0][2]=grille[(n-i)%n][0]
        g[1][2]=grille[(n-i-1)%n][0]
        g[2][2]=grille[(n-i-2)%n][0]
        
    if j == 0 and i == 0:
        g[0][0]=grille[0][0]
        
    if j == m-1 and i == 0:   
        g[0][2]=grille[0][m-1]
        
    if j == 0 and i == n-1:
        g[2][0]=grille[n-1][0]
        
    if j == 0 and i == 0:
        g[2][2]=grille[n-1][m-1]    
    return(g)

Une version analogue de voisin_charlie, utilisant voisin_klein.

def voisin_charlie2(grille,i,j):
    vois=voisin_klein(grille,i,j)
    n=len(grille)
    m=len(grille[0])
    gi=[[(m-j-1)%m,(m-j)%m,(m-j+1)%m],[(j-1)%m,j,(j+1)%m],[(j-1)%m,j,(j+1)%m]]
    gj=[[(n-i-1)%n,(i-1)%n,(i-1)%n],[(n-i)%n,i,i],[(n-i+1)%n,(i+1)%n,(i+1)%n]]
    def auxi(k,l):
        if i==0:
            return(gi[k][l])
        elif i==(n-1):
            return(gi[l][k])
        else:
            return((l+j-1)%m)
    def auxj(k,l):
        if j==0:
            return(gj[k][l])
        elif j==(m-1):
            return(gj[l][k])
        else:
            return((k+i-1)%n)
    return([[grille[auxj(k,l)][auxi(k,l)] for l in range(3)] for k in range(3)])

Ci-dessous, quatre fonctions définissant les quatre règles de vie mentionnées au dessus :

def conway(vois):
    S=sum(list(map(sum,vois)))-vois[1][1]
    E=vois[1][1]
    return(int((S==3) or (E==1 and S==2)))

def dayandnight(vois):
    S=sum(list(map(sum,vois)))-vois[1][1]
    E=vois[1][1]
    return(int(S==3 or S==6 or S==7 or S==8 or (S==4 and E==1)))

def highlife(vois):
    S=sum(list(map(sum,vois)))-vois[1][1]
    E=vois[1][1]
    return(int((S==3) or (S==6 and E==0) or (S==2 and E==1)))

def life_3_4(vois):
    S=sum(list(map(sum,vois)))-vois[1][1]
    E=vois[1][1]
    return(int(S==3 or S==4))

On a seulement à changer la fonction de voisinage pour changer de type de surface.

La fonction suivante donne la grille de génération suivante selon la règle choisie, et le type de surface :

def suivant(grille,regle,surface):
    n=len(grille)
    m=len(grille[0])
    neogrille=init_grille(n,m)
    for i in range(n):
        for j in range(m):
            if surface=="tore":
                vois=voisin_tore(grille,i,j)
            elif surface=="klein":
                vois=voisin_klein(grille,i,j)
            elif surface=="charlie":
                vois=voisin_charlie(grille,i,j)
            if regle=="conway":
                neogrille[i][j]=conway(vois)
            elif regle=="dayandnight":
                neogrille[i][j]=dayandnight(vois)
            elif regle=="highlife":
                neogrille[i][j]=highlife(vois)
            elif regle=="life_3_4":
                neogrille[i][j]=life_3_4(vois) 
    return(neogrille)

La fonction suivante donne l'évolution de la population de la grille selon le temps (selon le nombre de générations) :

def evolution_population(n,m,iterations,regle,surface):
    l=[0]*iterations
    grille=aleat_grille(n,m)
    def population(grid):
        pop=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                pop+=grid[i][j]
        return pop
    for k in range(iterations):
        l[k]=population(grille)
        grille=suivant(grille,regle,surface)
    return l

evolution_population(20,20,78,"highlife","tore")

[226,
 109,
 134,
 118,
 116,
 104,
 113,
 127,
 120,
 134,
 101,
 110,
 81,
 79,
 80,
 75,
 57,
 56,
 65,
 70,
 68,
 69,
 66,
 62,
 57,
 66,
 66,
 68,
 75,
 79,
 69,
 67,
 59,
 67,
 59,
 59,
 64,
 72,
 76,
 75,
 71,
 72,
 69,
 73,
 78,
 82,
 74,
 95,
 82,
 87,
 93,
 97,
 90,
 99,
 92,
 93,
 98,
 90,
 84,
 98,
 106,
 106,
 92,
 109,
 91,
 93,
 79,
 83,
 75,
 72,
 81,
 74,
 78,
 68,
 82,
 81,
 88,
 72]

On définit une structure de départ (ici un objet et un planeur pour la règle conway).

def objet(grille):
    grille[0][0]=1
    grille[1][0]=1
    grille[1][1]=1
    grille[1][2]=1
    grille[2][1]=1
    return grille

def planeur(grille):
    grille[0][4]=1
    grille[1][5]=1
    grille[2][3]=1
    grille[2][4]=1
    grille[2][5]=1
    return grille

L'exemple suivant donne l'évolution de la grille après 60 itérations (ou plus il suffit de modifier) selon la règle conway et le type de surface klein :

grille=init_grille(40,80)
res=objet(grille)
def ite(n,res):
    if n==0:
        return(res)
    else:
        return(ite(n-1,suivant(res,"conway","klein")))
res=ite(60,res)
aff=plt.pcolormesh(res)
plt.show()

On crée à présent une fonction qui affiche une animation de l'évolution de la grille selon la règle de vie et le type de surface.

La fonction animer anime dans un fichier .gif un jeu sur une grille de taille n * m en nbrimages séquences, avec la règle de vie regle et sur la surface de type surface. Attention, cette fonction est très lente pour des grilles, ou un nombre de séquences importants.

def animer(n,m,regle,surface,nbrimages):
    state = init_grille(n,m)
    state=planeur(state)
    def animate(frame):
        global state
        state = suivant(state,regle,surface)
        plt.imshow(state)
    fig = plt.figure()
    anim = animation.FuncAnimation(fig, animate, frames=nbrimages, interval=200)
    anim.save("jeu-de-la-vie-"+regle+"-"+surface+".gif")
    plt.show()

animer(10,10,"conway","charlie",40)

MovieWriter ffmpeg unavailable; using Pillow instead.

2 LABYRINTHE

Préliminaire :

On cherche à créer des labyrinthes sans boucles (i.e. des labyrinthes ayant une structure d'arbres), aléatoirement sur des grilles recollées selon les différents types de surface : tore, bouteille de Klein et la surface de Boy (toujours appelée charlie).

Pour construire un labyrinthe sur une grille recollée au niveau de ses bords, on commence par créer un graphe (grille, c'est-à-dire que chaque sommet possède quatre voisins), et l'on pondère les arêtes selon une loi uniforme. On détermine ensuite l'arbre couvrant de poids minimum : ce sera le labyrinthe recherché.

On passera de la structure de graphe sous forme de tableau des voisins à celle sous forme de matrice d'adjacence par la conversion suivante : le point de coordonnées (i,j) de la matrice d'adjacence est représentée par l'entier m*i+j dans le tableau des voisins.

On initialise un labyrinthe de type grille où on peut se déplacer au plus dans quatre directions, cela sur une surface fermée de type tore, klein ou charlie le poids donné sur les arêtes sert uniquement à déterminer de façon aléatoire (supposée uniforme) un labyrinthe qui sera un arbre couvrant de poids minimal sur le graphe connexe pondéré ainsi formé.

Ci-après les trois fonctions qui permettent de générer sous forme de couple : tableau des voisins, liste des poids des arêtes, un graphe grille recollée selon le type de surface indiqué dans le nom de la fonction. Les poids donnés sont pris selon une loi supposée uniforme.

#plutôt rapide
def init_lab_tore(m):    
    G=[[((i-1)%m)*m+j,((i+1)%m)*m+j,m*i+((j-1)%m),m*i+((j+1)%m)] for i in range(m) for j in range(m)]
    W=[[0]*4 for i in range(m*m)]
    for i in range(m):
        for j in range(m):
            for h in range(4):
                if W[m*i+j][h]==0:
                    a=np.random.random()
                    W[m*i+j][h]=a
                    x,y=((G[m*i+j][h])//m,(G[m*i+j][h])%m)
                    if x==i:
                        if y==((j-1)%m):
                            W[G[m*i+j][h]][2]=a
                        else:
                            W[G[m*i+j][h]][3]=a
                    else:
                        if x==((i-1)%m):
                            W[G[m*i+j][h]][0]=a
                        else:
                            W[G[m*i+j][h]][1]=a
    return(G,W)

def init_lab_klein(m):    
    G=[[((i-1)%m)*m+j,((i+1)%m)*m+j,m*i+((j-1)%m),m*i+((j+1)%m)] for i in range(m) for j in range(m)]
    for c in range (int(m/2)) :
        G[c][0],G[m-c-1][0]=G[m-c-1][0],G[c][0]
        G[c+m*(m-1)][1],G[(m-c-1)+m*(m-1)][1]=G[(m-c-1)+m*(m-1)][1],G[c+m*(m-1)][1]
    
    W=[[0]*4 for i in range(m*m)]
    for i in range(m):
        for j in range(m):
            for h in range(4):
                if W[m*i+j][h]==0:
                    a=np.random.random()
                    W[m*i+j][h]=a
                    x,y=((G[m*i+j][h])//m,(G[m*i+j][h])%m)
                    if x==i:
                        if y==((j-1)%m):
                            W[G[m*i+j][h]][2]=a
                        else:
                            W[G[m*i+j][h]][3]=a
                    else:
                        if x==((i-1)%m):
                            W[G[m*i+j][h]][0]=a
                        else:
                            W[G[m*i+j][h]][1]=a
                            
    for c in range (int(m/2)) :
        W[c][0],W[m-c-1][0]=W[m-c-1][0],W[c][0]
        W[c+m*(m-1)][1],W[(m-c-1)+m*(m-1)][1]=W[(m-c-1)+m*(m-1)][1],W[c+m*(m-1)][1] 
    return(G,W)

def init_lab_charlie(m):    
    G=[[((i-1)%m)*m+j,((i+1)%m)*m+j,m*i+((j-1)%m),m*i+((j+1)%m)] for i in range(m) for j in range(m)]
    for c in range (int(m/2)):
        G[c][0],G[m-c-1][0]=G[m-c-1][0],G[c][0]
        G[c+m*(m-1)][1],G[(m-c-1)+m*(m-1)][1]=G[(m-c-1)+m*(m-1)][1],G[c+m*(m-1)][1]
    for d in range (int(m/2)):
        G[d*m][2],G[(m-d-1)*m][2]=G[(m-d-1)*m][2],G[d*m][2]
        G[d*m+m-1][3],G[(m-d-1)*m+m-1][3]=G[(m-d-1)*m+m-1][3],G[d*m+m-1][3]  
    W=[[0]*4 for i in range(m*m)]
    for i in range(m):
        for j in range(m):
            for h in range(4):
                if W[m*i+j][h]==0:
                    a=np.random.random()
                    W[m*i+j][h]=a
                    x,y=((G[m*i+j][h])//m,(G[m*i+j][h])%m)
                    if x==i:
                        if y==((j-1)%m):
                            W[G[m*i+j][h]][2]=a
                        else:
                            W[G[m*i+j][h]][3]=a
                    else:
                        if x==((i-1)%m):
                            W[G[m*i+j][h]][0]=a
                        else:
                            W[G[m*i+j][h]][1]=a
    for c in range (int(m/2)):
        W[c][0],W[m-c-1][0]=W[m-c-1][0],W[c][0]
        W[c+m*(m-1)][1],W[(m-c-1)+m*(m-1)][1]=W[(m-c-1)+m*(m-1)][1],W[c+m*(m-1)][1]
    for d in range (int(m/2)):
        W[d*m][2],W[(m-d-1)*m][2]=W[(m-d-1)*m][2],W[d*m][2]
        W[d*m+m-1][3],W[(m-d-1)*m+m-1][3]=W[(m-d-1)*m+m-1][3],W[d*m+m-1][3]               
    return(G,W)

#attention lent pour des tailles moyennes
def init_lab_tore2(m):    
    G=[[((i-1)%m)*m+j,((i+1)%m)*m+j,m*i+((j-1)%m),m*i+((j+1)%m)] for i in range(m) for j in range(m)]
    W=[[0]*(m*m) for i in range(m*m)]
    for k in range(m*m):
        for l in G[k]:
            if W[k][l]==0:
                a=np.random.random()
                W[k][l]=a
                W[l][k]=a
    return(G,W)

On privilégiera donc la fonction de init_lab_tore.

Voici une fonction qui nous sera utile dans la suite, elle retourne l'indice du premier élément égal à x dans la liste l. La fonction weight donne le poids dans le graphe pondéré (G,W) entre les sommets u et v.

def filtre(x,l):
    for i in range(len(l)):
        if x==l[i]:
            return(i)
    return(None)

def weight(u,v,G,W):
    return(W[u][filtre(v,G[u])])

Algorithme à proprement parler

On met en place la structure union-find pour gérer les partitions d'ensembles, avec améliorations, d'où un coût en O((k+n)α(n)) où α(n) est l'inverse de la fonction (n -> A(n,n)) où A est la fonction d'Ackermann (On ne prouve pas ce résultat). On le fait sous la forme d'un module/classe pour une réutilisation facile.

class UnionFind:
    def __init__(self,n):
        self.up=list(range(n))
        self.rank=[0]*n

    def find(self,x):
        if self.up[x]==x:
            return(x)
        else:
            self.up[x]=self.find(self.up[x])
            return(self.up[x])

    def union(self,x,y):
        repr_x=self.find(x)
        repr_y=self.find(y)
        if repr_x==repr_y:
            return(False)
        if self.rank[repr_x]==self.rank[repr_y]:
            self.rank[repr_x]+=1
            self.up[repr_y]=repr_x
        elif self.rank[repr_x]>self.rank[repr_y]:
            self.up[repr_y]=repr_x
        else:
            self.up[repr_x]=repr_y
        return(True)

Algorithme de Kruskal : pour déterminer l'arbre couvrant de poids minimal dans un graphe non orienté connexe pondéré par des réels : G=(V,E,W). Le coût temporel est celui du tri des arêtes soit en O(|E|log|E|) Le graphe est représenté par le tableau de la liste des voisins (en python la liste de la liste des voisins) les poids (weight) est une matrice de flottants de taille |G|^2 ~ |E|.

def kruskal(graph,W):
    uf=UnionFind(len(graph))
    edges=[]
    for u in range(len(graph)):
        for v in graph[u]:
            edges.append((weight(u,v,graph,W),u,v))
    edges.sort()
    mst=[]
    for w,u,v in edges:
        if uf.union(u,v):
            mst.append((u,v))
    return(mst)

Voici une fonction pour changer le format de données en sortie de kruskal en vue de l'afficher (ça peut être amélioré ou intégré à affichage, c'est comme on veut). De plus elle permet de sélectionner le type de surface du graphe utilisé :

def points_relies(m,surface):
    if surface=="tore":
        (G,W)=init_lab_tore(m)
    elif surface=="klein":
        (G,W)=init_lab_klein(m)
    elif surface=="charlie":
        (G,W)=init_lab_charlie(m)
    arb=kruskal(G,W)
    def aux(x):
        (k,l)=x
        return([(k//m,k%m),(l//m,l%m)])
    return(list(map(aux,arb)))

Les fonctions suivantes sont les fonctions d'affichage des labyrinthes associés au type de surface : m est la taille du côté de la grille, e est une variable qui permet de contrôler l'empilement au niveau du graphique. La stratégie d'affichage est par "cassage de murs" : on construit une grille quadrillée noire, et on place un segment blanc sur les cloisons à éliminer (là où passe le labyrinthe) les spécificités apparaissant au niveau des bordures.

def affichage_tore(m,l,e):
    vx=[]
    hx=[]
    vmin=[]
    vmax=[]
    hmin=[]
    hmax=[]
    for a in l:
        [(a1,a2),(b1,b2)]=a
        if a1==b1 and abs(a2-b2)<=1:
            vx.append(max(a2,b2))
            vmin.append(a1+e)
            vmax.append(a1+1-e)
        elif a2==b2 and abs(a1-b1)<=1:
            hx.append(max(a1,b1))
            hmin.append(a2+e)
            hmax.append(a2+1-e)
        elif a1==b1:
            vx.append(max(a2,b2)+1)
            vx.append(min(a2,b2))
            vmin.append(a1+e)
            vmin.append(a1+e)
            vmax.append(a1+1-e)
            vmax.append(a1+1-e) 
        elif a2==b2:
            hx.append(max(a1,b1)+1)
            hx.append(min(a1,b1))
            hmin.append(a2+e)
            hmin.append(a2+e)
            hmax.append(a2+1-e)
            hmax.append(a2+1-e)         
    plt.vlines([j for j in range(m+1)],[0 for j in range(m+1)],[m for j in range(m+1)],color='black', linewidth=1)
    plt.hlines([i for i in range(m+1)],[0 for i in range(m+1)],[m for i in range(m+1)],color='black', linewidth=1)  
    plt.vlines(vx,vmin,vmax,color='white', linewidth=2)
    plt.hlines(hx,hmin,hmax,color='white', linewidth=2)    

def affichage_klein(m,l,e):
    vx=[]
    hx=[]
    vmin=[]
    vmax=[]
    hmin=[]
    hmax=[]
    for a in l:
        [(a1,a2),(b1,b2)]=a
        if a1==b1 and abs(a2-b2)<=1:
            vx.append(max(a2,b2))
            vmin.append(a1+e)
            vmax.append(a1+1-e)
        elif a2==b2 and abs(a1-b1)<=1:
            hx.append(max(a1,b1))
            hmin.append(a2+e)
            hmax.append(a2+1-e)
        elif a1==b1:
            vx.append(max(a2,b2)+1)
            vx.append(min(a2,b2))
            vmin.append(a1+e)
            vmin.append(a1+e)
            vmax.append(a1+1-e)
            vmax.append(a1+1-e)
        elif a2 == abs(m-b2) -1:
            if a1 > b1:
                hx.append(a1+1)
                hmin.append(a2+e)
                hmax.append(a2+1-e)
                hx.append(b1)
                hmin.append(b2+e)
                hmax.append(b2+1-e)
            elif a1 <= b1:
                hx.append(b1+1) 
                hmax.append(b2+1-e)
                hmin.append(b2+e)
                hx.append(a1)
                hmin.append(a2+e)
                hmax.append(a2+1-e)
    plt.vlines([j for j in range(m+1)],[0 for j in range(m+1)],[m for j in range(m+1)],color='black', linewidth=1)
    plt.hlines([i for i in range(m+1)],[0 for i in range(m+1)],[m for i in range(m+1)],color='black', linewidth=1)
    plt.vlines(vx,vmin,vmax,color='white', linewidth=2)
    plt.hlines(hx,hmin,hmax,color='white', linewidth=2)

def affichage_charlie(m,l,e):
    vx=[]
    hx=[]
    vmin=[]
    vmax=[]
    hmin=[]
    hmax=[]
    for a in l:
        [(a1,a2),(b1,b2)]=a
        if a1==b1 and abs(a2-b2)<=1:
            vx.append(max(a2,b2))
            vmin.append(a1+e)
            vmax.append(a1+1-e)
        elif a2==b2 and abs(a1-b1)<=1:
            hx.append(max(a1,b1))
            hmin.append(a2+e)
            hmax.append(a2+1-e)
        elif ((a1,a2)==(0,0) and (b1,b2)==(m-1,m-1)) or ((a1,a2)==(m-1,m-1) and (b1,b2)==(0,0)):
            hx.append(0)
            hmin.append(0+e)
            hmax.append(1-e)
            vx.append(0)
            vmin.append(0+e)
            vmax.append(1-e)
            hx.append(m)
            hmin.append(m-1+e)
            hmax.append(m-e)
            vx.append(m)
            vmin.append(m-1+e)
            vmax.append(m-e)
        elif ((a1,a2)==(0,m-1) and (b1,b2)==(m-1,0)) or ((a1,a2)==(m-1,0) and (b1,b2)==(0,m-1)):
            hx.append(m)
            hmin.append(0+e)
            hmax.append(1-e)
            vx.append(0)
            vmin.append(m-1+e)
            vmax.append(m-e)
            hx.append(0)
            hmin.append(m-1+e)
            hmax.append(m-e)
            vx.append(m)
            vmin.append(0+e)
            vmax.append(1-e)
        elif a1+b1+1==m and b2==0:
            vx.append(a2+1)
            vmin.append(a1+e)
            vmax.append(a1+1-e)
            vx.append(b2)
            vmin.append(b1+e)
            vmax.append(b1+1-e)
        elif a1+b1+1==m and a2==0:
            vx.append(b2+1)
            vmin.append(b1+e)
            vmax.append(b1+1-e)
            vx.append(a2)
            vmin.append(a1+e)
            vmax.append(a1+1-e)
        elif a2+b2+1==m and b1==0:
            hx.append(a1+1)
            hmin.append(a2+e)
            hmax.append(a2+1-e)
            hx.append(b1)
            hmin.append(b2+e)
            hmax.append(b2+1-e)
        elif a2+b2+1==m and a1==0:
            hx.append(b1+1) 
            hmin.append(b2+e)
            hmax.append(b2+1-e)
            hx.append(a1)
            hmin.append(a2+e)
            hmax.append(a2+1-e)
    plt.vlines([j for j in range(m+1)],[0 for j in range(m+1)],[m for j in range(m+1)],color='black', linewidth=1)
    plt.hlines([i for i in range(m+1)],[0 for i in range(m+1)],[m for i in range(m+1)],color='black', linewidth=1)
    plt.vlines(vx,vmin,vmax,color='white', linewidth=2)
    plt.hlines(hx,hmin,hmax,color='white', linewidth=2)

La ligne qui suit est un exemple d'effacement de cloisons sur les coins de la grille de type surface de Boy (charlie) :

#affichage_charlie(5,[[(1,0),(3,4)]],(0.05))
affichage_charlie(5,[[(0,4),(4,0)]],(0.05))

On crée donc la fonction qui génère un labyrinthe aléatoirement, et qui renvoie le labyrinthe en question sous forme du graphe en format tableau de voisins (sans répétitions) de l'arbre obtenu, et de la liste des murs "à détruire".

#version modifiée de la fonction filtre (renvoie l'indice du premier élément de l égal à x):
def est_present(x,l):
    if l==[]:
        return(False)
    else:
        for i in range(len(l)):
            if x==l[i]:
                return(True)
        return(False)

def labyrinthe(m,surface):
    l=points_relies(m,surface)
    deb=np.random.randint(0,m*m-1)    #on tire deux points au hasard et on s'assure qu'ils sont différents : ce sont les points début et final
    fin=np.random.randint(0,m*m-1)
    while deb==fin:
        fin=np.random.randint(0,m*m-1)
    g=[[] for k in range(m*m)]
    for x in l:
        [(a1,a2),(b1,b2)]=x
        if not est_present(m*b1+b2,g[m*a1+a2]):
            g[m*a1+a2].append(m*b1+b2)
            g[m*b1+b2].append(m*a1+a2)
    return(g,l,deb,fin)

Résolution du labyrinthe en partant de début et en arrivant à fin : on réalise un parcours en largeur, avec l'algorithme BFS bien connu (ici la fonction est générale parce-que c'est toujours utile de l'avoir), puis on affiche le chemin reliant les sommets.

from collections import deque
#module de gestion de liste chaînée avec ajout d'élément à gauche(c'est plus simple comme ça)

def bfs(graph,deb=0):
    to_visit=deque()
    dist=[float('inf')]*len(graph)
    prec=[None]*len(graph)
    dist[deb]=0
    to_visit.appendleft(deb)
    while to_visit:           #file vide est évaluée comme un faux
        node=to_visit.pop()
        for neighbor in graph[node]:
            if dist[neighbor]==float('inf'):
                dist[neighbor]=dist[node]+1
                prec[neighbor]=node
                to_visit.appendleft(neighbor)
    return(dist,prec)

def parcours(g,deb,fin):
    dist,prec=bfs(g,deb)
    chemin=deque([])
    x=fin
    while prec[x]!= None:
        chemin.appendleft(x)
        x=prec[x]
    return(chemin)

Les deux fonctions suivantes affichent le chemin reliant deux points tirés aléatoirement (uniformément) dans le labyrinthe. plot_chemin l'affiche en rouge, lorsque un chemin passe par une "bordure" de la grille, elle réapparaît de l'autre côté (suivant le type de surface) et le chemin est matérialisé par une grande ligne traversante.

def chemin_to_plot(m,chemin):
    def aux(x):
        return([(x//m+0.5,x%m+0.5)])
    return(list(map(aux,chemin)))

def plot_chemin(m,chemin):
    q=chemin_to_plot(m,chemin)
    [(ydeb,xdeb)]=q[0]
    [(yfin,xfin)]=q[-1]
    plt.plot((np.transpose(q)[1]).tolist()[0],(np.transpose(q)[0]).tolist()[0],color='red')
    plt.plot(xdeb,ydeb, marker="o", color="green")
    plt.plot(xfin,yfin, marker="o", color="green")

ci dessous une ligne exemple :

g,l,deb,fin=labyrinthe(40,"klein")
chemin=list(parcours(g,deb,fin))

affichage_klein(40,l,0.05)
#plot_chemin(40,chemin)

Cette fonction est la fonction recherchée : elle affiche un voyage -qui est le plus court entre 2 points- (un chemin au hasard sur un labyrinthe au hasard sur une surface choisie de taille choisie m).

def affiche_un_voyage(m,surface):
    g,l,deb,fin=labyrinthe(m,surface)
    chemin=list(parcours(g,deb,fin))
    if surface=="tore":
        affichage_tore(m,l,0.05)
    elif surface=="klein":
        affichage_klein(m,l,0.05)
    elif surface=="charlie":
        affichage_charlie(m,l,0.05)
    plot_chemin(m,chemin)

affiche_un_voyage(50,"charlie")

3 Références

— [1] Christophe Dürr et Jill-Jênn Vie, Programmation efficace, Ellipses

— [2] Ismael Belghiti, Roger Mansuy, Jill-Jênn Vie, Les clefs pour l'info, Calvage & Mounet

— [3] Olivier Carton, Langages formels Calculabilité et complexité, Vuibert

— [4] https://fr.wikipedia.org/wiki/Homologie_(mathématiques)

usages notables : [1] a servi pour les algorithmes union-find, et kruskal [2] pour la notion de fonction d'Ackermann dans le coût de union-find [3] pour la notion de complexité

Ces ouvrages ont aussi contribué à la réalisation des autres fonctions de ce devoir, par l'enseignement qu'ils ont fourni.