Connexion élèves

Choisir le(s) module(s) à installer :

Les graphes en Python

Après toutes ces notions de base, place à la manipulation de graphes en Python.

Le TAD GRAPHE

Quelles sont les primitives dont nous avons besoin pour le TAD graphe ?

On peut aussi envisager :

Une structure très riche ! Nous n'aurons pas toujours besoin de toutes ces fonctionnalités, mais nous allons réfléchir à comment implémenter les principales.

Implémentation du TAD GRAPHE

Vous allez implémenter les primitives du TAD Graphe.
L'objectif sera à la fin de ce chapitre de disposer d'un module graphe prêt à l'importation dans un script, et qui permettra de manipuler les graphes.

Vous modéliserez un graphe par un dictionnaire des listes d'adjacence de ce graphe.

Pour simplifier, on considérera tous les graphes comme orientés, et non pondérés.

Vous pourrez utiliser des assertions pour tester les préconditions des primitives.

Primitives

Le but est d'écrire une classe Graphe, dont le seul attribut sera le dictionnaire des listes d'adjacence du graphe.

Les seules primitives à implémenter seront :

Implémentation

Vous trouverez ci-dessous la signature des différentes méthodes à implémenter; à vous de compléter le code :

class Graphe: def __init__(self, S = None): '''Méthode qui crée un graphe vide ou à partir d'une liste de sommets. Entrée : S = la liste des sommets du graphe ( None par défaut ) ''' pass def ajoute_sommet(self, id: str): '''Méthode qui ajoute un unique sommet au graphe. Entrée : id = l'identifiant du sommet dans le graphe Lève une exception au cas où l'identifiant existe déjà dans le graphe ''' pass def ajoute_arc(self, id1: str, id2: str): '''Méthode qui créé un arc entre deux sommets. Entrées : id1 = identifiant du sommet de départ de l'arc id2 = identifiant du sommet de fin de l'arc Lève une exception au cas où l'identifiant d'un des sommets n'existe pas dans le graphe ''' pass def ajoute_arete(self, id1: str, id2: str): '''Méthode qui créé une arête entre deux sommets. Entrées : id1 = identifiant du sommet de départ de l'arc id2 = identifiant du sommet de fin de l'arc Lève une exception au cas où l'identifiant d'un des sommets n'existe pas dans le graphe ''' pass def adjacents_de(self, id: str)->list: '''Méthode qui renvoie la liste des sommets adjacents (voisins ou successeurs ) d'un sommet donné. Entrée : id = l'identifiant du sommet Sortie : la liste des sommets adjacents du sommet passé en paramètre Lève une exception si le sommet n'existe pas dans le graphe. ''' pass

Avant de passer à la suite, réaliser quelques tests unitaires sur le code que vous venez d'écrire pour vous assurer de son bon fonctionnement.

SOLUTION

Une fois le code de la classe GrapheD mis au point, enregistrez-le seul ( sans les tests ) dans un fichier nommé graphe.py, que l'on pourra ensuite importer dans un nouveau script.

Autres fonctionnalités

Vous allez maintenant utiliser le code que vous venez d'écrire en écrivant quelques fonctions qui utiliseront la classe Graphe.

Ces fonctions pourraient éventuellement être codées comme méthodes de cette classe car elles lui apportent des fonctionnalités plus étendues, mais nous choisirons de laisser la classe réduite à ses primitives de base car ces fonctionnalités ne sont pas toujours nécessaires.

Les fonctions suivantes devront donc être écrites dans un nouveau script, qui importera le module graphe. Attention donc à ce que le fichier graphe.py soit bien dans le même répertoire que votre nouveau script, ou alors pensez à l'importer au préalable dans l'éditeur si vous travaillez en ligne.

  1. Création d'un graphe :

    instancier un objet Graphe, et donner lui quelques sommets et quelques relations ( vous pouvez prendre un exemple aléatoire des exercices précédents 😏 ).

  2. Renvoi de la matrice d'adjacence d'un graphe :

    Écrire une fonction vers_matrice qui :

    • prend comme paramètre un objet Graphe
    • renvoi la liste des sommets et la matrice d'adjacence du graphe

    Bien entendu, le graphe ne devra pas être vide...

    Ce problème n'est pas si évident...voici un algorithme qui devrait vous aider un peu :

    
sommets ← liste des sommets ( comment la déterminer ? )
adjacence ← liste de listes de n x n éléments tous égaux à 0 ( combien de lignes ? de colonnes ? comment le déterminer ? )

