Installation et imports

pip install networkx matplotlib numpy

Dans chaque fichier Python (ou cellule de notebook) :

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

Graphiz

Dans ce TP, on s’intéresse à différentes façons de représenter un graphe en informatique. L’objectif est de montrer que, quelle que soit la représentation utilisée, on peut produire une description DOT utilisable par Graphviz pour visualiser le graphe. Dit autrement : vous générez du texte DOT que vous collez dans l’éditeur en ligne :

  • Graphviz Online : https://dreampuf.github.io/GraphvizOnline
  • ou via la command dot

L’idée est surtout de vous forcer à manipuler matrice d’adjacence, liste d’incidence et liste d’adjacence, puis de reconstruire à la main un diagramme Graphviz cohérent.

Vous allez aussi écrire plusieurs itérateurs Python utilisant yield pour générer les arcs du graphe.

Introduction au format DOT (Graphviz):

Pour un graphe non orienté :

graph G {
    1 -- 2;
    1 -- 3;
    2 -- 4;
}

Pour un graphe orienté :

digraph G {
    A -> B;
    B -> C;
    A -> C;
}

Notez que vous pouvez utiliser un outils similaire mermaid.js que j’exploite sur ce site.

Pour cette partie, on considère le graphe suivant (non orienté) :

graph LR 1((1)) --- 2((2)) 1 --- 3((3)) 2 --- 3 2 --- 4((4)) 3 --- 5((5)) 4 --- 5

Travail demandé, en python :

  • Écrire la matrice d’adjacence de ce graphe
  • Écrire la liste d’incidence sommet–arêtes
  • Écrire la liste d’adjacence (successeurs de chaque sommet)
  • Attention aux indices : $i = x_i -1$

Vous devriez avoir respectivement 3 variables :

M = np.matrix([...]) # Matrice d’adjacence
A = [[]] # Liste d’adjacence
E = [[]] # Liste d’incidence sommet–arêtes
  • Ensuite on vous demande d’ecrire 3 iterateurs python avec yield.
def arcs_from_adjacency_matrix(M):
    yield 'A -- B'

def  arcs_from_adjacency_list(A):
    yield 'A -- B'

def  arcs_from_edge_list(E):
    yield 'A -- B'

Qui pourra etre donner a la fonction de generation du dot suivante :

def generate_dot(arc_iterator):
    print("digraph G {")
    for arc in arc_iterator:
        print(" ", arc)
    print("}")

Cette fonction pourra donc etre utiliser comme ceci :

generate_dot(arcs_from_adjacency_matrix(M))
generate_dot(arcs_from_adjacency_list(A))
generate_dot(arcs_from_edge_list(E))
  • Comprarer les differentes versions, qui doivent etre identiques.
Plus d’info sur yield

yield est un mot-clé qui permet de créer un générateur.
Un générateur renvoie les valeurs une par une, au lieu de tout renvoyer d’un coup.

  • yield renvoie une valeur.
  • La fonction se met en pause.
  • Lors de la prochaine demande, elle reprend après le yield.
  • yield transforme une fonction en générateur.
  • Les valeurs sont produites progressivement.
def mots():
    yield "bonjour"
    yield "python"
    yield "monde"

for mot in mots():
    print(mot)

Résultat :

bonjour
python
monde