###########################################
###########################################
############# TP 10 : Graphes #############
###########################################
###########################################

## Importations
import numpy as np

## Exercice 1 : ensembles V et A du graphe G

# V = {0,1,2,3,4,5,6} : ensemble des sommets ('vertex' = 'sommet')
# A = {(0,1), (0,6), (1,6), (1,2), (6,2), (6,5), (5,2), (5,3), (3,2), (4,5), (4,3)} : ensemble des arêtes
# Dans cet exemple, les arêtes sont des couples (i,j) avec i,j dans V.
# Le graphe G est orienté.


## Exercice 2 : définition de sommet voisin

# Soit G = (V,A) un graphe, soient i,j deux sommets dans V.
# On dit que j est un voisin de i ssi (i,j) est dans A.
# Si G est non orienté, alors
# j est un voisin de i ssi {i,j} est dans A.
# On a alors : j voisin de i ssi i voisin de j.

## Exercice 3 : Matrice d'adjacence d'un graphe

#1. Si G est non orienté, alors j voisin de i ssi i voisin de j
# donc M_{i,j} = 1 ssi M_{j,i} = 1,
# donc M est une matrice symétrique.

#2. Exemple du poly

L0 = [0,1,0,0,0,0,1]
L1 = [0,0,1,0,0,0,1]
L2 = [0,0,0,0,0,0,0]
L3 = [0,0,1,0,0,0,0]
L4 = [0,0,0,1,0,1,0]
L5 = [0,0,1,1,0,0,0]
L6 = [0,0,1,0,0,1,0]

M = np.array([L0,L1,L2,L3,L4,L5,L6])
# M est la matrice d'adjacence du graphe orienté G du poly

T = M.transpose()
M2 = T+M
for i in range(7) :
    for j in range(7) :
        M2[i,j] = min(1,M2[i,j])
        # ou : M2[i,j] = M[i,j] or T[i,j]

## Exercice 4 : somme sur les lignes ou colonnes

#1. La somme des éléments de la ligne i de M
# est le nombre total de voisins de i.

#2. La somme des éléments de la colonne j de M
# est le nombre de sommets i tels que j est voisin de i.


## Exercice 5 : liste d'adjacence

L_adj = [[1,6],[2,6],[],[2],[3,5],[2,3],[2,5]]

## Exercice 6 : liens entre matrice et liste d'adjacence

def M2L(M) :
    (n,p) = np.shape(M)
    L = [[] for _ in range(n)]
    for i in range(n) :
        for j in range(n) :
            if M[i,j] == 1 :
                L[i].append(j)
    return L

# test :
assert M2L(M) == L_adj

def L2M(L) :
    n = len(L)
    M = np.zeros((n,n))
    for i in range(n) :
        for elt in L[i] :
            M[i,elt] = 1
    return M

# test :
assert np.all(L2M(L_adj) == M)

## Exercice 7 : nombre de chemins

#1. d_{ij} = M²_{ij} = SUM_{k=1 à n} Mik.Mkj

#2. Mik.Mkj = 1 si Mik=Mkj=1
#           = 0 sinon (si Mik=0 ou Mkj=0)
# Le premier cas équivaut à :
# k est voisin de i, et j est voisin de k
# donc : il existe un chemin de longueur 2
# entre i et j et qui passe par k.

#3. On en déduit que d_{ij} = M²_{ij} compte
# le nombre de chemins de longueur 2 du sommet i
# vers le sommet j.

#4. De même : M**k_{ij} est le nombre de chemins
# de longueur k du sommet i vers le sommet j.
# La somme des coefficients diagonaux de M**k
# est 2k fois le nombre de cycles de longueur k. (???)

## Exercice 8 : nombre de cycles

def nbcycles(M,l) :
    N = np.linalg.matrix_power(M,l)
    (n,n) = np.shape(M)
    s = 0
    for i in range(n) :
        s += N[i,i]
    return s

for l in range(2,6) :
    print('Le nombre de cycles de longueur '+str(l)+' dans le graphe G orienté est : '+str(nbcycles(M,l)))

print('\n')

for l in range(2,6) :
    print('Le nombre de cycles de longueur '+str(l)+' dans le graphe G non orienté est : '+str(nbcycles(M2,l)))

## Exercice 9 : liste des voisins

def Lvoisins(x,L) :
    return L[x]

## Exercice 10 : passé

## Exercice 11 : parcours en largeur

def parcours(start, stop, L) :
    file = [(start,[start])]
    vus = []
    while file :
        s,path = file.pop(0)
        if s not in vus :
            vus.append(s)
            V = Lvoisins(s,L)
            for v in V :
                if not v in vus :
                    file.append((v,path+[v]))
            if s == stop :
                return path
    message = "impossible d'atteindre "+str(stop) + " à partir de " + str(start)
    return message



## Exercice 12 :

L = M2L(M)
print(parcours(0, 4, L))