import numpy as np

mat_adjacence_sherlock=np.array([[0,1,1,0,0,1,1,0],[1,0,1,0,0,0,0,1],[1,1,0,1,1,0,0,1],[0,0,1,0,1,0,0,0],[0,0,1,1,0,1,0,0],[1,0,0,0,1,0,0,0],[1,0,0,0,0,0,0,1],[0,1,1,0,0,0,1,0]])

def lettres(L):
    return [chr(65+i) for i in L]

def recherche_voisins(mat_adj,noeud):
    return [i for i in range(len(mat_adj)) if mat_adj[noeud][i]!=0]

##  representation graphe
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
for i in range(len(mat_adjacence_sherlock)):
    G.add_node(i,text=chr(65+i),size=1)

for i in range(len(mat_adjacence_sherlock)) :
    for j in range(len(mat_adjacence_sherlock)) :
        if i!=j and  mat_adjacence_sherlock[i][j]!=0:
            G.add_edge(i,j)

options = {
    "font_size": 36,
    "node_size": 2000,
    "node_color": "white",
    "edgecolors": "black",
    "linewidths": 4,
    "width": 4,
}
nx.draw_networkx(G, **options)

# Set margins for the axes so that nodes aren't clipped
ax = plt.gca()
ax.margins(0.20)
plt.axis("off")
plt.show()

##
##


import os
os.chdir(r"\\SERVEUR01\HOSPITF\Travail\Téléchargements")

from graphviz import *
import numpy as np

mat_adjacence_sherlock=np.array([[0,1,1,0,0,1,1,0],[1,0,1,0,0,0,0,1],[1,1,0,1,1,0,0,1],[0,0,1,0,1,0,0,0],[0,0,1,1,0,1,0,0],[1,0,0,0,1,0,0,0],[1,0,0,0,0,0,0,1],[0,1,1,0,0,0,1,0]])

etiquettes=[chr(ord('A') + i)for i in range(len(mat_adjacence_sherlock))]


dico={}
for i in range(len(mat_adjacence_sherlock)):
    dico[etiquettes[i]]=dict((etiquettes[j],1) for j in range(len(mat_adjacence_sherlock)) if mat_adjacence_sherlock[i,j]==1)



# def lecture_directe(dictionnaire):
#     # définition du graphe non orienté avec le moteur 'neato'
#     graphe = Graph(engine='neato')
#     for noeud in dictionnaire.keys():
#         # Construction des arêtes avec leurs poids
#         for arete in dictionnaire[noeud]:
#             graphe.edge(noeud,arete,label=str(dictionnaire[noeud][arete]))
#         # Construction des noeuds
#         graphe.node(noeud,noeud,shape='circle')
#     # Rendu visuel
#     return graphe.render('Question_1_corrige',view=True)
#
# lecture_directe(dico)


def graphe(nom_noeuds,matrice):
    # définition du graphe non orienté
    graphe = Graph(engine='neato')
    # Lecture de la matrice triangulaire inférieure pour éviter les doublons
    for i in range(len(matrice)):
        graphe.node(nom_noeuds[i],nom_noeuds[i],shape='circle')
        for j in range(i):
            if matrice[i][j] != 0: # On ne fait rien si le poids est 0
                graphe.edge(nom_noeuds[i],nom_noeuds[j],label=str(matrice[i][j]))
    return graphe.render('sherlock',view=True)

# def etiquettes(dictionnaire):
#     # Initialisation de la matrice et de la numérotation
#     matrice = []
#     for noeud in dictionnaire.keys():
#         matrice.append(noeud)
#     return matrice
#
# #-----------------------------------------------------------------------------
# # Test de la fonction
#
# etiquetage = etiquettes(dico)

graphe(etiquettes,mat_adjacence_sherlock)

##
def recherche_sommet_simplicial(mat_adjacence,sommet):
    n=len(mat_adjacence)
    voisins_sommet=[i for i in range(n) if mat_adjacence[sommet][i] !=0]
    for i in range(len(voisins_sommet)):
        noeud_1=voisins_sommet[i]
        for j in range(i+1,len(voisins_sommet)):
            noeud_2=voisins_sommet[j]
            if mat_adjacence[noeud_1][noeud_2]==0:
                return False
    return True

def elimination(mat_adjacence):
    sommet=0
    while len(mat_adjacence)!=0 and (sommet!=len(mat_adjacence) or sommet==0):
        if recherche_sommet_simplicial(mat_adjacence,sommet)==False :
            sommet+=1
        else:
            mat_adjacence=np.delete(mat_adjacence,sommet,axis=0)
            mat_adjacence=np.delete(mat_adjacence,sommet,axis=1)
            sommet=0
    if len(mat_adjacence)==0:
        return True
    else:
        return False

etiquettes=[chr(ord('A') + i)for i in range(len(mat_adjacence_sherlock))]


for i in range(len(mat_adjacence_sherlock)):
    mat_adjacence_1=np.delete(mat_adjacence_sherlock,i,axis=0)
    mat_adjacence_1=np.delete(mat_adjacence_1,i,axis=1)
    r=elimination(mat_adjacence_1)
    print(etiquettes[i],r)