# -*- coding: utf-8 -*-
"""
Created on Thu Sep 14 20:45:54 2017

@author: adomps
"""

import numpy as np
import random as rd

# petit graphe connexe, Gondran page 18
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]]


def listes_vers_matrice(L) :
    n = len(L) # nombre de noeuds
    M = np.zeros([n,n], dtype = int)
    for i in range(n) :
        for j in L[i] :
            M[i,j] += 1  # permet de traiter les arêtes multiples
    return M

# On ne traite que les graphes simples, pas d'arête multiple    
# Si on suppose le graphe non orienté, on peut ne parcourir
# que la moitié de la matrice, ce que je n'ai pas fait
def matrice_vers_listes(M) :
    n = len(M)
    L = []
    for i in range(n) :
        L.append([])
        for j in range(n) :
            if M[i,j] == 1 :
                L[i].append(j)
    return L
               
def degre(i, M) :
    deg = 0
    n = len(M)
    for j in range(n) :
        deg += M[i,j]
    return deg
    
def est_chaine(suite, M) :
    depart = suite[0]
    for suivant in suite[1:] :
        if M[depart, suivant] == 0 :
            return False
        else :
            depart = suivant
    return True

def est_chaine_rec(suite, M) :
    if len(suite) <= 1 : # cas terminal, suite vide ou d'un seul élément, c'est une chaine triviale
        return True
    depart = suite[0]
    suivant = suite[1]
    if M[depart, suivant] == 1 : # Si on peut avancer d'un pas
        return est_chaine_rec(suite[1:], M) # on examine la suite
    else :
        return False


def matrice_ponderee_vers_listes(M) :
    n = len(M)
    L = []
    for i in range(n) :
        L.append([])
        for j in range(n) :
            if M[i,j] != 0 :
                L[i].append((j, M[i, j]))
    return L    

# Générateur de graphes aléatoires
def construit_graphe_simple_alea(n, degre_max) :
    ''' Renvoie la liste d'adjacence d'une graphe simple, non orienté, aléaoire de n sommets
    dont le degré maximal est degre_max '''
    L_adjacence = [[] for _ in range(n)] # L_touffu = n * [[]] donnerait des alias !!!!
    for i in range(n) :
        degre = rd.randint(0, degre_max)
        for _ in range(degre) :  # on va choisir j aléatoire différente de i, avec astuce
            j = (i + rd.randint(1, n-1)) % n # attention randint inclut la borne supérieure
            if j not in L_adjacence[i] : # je veux des graphes simples. 
                L_adjacence[i].append(j)
                L_adjacence[j].append(i) # graphe non orenté : arête dans les deux sens
    return L_adjacence
            
L_touffue = construit_graphe_simple_alea(10, 15)