# S11 05/05
import queue as q

# Graphes de test
g1_NO_d = {0:[3,4],1:[2,3,4],2:[1,4],3:[0,1], 4:[0,1,2]}
g1_NO_m = [[0,0,0,1,1],[0,0,1,1,1],[0,1,0,0,1],[1,1,0,0,0],[1,1,1,0,0]]

g2_NO_d = {0:[1,4],1:[0,2,3,4],2:[1], 3:[1,4], 4:[0,1,3]}
g2_NO_m = [[0,1,0,0,1],[1,0,1,1,1],[0,1,0,0,0],[0,1,0,0,1],[1,1,0,1,0]]

g3_O_d = {1:[2,4],2:[5,6],3:[2,6], 4:[5], 5:[3,6],6:[1,3]}
g4_O_d = {1:[2,6,7],2:[3,4],3:[1,5], 4:[6,7], 5:[1,4],6:[7], 7:[]}

g5_OP_m = [[0,1, 2, 0, 0, 0], [0, 0, 12, 0, 0, 0], [0, 0, 0, 23, 24, 25], [0, 0, 0, 0, 34, 0],[0, 0, 0, 0, 0, 45], [50, 0, 0, 0, 0, 0]]

g6_NO_d = {0:[2], 1:[2], 2:[0, 1, 3, 4], 3:[2, 4], 4:[2, 3]}
g6_NO_m = [[0,0,1,0,0], [0,0,1,0,0],[1,1,0,1,1],[0,0,1,0,1],[0,0,1,1,0]]

# 4.1 outils
#1
def degre_non_oriente(g: dict,s)->int:
    ''' graphe non orienté
        g : dictionnaire de liste d'adjacence
    '''
    if s in g.keys():
        return len(g[s])
    return 's pas dans le graphe'

#2
def degre_sortant(g: dict,s)->int:
    ''' graphe orienté
        g : dictionnaire de liste d'adjacence
    '''
    if s in g.keys():
        return len(g[s])
    return 's pas dans le graphe'

#2
def degre_entrant(g: dict,s)->int:
    ''' graphe orienté
        g : dictionnaire de liste d'adjacence
    '''
    assert s in g.keys(), 's pas dans le graphe'
    deg_e = 0
    for liste_a in g.values():
        if s in liste_a:
            deg_e += 1
    return deg_e


# 4.2 Fonction de base
#4
def convertir_matrice_dict(graphe_mat):
    graphe_dict = {}
    list_a = []
    for i in range(len(graphe_mat)):
        for j in range(len(graphe_mat)):
            if graphe_mat[i][j] != 0:
                list_a.append(j)
        graphe_dict[i] = list_a
        list_a = []
    return graphe_dict

def convertir_matrice_pond(graphe_mat_pond):
    graphe_dict_adj = {} # dico liste adjacence
    dict_poids = {} # dico arête/poids
    list_a = []
    for i in range(len(graphe_mat_pond)):
        for j in range(len(graphe_mat_pond)):
            if graphe_mat_pond[i][j] != 0:
                list_a.append(j)
                dict_poids[(i,j)] = graphe_mat_pond[i][j]
        graphe_dict_adj[i] = list_a
        list_a = []
    return graphe_dict_adj, dict_poids