import numpy as np

"""
Classe pour représenter un graphe non pondéré
"""

class Graphe:
    "Définition d'un graphe: G = Graphe('Liste des sommets à la suite' , booléen self.vertex.index( vertex )).\n \
    Ex: G = Graphe('ABC'), booléen self.vertex.index( vertex )) \n\
    Quatre méthodes : __init__, __str__, Edges, addEdges et adjMatrix.\n"
    
    def __init__(self, vertex: str, orient = True):
        # __init__ est le constructeur de la classe
        self.vertex = [ v for v in vertex ] # 'vertex' est un attribut de la classe 'Graphe'
        self.edges = {} # 'edges' est un attribut de la classe 'Graphe' représentant les arêtes
        self.ordre = len( self.vertex ) # ordre du graphe = nombre de sommets
        self.orient = orient
        
    def Edges(self, edges: dict):
        # 'Edges' est une méthode de la classe 'Graphe'
        for v,L in edges.items():
            if v not in self.vertex:
                print(f'Erreur dans la liste des sommets: {v} n\'est pas un sommet du graphe.')
                return None
            for i in L:
                if i not in self.vertex:
                    print(f'Erreur dans la liste des sommets: {i} n\'est pas un sommet du graphe.')
                    return None
                
        if self.orient:
            self.edges = edges
        else:
            for vertex, summits_list in edges.items():
                for i in summits_list:
                    self.addEdges( [ ( i , vertex ) ] )
                    self.addEdges( [ ( vertex , i ) ] )
                         
    def __str__(self): # dunder method = double underscore method
        # pour choisir le formattage de l'affichage de l'objet
        s = ''
        for vertex, edges in self.edges.items():
            s += f' {vertex} : {edges}\n'
            
        return s
        
    def addEdges(self, L: list):
        # L est une liste de couples (sommet 1 ; sommet 2)
        for i in L:
            if i[0] not in self.edges:
                self.edges[ i[0] ] =  [ i[1] ]
            else:
                self.edges[ i[0] ].append( i[1] )
                
    def adjMatrix(self):
        # obtenir la matrice d'adjacence
        M = np.zeros( (self.ordre , self.ordre) , dtype = int)
        for vertex, edges in self.edges.items():
            line = self.vertex.index( vertex )
            for v in edges:
                column = self.vertex.index( v )
                M[line][column] = 1
                
        return M
    
    def nbchains(self,i,j,n: int):
        # i, j = sommets
        M = np.linalg.matrix_power(self.adjMatrix(), n)
        return M[self.vertex.index(i)][self.vertex.index(j)]
        
        
        
# Exemple d'un graphe de sommets (A,B,C,D, E)

G = Graphe('ABCDE' , False)

""" Exemple 1 : graphe orienté 
G.Edges( { 'A' : ['B', 'C'] ,
           'B' : ['A' , 'C' , 'D'],
           'C' : ['B' , 'A'],
           'D' : ['B'],
           'E' : ['A','D'] } )"""

""" Exemple 2 : graphe non orienté """

G.Edges( { 'A' : ['B', 'C'] , 'B' : [ 'D' ] , 'C' : [ 'D' , 'E' ] } )

#print( G.__doc__ )

print( G )

print( G.adjMatrix() )

print( G.nbchains('A','B',3) )