On vous demande de réaliser une classe Graphe. On supposera :
- Que les graphes sont non orientés, simples, non pondérés,
- Que les sommets sont numérotés par des entiers.
Initialisation de la classe
Construire la base de la classe Graphe.
- Vous lui incorporerez un constructeur,
- vide pour l'instant (ne contenant que pass),
- et sans argument (autre que self).
- Vous n'oublierez pas de documenter la classe (docstrings).
- Cette classe possédera deux attributs privés :
- _sommets : la liste des sommets (une liste d'entiers),
- _aretes : la liste des arêtes (une liste de couples de sommets, i.e. une liste de couples d'entiers).
Amélioration du constructeur
On souhaite maintenant réaliser un constructeur digne de ce nom...
def __init__(self):
devient
def __init__(self, sommets = [], aretes = []):
Noter que :
- La valeur de l'argument sommets sera passée à l'attribut _sommets.
- La valeur de l'argument aretes sera passée à l'attribut _aretes.
- On incorporera des tests au constructeur, tels que :
- Tester si sommets est bien constitué d'entiers, tous différents.
- Tester si aretes est bien constitué de couples d'entiers, tous différents.
- Tester si les sommets présents dans aretes sont bien présents dans sommets
- Tester si aretes ne contient pas de boucle.
Création d'un main
On ajoutera un main à son module, qui testera la création d'un objet Graphe.
Ce main commencera par :
if __name__ == ' __main__ ':
Ajout de quelques méthodes de base
On va étoffer un peu cette classe, avec quelques méthodes raisonnables. Créer les méthodes suivantes :
- ordre(), qui renverra le nombre de sommets du graphe.
- get_sommets(), accesseur qui renverra la liste des sommets.
- get_aretes(), accesseur qui renverra la liste des arêtes.
- get_degre(), qui renvoie
- le degré du sommet passé en argument, s'il y a un argument,
- le degré du graphe, sinon.
- est_connecte(i,j), qui renvoie un booléen (vrai si $i$ est $j$ sont connectés par une arête).
Ajout de sommets, d'arêtes
Faire les méthodes suivantes, qui permettent d'ajouter des sommets :
- add_sommet(i), qui ajoute le sommet $i$,
- add_sommets_from(L), qui ajoute les sommets contenus dans la liste $L$.
Faire les méthodes équivalentes associées aux arêtes, ainsi que celles permettant de supprimer un (ou des) sommet(s)/arête(s).
On veillera à tester que :
- le sommet ajouté n'existe pas déjà,
- le sommet à retirer existe bien,
Idem pour les arêtes. On pourra, auquel cas, et au choix : lever une exception, ou ignorer la demande.
Composantes connexes
Faire une fonction qui permet d'extraire les composantes connexes d'un graphe.
On pourra faire un parcours en largeur :
- prendre un premier sommet, chercher les sommets qui lui sont connectés, puis les sommets qui sont connectés à ces derniers, etc.
- Quand il n'y a plus de nouveaux sommets connectés, on renvoie la liste obtenue, qui correspond à une composante connexe du graphe.
- On recommence avec les sommets restants, jusqu'à épuisement complet de la liste des sommets.
Méthodes est_connexe, est_complet
Réalisez les méthodes :
- est_connexe, qui renvoie vrai si et seulement si le graphe possède une unique composante connexe,
- est_complet, qui renvoie vrai si et seulement si chaque sommet est connecté à tous les autres sommets.
Méthode est_eulerien
Faire une méthode est_eulerien, qui renvoie évidemment vrai si et seulement si le graphe est eulérien.
On rappelle le résultat d'Euler : un graphe est eulérien si et seulement si il est connexe, avec tous ses sommets de degré pair.
Représentations
- Faire les méthodes :
- get_matrice_incidence,
- get_matrice_adjacence,
- get_liste_adjacence,
qui renverront respectivement les matrices d'incidence, d'adjacence, et la liste d'adjacence du graphe instancié.
- Ecrire les setteurs associés.
On pourra vérifier si les arguments passés aux setteurs conviennent (par exemple, une matrice d'adjacence doit être carrée, symétrique, constituée uniquement de 0 et de 1).
Nombres de chemins :
Faire une méthode nombre_chemins(i,j,k), qui renvoie le nombre de chemins de longueur $k$ reliant $i$ à $j$.
Arbre :
Faire une méthode qui renvoie vrai si et seulement si le graphe est un arbre : connexe, avec $n-1$ arêtes.
Finalisation
On finalisera sa classe :
- documentation complète de la classe, et de toutes les méthodes publiques,
- property là où il faut, les méthodes associées devenant privées,
- etc.
avant de rédiger un main complet.