Graphes

I/ Graphes orientés

1) Comme dictionnaire Python

Il est parfois nécessaire d'associer plusieurs valeurs à une même clé d'un dictionnaire Python. On peut le faire en prenant pour valeurs des listes, comme ici :

graphe = { 'A': ['B','C'],    
	   'B': ['A'],        
	   'C': ['A','B'] }

2) Définitions

Lorsque

• Les valeurs d'un dictionnaire sont des listes
• tous les éléments de ces listes sont des clés du dictionnaire

Les clés du dictionnaire s'appellent les sommets du graphe :

sommets = graphe.keys()
print(sommets)

dict_keys(['B', 'C', 'A'])

La valeur associée au sommet A s'appelle liste d'adjacence de ce sommet :

def liste_adjacence(sommet):
	return graphe[sommet]
print(liste_adjacence('A'))

['B', 'C']

Comme B est dans la liste d'adjacence de A, on dit que A et B sont adjacents, ou qu'il y a un arc allant de A vers B.

On dessine le graphe ci-dessus avec des flèches entre les sommets, pour représenter les arcs :

En machine, on utilise plutôt des listes de listes :

II/ Dessin

Pour dessiner un graphe orienté, on utilise un objet de la classe Digraph. Un tel objet peut être construit si on a importé la classe depuis le module graphviz. L'installation de ce module se fait en bash par

 sudo apt-get install graphviz
 pip3 install graphviz

1) Création du graphe

Pour créer un graphe orienté graphe, on fait

from graphviz import Digraph
graphe = Digraph(format='png')

On dit que le graphe est instancié. À ce stade il n'a pas encore d'attributs (couleur, sommets, arcs...) :

digraph {
}

2) Ajout des sommets

Pour lui ajouter des sommets, on utilise une méthode appelée node :

graphe.node('A','A')
graphe.node('B','B')
graphe.node('C','C')

Le deuxième élément du couple est ce qui apparaîtra dans le dessin. Ce n'est pas nécessairement le même que le nom interne (premier élément du couple). Après ces trois appels à la méthode node le graphe ressemble à ceci :

digraph {
	A [label=A]
	B [label=B]
	C [label=C]
}

3) Ajout des arcs

De même, le graphe possède une méthode appelée edge qui permet d'ajouter un arc. Dans graphviz un arc est représenté par un couple dont le premier élément est le nom du sommet dont part la flèche, et le second élément est le nom (interne) du sommet d'arrivée :

graphe.edge('A','B')
graphe.edge('A','C')
graphe.edge('B','A')
graphe.edge('C','A')
graphe.edge('C','B')

L'affichage du graphe montre les arcs sous forme de flèches :

digraph {
	A [label=A]
	B [label=B]
	C [label=C]
	A -> B
	A -> C
	B -> A
	C -> A
	C -> B
}

4) Dessin du graphe

Le dessin (ou « rendu ») du graphe orienté se fait par sa méthode render, à qui on fournit le nom du graphe :

graphe.render('ABC')

Cela a pour effet d'enregistrer dans le dossier courant un fichier nommé ABC.png et contenant l'image ci-dessus.

III/ Matrice d'adjacence

On peut représenter l'adjacence dans un tableau comprenant un 1 à la ligne correspondant à un sommet et la colonne correspondant à un sommet qui lui est adjacent. Par exemple

Un tel tableau s'appelle une matrice d'adjacence. On peut la coder en Python par une liste de listes :

matrice = [[0,1,1],     
           [1,0,0],     
           [1,1,0]]

IV/ Graphes non orientés

1) Définitions

Lorsque, chaque fois qu'il y a un arc entre A et B, il y en a aussi entre B et A, on dit que le graphe est non orienté. Dans ce cas, plutôt que le dessiner comme ceci :

on ne représente pas les flèches, devenues inutiles :

Voici la représentation machine de ce graphe non orienté :

On utilise le mot « graphe » pour les graphes non orientés. Pour un graphe (non orienté), on ne parle plus d'arcs mais d'arêtes. On représente les arêtes par des traits, pas forcément droits.

2) Matrice d'adjacence

La matrice d'adjacence d'un graphe (non orienté) est symétrique, c'est-à-dire qu'elle ne change pas si on échange ses lignes et ses colonnes. Exemple :

Représentation machine de la matrice :

3) Dessin

graphviz possède également une classe Graph pour dessiner un graphe (non orienté). Le début d'un graphe se fait donc ainsi :

from graphviz import Graph
graphe = Graph(format='png')

Le reste se fait comme avec les graphes orientés.