''' Lycée Vaugelas MPSI 
    Graphe du métro parisien
    Représentation par listes d'adjacence
'''
# lecture du fichier du métro parisien
import os
repertoire_courant = os.getcwd()
nom_fichier = '/metro_paris.txt'
fichier = open(repertoire_courant + nom_fichier, 'rt', encoding='utf-8')

Ordre =  376
Taille =  933
ligne = fichier.readline() # Cette ligne de code permet de passer la ligne "[VERTICES]\n"  du fichier

S = []
for i in range(Ordre):
    ligne = fichier.readline().rstrip('\n')
    S.append( ligne[5:]  )

ligne = fichier.readline() # Cette ligne de code permet de passer la ligne "[EDGES]\n"  du fichier

A = []
for i in range(Taille):
    ligne = fichier.readline().split(' ')
    arc = int(ligne[0]) , int(ligne[1])
    A.append( arc  )

fichier.close()
graphe_metro = (S,A)

# création de la représentation par listes d'adjacences
def liste_adjacence(G):
    nb_sommets = len(G[0])
    LA = [[] for i in range(nb_sommets)]
    for s in range(nb_sommets):
        for (u, v) in G[1]:
            if v == s:
                LA[u].append(s)
    return LA

metro_la = liste_adjacence(graphe_metro)

### Files
from collections import deque
def file_vide():
    return deque()

def file_est_vide(f):
    return f == deque()

def enfiler(f, x):
    f.appendleft(x)

def defiler(f):
    return f.pop()



def nombre_etapes(g, source, dest) :
    """
    renvoie le plus petit nombre d'arc entre source et dest dans le graphe g
    
    Entrées :
    - g : graphe orienté représenté par sa liste d'adjacence
    - source : entier représentant l'index du sommet de départ
    - dest : idem pour le sommet d'arrivée

    Sortie :
    - nb_arc : le plus petit nombre d'arc entre source et dest
    """
    pass # TODO



def donne_acces_a_tout(g, s) :
    """
    renvoie True, si depuis le sommet s, tous les autres sommets du graphe g
    sont atteignables

    Entrées :
    - g : graphe orienté représenté par sa liste d'adjacence
    - source : entier représentant l'index du sommet de départ

    Sortie :
    - booléen

    """


    return True



def fortement_connexe(g) :
    """
    renvoie un booléen précisant, si pour tout sommet source du graphe g,
    on peut atteindre le sommet dest.

    Entrée :
    - g : graphe orienté représenté par sa liste d'adjacence

    Sortie :
    - booléen
    """


    return True