## TP15 -- Parcours de graphes



## Exercise 15.6 -- Tests de connexité

## question 1)

# Pour cette fonction, on utilise une fonction auxiliaire.
# Elle renvoie le nombre de sommets accessibles à partir d'un sommet.
def nombresSommetsAccessibles(G, s):
    NON_TRAITE = 0
    EN_COURS = 1
    FINI = 2

    etats = {t: NON_TRAITE for t in G}
    aParcourir = []

    N = 0

    aParcourir.append(s)
    etats[s] = EN_COURS

    while aParcourir != []:
        t = aParcourir.pop()
        N = N+1
        for u in G[t]:
            if etats[u] == NON_TRAITE:
                aParcourir.append(u)
                etats[u] = EN_COURS
        etats[t] = FINI

    return N


# Voici la fonction demandée.

def unSommet(G):
    for s in G:
        return s

def estConnexe(G):
    n = len(G)
    s = unSommet(G)
    N = nombresSommetsAccessibles(G, s)
    return N == n


# Voici une version récursive de `nombresSommetsAccessibles`.

def nombresSommetsAccessibles2(G, s):
    memo = {t: False for t in G}

    def nb(t):
        if memo[t]:
            return 0
        else:
            memo[t] = True
            N = 0
            for u in G[t]:
                N = N + nb(u)
            return N+1

    return nb(s)

## question 2)

def estFortementConnexe(G):
    n = len(G)
    for s in G:
        N = nombresSommetsAccessibles(G, s)
        if N < n:
            return False
    return True



## Exercise 15.7 -- Détection de cycles

## question 2)

def estAutoAccessible(g, s):
    NON_TRAITE = 0
    EN_COURS = 1
    FINI = 2

    etats = {t: NON_TRAITE for t in g}
    aParcourir = [s]
    etats[s] = EN_COURS

    while aParcourir != []:
        t = aParcourir.pop()
        for u in g[t]:
            if u == s:
                return True
            if etats[u] == NON_TRAITE:
                aParcourir.append(u)
                etats[u] = EN_COURS
        etats[t] = FINI

    return False

def possedeUnCycle(g):
    for s in g:
        if estAutoAccessible(g, s):
            return True
    return False



## Exercise 15.8 -- Degré d'un graphe

## question 2)

def degreMax(g):
	maximum = 0
	for s in g:
		nombreSucccesseurs = len(g[s])
		if nombreSucccesseurs > maximum:
			maximum = nombreSucccesseurs
	return maximum



## Exercise 15.9 -- Inverse d'un graphe

## question 2)

def grapheInv(g):
	gInv = { s: [] for s in g }
	for s in g:
		for t in g[s]:
			gInv[t].append(s)
	return gInv



## Exercise 15.10 -- Coloration d'un graphe

## question 1)

def colorationValide(g, couleurs):
	for s in g:
		for t in g[t]:
			if couleurs[s] == couleurs[t]:
				return False
	return True