#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Oct  5 10:59:21 2022

@author: adomps
"""

import matplotlib.pyplot as plt

# petit graphe connexe
L_11 = [[3], [2, 3], [1, 3], [0, 1, 2, 4], [3]]

# petit graphe personnel
L_andre = [[5, 6, 9], [2, 5, 8], [1],[4],[3],[0, 1, 8], [0], [],[5, 9, 1], [8, 0]]


# Produits chimiques
Listes_graphe_produits_chimiques = [[1, 2, 3, 6, 7],
                                   [0, 4, 5, 6],
                                   [0, 3, 5, 6, 7],
                                   [0, 2, 4, 7], 
                                   [1, 3, 5, 6], 
                                   [1, 2, 4],
                                   [0, 1, 2, 4],
                                   [0, 2, 3] ]


L_colo = [[9, 4, 5, 11], [8, 3, 7], [9, 6, 3, 10, 11], [1, 7, 11, 10, 2, 5, 9],
          [0, 6, 8, 5, 7], [0, 8, 7, 6, 4, 3, 10], [2, 4, 5, 8, 9],
          [3, 5, 9, 1, 4, 11], [1, 4, 5, 6, 11], [0, 2, 7, 11, 3, 6, 10], 
          [3, 9, 5, 2], [3, 7, 9, 8, 2, 0]]



Listes_graphe_1 = [[1, 8], [0, 2, 3, 4, 7, 8], [1, 3, 4, 6], [1, 2, 5, 6],
            [1, 2, 5, 6, 8], [3, 4, 8], [2, 3, 4, 8], [1, 8], [0, 1, 4, 5, 6, 7]]

Listes_graphe_2 = [[1, 2, 3, 6, 7, 8, 9], [0, 2, 3, 6, 8], [0, 1, 5, 6, 9], 
                    [0, 1, 7, 8, 9], [2, 5, 6, 7, 8], [4, 6, 8],
                    [0, 1, 2, 4, 5], [0, 3, 4, 8, 9], [0, 1, 3, 4, 5, 7, 9],
                    [0, 2, 3, 7, 8]]


#########################################################################
#####   AVEC DES DICTIONNNAIRES, EX DE GRAPHES PONDÉRÉS
#########################################################################

G_p224 = {'a' : {'b' : 6, 'c' : 2},
     'b' : {'a' : 6, 'c' : 3, 'e' : 4, 'd' : 8},
     'c' : {'a' : 2, 'b' : 3, 'e' : 5, 'f' : 8},
     'd' : {'b' : 8, 'e' : 5, 'g' : 13},
     'e' : {'b' : 4, 'c' : 5, 'd' : 5, 'f' : 10, 'g': 8},
     'f' : {'c' : 8, 'e' : 10, 'g' : 6},
     'g' : {'d' : 13, 'e' : 8, 'f' : 6}}


G_villes = {'Lille' : {'Brest' : 725, 'Paris' : 222, 'Strasbourg' : 522},
            'Brest' : {'Lille' : 725 , 'Paris' : 596, 'Bordeaux' : 623},
            'Paris' : {'Lille' : 222, 'Brest' : 596, 'Strasbourg' : 490, 
                       'Nice' : 932, 'Perpignan' : 857, 'Bordeaux' : 583},
            'Strasbourg' : {'Lille' : 522, 'Paris' : 490, 'Nice' : 804},
            'Bordeaux' : {'Brest' : 623, 'Paris' : 583, 'Perpignan': 451},
            'Perpignan' : {'Bordeaux' : 451, 'Paris' : 857, 'Nice' : 476},
            'Nice' : {'Perpignan' : 476, 'Paris' : 932, 'Strasbourg' : 804},
        }
            
        
G_adj_4 = {0: {1: 3, 2: 10},
 1: {0: 3, 2: 6, 3: 2, 4: 7, 5: 4},
 2: {0: 10, 1: 6, 5: 3},
 3: {1: 2, 4: 1},
 4: {1: 7, 3: 1, 5: 2},
 5: {1: 4, 2: 3, 4: 2}}    



##################################################################################
#############  DESSIN DU LABYRINTHE
##################################################################################

def dessine_laby(G_laby, N) :   
    plt.figure()
    plt.clf()
    ax = plt.gca()
    ax.patch.set_facecolor('blue')  # Pour avoir un fond qui représentera les murs    
    plt.xlim(-1, N)
    plt.ylim(-1, N)
    for x, D in G_laby.items() :
        for y in D :
            plt.plot([x[0], y[0]], [x[1], y[1]], color='white', linewidth = 15)



def trace_soluce(soluce) :
    indices_i = [noeud[0] for noeud in soluce]
    indices_j = [noeud[1] for noeud in soluce]
    print(indices_i)
    print(indices_j)
    plt.plot(indices_i, indices_j, color = 'red', linestyle = 'dashed')


################################################################################
#### Fonction récursive de résolution d'un labyrinthe
################################################################################    


def recherche_chemin_rec(depart, arrivee, G_lab) :
    
    if depart == arrivee :
        return  ..., ...
            
    noeuds_accessibles = [s for s in G_lab[depart] if G_lab[depart][s] >= 0]
    
    if noeuds_accessibles == [] : # c'est un cul-de-sac 
        return ..., ...
      
    else : # on explore depuis chacun des points voisins
        for voisin in noeuds_accessibles :
            G_lab[...][...] = -1 # on déclare ce passage fermé
            G_lab[...][...] = -1 # en sens inverse aussi
            # Appel récursif
            essai, suite_chemin = recherche_chemin_rec(..., ..., ....) 
            if essai :  # on a trouvé !
                return ... , [depart] + .... 
        return ..., .... # si TOUS les voisins ont conduit à une impasse