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

################################
#                              #
#         Graphes : G2         #
#                              #
################################

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 : G2 '''
#################################################################

# ensemble des sommets
S=xxx
# ensemble des aretes sous forme d'une liste simple
L=xxx
# pour les tests de nombreSommets(), listeSommets() et convertListeMatrice()
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"))]

################################
## G2 : à l'aide d'une matrice #
################################

# renvoie le nombre de sommets d'un graphe suppose connexe
# entree : liste simple representant un graphe connexe expl : L=[[(1,3),(2,5),(3,1)],[(3,4),(4,3)]]
# sortie : entier
def nombreSommets(L: int) -> int:
   return xxx

# renvoie la liste des sommets d'un graphe suppose connexe
# entree : liste simple representant un graphe connexe
# sortie : liste de sommets
def listeSommets(L: list) -> list:
   return xxx

# renvoie une matrice représentant une liste simple
# entree : une liste simple expl : L=[[(1,3),(2,5),(3,1)],[],[(3,4),(4,3)]]
# sortie : une matrice A expl : A=[(0,1,3),(0,2,5),(0,3,1),(2,3,4),(2,4,3)]
def convertListeMatrice(L: list) -> list:
   return xxx

# renvoie la matrice d'adjacence d'un graphe défini par ses Sommets et ses Aretes
# entree : une liste S de sommets et une matrice A d'aretes (si,sj)
# sortie : une matrice carre symetrique de taille |S|
def matriceAdjacenceP(S,A):
   return xxx

# renvoie le sommet parmi S qui possède un poids (wi) minimal
# entree : une liste S de sommets et une liste P de couples (sc,wi)
# sortie : un sommet de poids minimal spm appartenant à S
def sommetPoidsMin(S: list, P: list) -> int:
   mini=float("inf") # a garder
   xxx
   return xxx

# effectue l'algorithme de Dijkstra à l'aide de matrice
#    et 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 : une liste de sommets et un entier
def diskstraMat(ini: int, fin: int, L: list) -> tuple:
   return xxx

# Graphe d'un réseau de transport entre plusieurs capitales sud-américaines : (capitales, heure)
L3=[[(3,14),(6,16),(8,27),(9,22)],[(4,24),(5,48),(7,21)],[(4,78),(6,34),(9,36)],[(6,5),(8,16)],[(7,42)],[(7,29),(8,40),(9,33)],[],[],[(9,28)]]

# fin du fichier CPGE-graphes-G2.py