pour chaque ligne de adjacence :
	id1 ← sommet correspondant à la ligne ( comment le trouver ? )
	pour chaque colonne de adjacence :
		id2 ← sommet correspondant à la colonne ( comment le trouver ? )	
		si id2 est adjacent à id1 :
				adjacence[ligne][colonne] = 1

    Oui, c'est du O(n2) ! Pour une très grande matrice, il faudrait sans doute trouver mieux ( ça existe, mais les maths là-derrière ne sont pas au programme...).

    from graphe import Graphe def vers_matrice(G: Graphe)->list, list: '''Fonction qui renvoie la matrice d'adjacence du graphe à partir d'une instance de GrapheD. Entrée : G = objet de type Graphe Sorties : la liste des sommets, et la matrice d'adjacence Lève une exception si le graphe est vide. ''' pass
  3. Création d'un graphe à partir d'une matrice d'adjacence :

    L'exercice inverse : écrire une fonction vers_graphe qui :

    • prend comme paramètres la liste des sommets du graphe et sa matrice d'adjacence
    • renvoie un objet Graphe créé à partir de ces paramètres
    from graphe import Graphe def matrice_vers_graphe(S:list, M:list)->Graphe: '''Fonction qui crée un graphe à partir de la liste de ses sommets et de sa matrice d'adjacence Entrée : S = liste des sommets du graphe M = matrice d'adjacence Sortie : instance de Graphe ''' pass

SOLUTION

Visualisation d'un graphe

Présentation : le module graphviz

Ce module fournit deux classes : Graph pour un graphe non orienté, et Digraph pour un graphe orienté.


from graphviz import Graph # ou Digraph

On peut alors créer un objet Graph ( ou Digraph ) :


g = Graph() # ou : g = Digraph()

Ces deux classes ont de nombreux attributs qui gèrent les propriétés du graphe, notamment le modèle de rendu du graphe qui affectera son aspect ( certains modèles donnent un meilleur résultat visuel sur certains graphes ) ou alors le type de sortie ( format PDF ( par défaut ), PNG ou SVG par exemple avec Pyzo ).
vous pouvez consulter l'API de ces deux classes sur cette page pour plus d'informations sur les deux classes, ainsi que celle-ci pour la présentation des différents modèles de rendu.

On peut ensuite définir la liste des sommets du graphe, passée en argument à la méthode nodes(), ou alors les définir un par un avec la méthode node():


g.nodes(['A', 'B', 'C', 'D'])
g.node('E')

chaque sommet doit avoir un identifiant unique dans le graphe sous forme d'une chaîne de caractère(s), qui constituera de plus l'étiquette par défaut du sommet lors de l'affichage du graphe.

De la même manière, on définira la liste des arêtes/des arcs avec les méthodes edges() ou edge() :


g.edges(['AB', 'CD']) # crée un arc A->B et un arc C->D ( des arêtes pour un objet Graph bien sûr...)

g.edge('E', 'A') # pour cette méthode, les sommets doivent être séparés.

L'ordre d'écriture des identifiants des nœuds indique le sens de l'arc dans le cas d'un graphe orienté.

Il se trouve que la seule liste des arêtes/des arcs peut suffire pour définir le graphe dans graphviz !

Pour afficher le graphe, on utilise alors la méthode view() :


g.view()

Cela créera le graphe et lancera le programme adapté au format de sortie choisi ( pour Pyzo, le lecteur PDF par défaut, ou en ligne, un affichage à droite de l'éditeur ).

Vous pouvez essayer ce petit code et le modifier pour prendre en main le module :

from graphviz import Digraph g = Digraph() g.edge('A', 'B', label='5') # on peut rajouter une étiquette sur un arc/une arête g.edge('A', 'C', label='2') g.edge('A', 'D', label='6') g.edge('C', 'D', label ='9') g.edge('B', 'D', label = '3') g.edge('D', 'B', label = '1') g.view(engine = 'dot')

Le modèle de disposition peut être spécifié par l'argument engine de la méthode view(); par défaut, c'est le moteur dot qui est utilisé si l'on ne précise rien.
Pour Pyzo, utilisez help() pour connaître les autres modèles; en ligne, les modèles disponibles sont circo, dot, fdp, neato, osage et twopi.

Une fonction d'affichage de graphe

Compléter la classe Graphe avec une méthode dessine qui utilise le module Graphviz pour visualiser une instance de la classe.

from graphviz import Graph, Digraph class Graphe: ... def dessine(self): """Dessine un graphe à l'aide du module Graphviz.""" pass ...

SOLUTION