#!/usr/bin/python3
# -*- coding: utf-8 -*-

################################
#                              #
#         Graphes : G3         #
#                              #
################################

import numpy as np
import os
xxx=0 # ne pas modifier
os.chdir("/chemin/qui/va/bien/") # à modifier

#################################################################
''' Graphes non-orientés pondérés par des poids positifs : G3 '''
#################################################################

# ensemble des sommets
S2=xxx
# ensemble des aretes sous forme d'une liste simple
L2=xxx
# pour les tests de convertListeCompletee()
L2=[[(1,3),(2,5),(3,1)],[],[(3,4),(4,3)]]
# pour les tests du poids minimal (attention les poids mis sont aleatoires)
P2=[(0,7),(1,4),(2,1),(3,5),(4,float("inf"))]

############################
## G3 : à l'aide de listes #
############################

# renvoie une liste simple sous forme d'une liste de taille n=|S|
# entree : une liste simple expl : L=[[(1,3),(2,5),(3,1)],[],[(3,4),(4,3)]]
# sortie : une liste completee expl : L=[[(1,3),(2,5),(3,1)],[],[(3,4),(4,3)],[]]
def convertListeCompletee(L: list) -> list:
   return xxx

# renvoie toutes les aretes dont le sommet s est un sommet sous la forme (si,pi)
# entree : un sommet s et une liste completee
# sortie : une liste de couple (sj,pj)
def areteSommetP(s: int, L: list) -> list:
   return xxx

# renvoie une liste sans arete relie au sommet s dans l'ensemble fourni
# entree : un sommet s et une liste de couples (si,pi)
# sortie : une liste de couples (si,pi)
def retireSommetLigneP(s: int, ligne: list) -> list:
   return xxx

# renvoie une liste completee sans aucune arete reliee au sommet s
# entree : un sommet s et une liste completee
# sortie : une liste completee
def retireSommetListeP(s: int, L: list) -> list:
   return xxx

# fonction recursive qui implemente l'algorithme de Dijkstra, renvoie un sous-graphe minimal
# entree : deux sommets sc et fin, une liste completee L, une liste S de sommets, une liste P de couples sommet-poids
# sortie : une liste de couples representant un sous-graphe minimal
def diskstraR(sc: int, fin: int, L: list, S: list, P: list) -> list: # sc pourra etre le pivot de l'etape
   return xxx

# fonction qui effectue l'appel principal de fonctions recursives pour l'algorithme de Dijkstra à l'aide de liste
#     renvoie une chaine de poids minimale entre les sommets ini et fin
# entree : deux sommets ini, fin et une liste simple L representant un graphe
# sortie : un entier et une liste de sommets
def diskstraRinit(ini: int, fin: int, L: list) -> tuple:
   return xxx

# Graphe d'un réseau de transport entre plusieurs capitales européennes : (capitales, heure)
L4=[[(12, 7), (5, 3)], [(20, 16), (6, 14)], [(7, 4), (21, 4)], [(24, 7), (18, 4), (17, 11), (0, 7)], [(17, 6), (13, 5)], [(17, 4)], [(10, 12)], [(21, 8)], [(7, 15)], [(16, 18)], [(23, 9), (15, 10)], [(14, 6), (17, 17)], [(17, 6)], [(5, 2), (17, 4)], [(19, 19), (4, 15), (17, 12)], [(9, 14)], [(3, 12), (0, 15)], [], [(0, 9), (13, 7), (17, 11), (24, 4)], [(17, 15), (4, 10), (1, 21), (20, 14), (24, 11)], [(6, 13), (24, 8)], [], [(8, 7)], [(3, 6), (15, 16), (9, 16)], [(17, 13)], [(8, 18), (2, 4)]]

# fin du fichier CPGE-graphes-G3.py