# TP1, OLA : graphes

## Exercice 1

Pour la suite, pour écrire des fonctions génériques, il sera utile de savoir si un graphe donné est représenté comme un matrice ou comme une liste.

    def check_type(g):
        if g == []:
            return "mat"
        elif g[0] == []:
            return "list"
        elif type(g[0][0]) == bool:
            return "mat"
        else:
            return "list"

# Question 2

    def compte_sommets(g):
        return len(g)

    def compte_aretes(g):
        res = 0

        if check_type(g) == "mat":
            for ligne in g:
                for coeff in ligne:
                    if coeff:
                        res += 1
        else:
            for sommet in g:
                res += len(sommet)
        return res

# Question 3

def adjacents(g, i, j):
    res = False
    
    if check_type(g) == "mat":
        res = g[i][j]
    else:
        res = j in g[i]
    
    return res
    
# Question 4

def successeurs(g,s) : 

    res = []
    if check_type(g) == "mat" :
        for i, test in enumerate(g[s]) : 
            if test == True : 
                res.append(i)
        return res
    else: 
        return g[s]
        
# Question 5

def predecesseurs(g, s):
    res = []
    if check_type(g) == "mat":
        for i in range(len(g)): 
            if g[i][s] == True : 
                res.append(i)
    else:
        for i in range(len(g)):
            if s in g[i]:
                res.append(i)
    return res

# Question 6

def reflexif(g):
    res = True
    for k in range(compte_sommets(g)):
        if not adjacents(g, k, k):
            return False
    return res

# Question 7

def symetrique (g) :
    bol = True
    n = compte_sommets(g)
    for i in range(n):
        for j in range(n):
            if adjacents(g, i, j) != adjacents(g, j, i) :
                bol = False
    return bol

# Question 8

def symetrisation(g):
    
    n = compte_sommets(g)
    if check_type(g) == "mat":
        res = [[False for k in range(n)] for j in range(n)]
        for i in range(n):
            for j in range(n):
                res[i][j] = g[i][j] or g[j][i]
    else:
        res = [sommet.copy() for sommet in g]
        for i, sommet in enumerate(g):
            for adjacent in sommet:
                if i not in g[adjacent]:
                    res[adjacent].append(i)
    return res

def l_to_m(list_adj):
    n = compte_sommets(list_adj)
    res = [[False for k in range(n)] for j in range(n)]
    for i, sommet in enumerate(list_adj):
        for adjacent in sommet:
            print(i, adjacent)
            res[i][adjacent] = True
    return res

## Exercice 2 : Chemins et longueurs

### Question 1

mat_adj_pond = [[None, 1   , 1   , None, 1   , None, None, None],
                [None, None, None, 2   , None, 2   , None, None],
                [None, None, None, -3  , None, None, -3  , None],
                [None, None, None, None, None, None, None, 4   ],
                [None, None, None, None, None, -5  , -5  , None],
                [None, None, None, None, None, None, None, 6   ],
                [None, None, None, None, None, None, None, 7   ],
                [None, None, None, None, None, None, None, None]]

# Question 1-a

def verifie_chemin(g, c):
    n = compte_sommets(g)
    for i, s in enumerate(c[:-1]):
        if not 0 <= s and s < n:
            print("Un des sommets n'est pas dans le graphe")
            return False
        if g[s][c[i+1]] is None:
            print("Une des arêtes n'est pas dans le graphe")
            return False
    return True

# verifie_chemin(mat_adj_pond, [0,1,3])

# Question 1-b

def longueur(g, c):
    
    if not verifie_chemin(g, c):
        return None
    
    res = 0
    for i, s in enumerate(c[:-1]):
        res += g[s][c[i+1]]
    return res

# longueur(mat_adj_pond, [0,1,3])

### Question 2

a) Il faut rajouter des zeros sur la diagonale pour prendre en compte les chemins à un seul sommet.

b) cf https://fr.wikipedia.org/wiki/Algorithme_de_Floyd-Warshall

# Question 2-c

def dist_min(a, b):
    if a is None:
        return b
    elif b is None:
        return a
    else:
        return min(a, b)

def floyd_warshall(g):
    n = len(g)
    C = [[[0 for j in range(n)] for i in range(n)] for k in range(n+1)]
    C[0] = g
    for i in range(len(g)):
        C[0][i][i] = 0 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                C[k+1][i][j] = dist_min(C[k][i][j],
                                        dist_add(C[k][i][k], C[k][k][j]))
    return C[n]

## Exercice 3 : Coloration de graphe

# Question 1

def totale(c):
    for s in c:
        if s is None:
            return False
    return True

# totale([1,0])
# totale([1,None])

# Question 2

def verifie_coloration(g, c):
    n = compte_sommets(g)
    for s1 in range(n):
        for s2 in range(n):
            if adjacents(g, s1, s2):
                if c[s1] == c[s2]:
                    return False
    return True

# verifie_coloration(list_symm, [0,1])
# verifie_coloration(list_symm, [0,0])

# Question 3

def couleur_minimale(l, c):
    utilisees = {c[s] for s in l if c[s] is not None}
    return(min(k for k in range(len(c)) if k not in utilisees))

# couleur_minimale([2,1],[None, 1, 0, 3, None])

# Question 4

def coloriage_glouton(g):
    coloration = [None for k in range(compte_sommets(g))]
    for s in range(compte_sommets(g)):
        adjacents     = predecesseurs(g,s) + successeurs(g,s)
        coloration[s] = couleur_minimale(adjacents, coloration)
    return coloration, len(set(coloration))

# coloriage_glouton(list_adj)