%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]] > > | [[Code et Développement/Programmation/Graphes/01_Introduction aux graphes\|← Introduction aux graphes]] | [[Code et Développement/Programmation/Graphes/03_Parcours en largeur (BFS)\|Parcours en largeur – BFS →]] | > |:---|---:| %% nav-fin %% # Représentation d'un graphe en Python Ce chapitre présente deux façons de représenter un graphe en Python : - la classe `Graph` du module `networkx`, qui sert à construire et à manipuler un graphe ; - un dictionnaire Python, qui suffit pour programmer les algorithmes des chapitres suivants. Le module `networkx` s'importe avec `import networkx as nx`. Il s'installe avec `pip install networkx` s'il est absent. Les blocs de code de cette page ne gardent que la construction des graphes. Les dessins sont faits par les composants à manipuler. ## Construire un graphe avec networkx ```python import networkx as nx G = nx.Graph() G.add_node("A") # ajoute un sommet G.add_edge("A", "B") # ajoute une arête, et ses sommets s'ils n'existent pas G.add_edge("B", "F") G.add_edge("C", "D") G.add_edge("C", "E") G.add_edge("C", "F") G.add_edge("D", "E") G.add_edge("F", "G") G.add_edge("F", "A") G.add_edge("G", "D") ``` Pour dessiner le graphe dans Python, `networkx` s'appuie sur le module `matplotlib` : `nx.draw(G, with_labels=True)`. La disposition des sommets change d'un dessin à l'autre. Le graphe reste le même. ```sq-graphe-dessin titre: Le graphe G arêtes: A-B, B-F, C-D, C-E, C-F, D-E, F-G, F-A, G-D ``` ## Graphe orienté La classe `DiGraph` construit un graphe orienté. L'ordre des sommets dans `add_edge` fixe le sens de l'arête : `G.add_edge("A", "B")` crée une flèche de A vers B, différente de `G.add_edge("B", "A")`. ```python G = nx.DiGraph() # seule cette ligne change G.add_edge("A", "B") # … mêmes arêtes que plus haut ``` ```sq-graphe-dessin titre: Le graphe G orienté arêtes: A>B, B>F, C>D, C>E, C>F, D>E, F>G, F>A, G>D ``` ## Graphe pondéré Le paramètre `weight` de `add_edge` donne un poids à l'arête. Cela fonctionne pour les graphes orientés et non orientés. ```python G = nx.Graph() G.add_edge("A", "B", weight=12.3) G.add_edge("B", "F", weight=6.1) # … une ligne par arête ``` ```sq-graphe-dessin titre: Le graphe G pondéré arêtes: A-B:12.3, B-F:6.1, C-D:4.2, C-E:17.0, C-F:9.8, D-E:3.3, F-G:6.2, F-A:14.5, G-D:10.6 ``` ## Opérations courantes `G.degree(x)` donne le degré du sommet x. `G.adj[x]` donne ses voisins. **À manipuler :** G est le graphe de référence non orienté. ```sq-affiche # G est le graphe de référence construit plus haut. print(G.degree("D")) print(sorted(G.adj["D"])) --- saisie: lignes réponse: 3\n['C', 'E', 'G'] explication: D est relié à C, E et G. sorted renvoie la liste des voisins dans l'ordre alphabétique. ``` `G.remove_node(x)` supprime un sommet et toutes ses arêtes. `G.remove_edge(x, y)` supprime une arête. **À manipuler :** cliquez sur un sommet ou une arête pour le retirer. Le code `networkx` correspondant s'affiche. ```sq-graphe-proprietes arêtes: A-B, B-F, C-D, C-E, C-F, D-E, F-G, F-A, G-D ``` `G.edges.data("weight")` parcourt les arêtes avec leur poids. Chaque arête apparaît une fois. ```python for sommet1, sommet2, poids in G.edges.data("weight"): print(sommet1, sommet2, poids) ``` Pour le graphe pondéré ci-dessus, ce programme affiche : ``` A B 12.3 A F 14.5 B F 6.1 F C 9.8 F G 6.2 C D 4.2 C E 17.0 D E 3.3 D G 10.6 ``` Les sommets sont parcourus dans leur ordre de création : A, B, F, C, D, E, G. L'ordre des lignes en dépend. ## Un graphe dans un dictionnaire Un graphe se stocke dans un dictionnaire Python : - chaque clé est un sommet ; - la valeur associée est l'ensemble de ses voisins. ```python D = { 'A': {'B', 'F'}, 'B': {'A', 'F'}, 'C': {'D', 'E', 'F'}, 'D': {'C', 'E', 'G'}, 'E': {'C', 'D'}, 'F': {'A', 'B', 'C', 'G'}, 'G': {'D', 'F'}, } ``` Dans un graphe non orienté, chaque arête apparaît deux fois : B est dans les voisins de A, et A dans les voisins de B. Ce dictionnaire suffit pour programmer un algorithme sur le graphe, sans `networkx`. `nx.Graph(D)` construit le graphe `networkx` correspondant, pour le dessiner. Un graphe se représente aussi par une **matrice d'adjacence**. La case de la ligne x et de la colonne y vaut 1 s'il existe une arête de x vers y, et 0 sinon. Pour un graphe non orienté, la matrice est symétrique. **À manipuler :** le dessin, la matrice et le dictionnaire représentent le même graphe. Cliquez sur une case de la matrice pour ajouter ou retirer une arête. ```sq-representation arêtes: A-B, B-F, C-D, C-E, C-F, D-E, F-G, F-A, G-D ``` Pour un graphe orienté, la valeur associée à un sommet est l'ensemble des sommets vers lesquels partent ses flèches. Un sommet d'où ne part aucune flèche a pour valeur l'ensemble vide, `set()`. Il ne faut pas écrire `{}`, qui crée un dictionnaire vide. ```python D = { 'A': {'B'}, 'B': {'F'}, 'C': {'D', 'E', 'F'}, 'D': {'E'}, 'E': set(), 'F': {'A', 'G'}, 'G': {'D'}, } G = nx.DiGraph(D) # DiGraph conserve l'orientation ``` La matrice d'un graphe orienté n'est pas symétrique. ```sq-representation arêtes: A>B, B>F, C>D, C>E, C>F, D>E, F>G, F>A, G>D bascule: oui ``` Pour un graphe pondéré, la valeur associée à un sommet est un dictionnaire. Ses clés sont les voisins. Ses valeurs sont des dictionnaires `{'weight': poids}`, au format de `networkx`. ```python D = { 'A': {'B': {'weight': 12.3}}, 'B': {'F': {'weight': 6.1}}, 'C': {'D': {'weight': 4.2}, 'E': {'weight': 17.0}, 'F': {'weight': 9.8}}, 'D': {'E': {'weight': 3.3}}, 'E': {}, 'F': {'G': {'weight': 6.2}, 'A': {'weight': 14.5}}, 'G': {'D': {'weight': 10.6}}, } G = nx.DiGraph(D) # nx.Graph(D) donnerait un graphe non orienté ``` Ici, `'E': {}` est correct : la valeur est un dictionnaire de voisins, vide. ```sq-representation arêtes: A>B:12.3, B>F:6.1, C>D:4.2, C>E:17.0, C>F:9.8, D>E:3.3, F>G:6.2, F>A:14.5, G>D:10.6 bascule: oui ``` ## Exemple : émetteurs et récepteurs Un réseau relie des émetteurs à des récepteurs. Une arête orientée va d'un émetteur vers un récepteur qui peut le capter. ```python D = { 'A': {'D', 'E', 'G'}, 'B': set(), 'C': {'B', 'D', 'E'}, 'D': set(), 'E': set(), 'F': {'B', 'E'}, 'G': set(), } ``` Un émetteur est un sommet d'où part au moins une flèche. Un récepteur est un sommet d'où ne part aucune flèche. Le programme suivant indique, pour chaque sommet, s'il est émetteur. ```python emetteur = dict() for sommet in D: emetteur[sommet] = len(D[sommet]) > 0 # au moins une flèche part du sommet print(emetteur) ``` Ce programme affiche : ``` {'A': True, 'B': False, 'C': True, 'D': False, 'E': False, 'F': True, 'G': False} ``` A, C et F sont des émetteurs. B, D, E et G sont des récepteurs. Le dessin ci-dessous les distingue par leur couleur. ```sq-graphe-dessin titre: Réseau d'émetteurs et de récepteurs arêtes: A>D, A>E, A>G, C>B, C>D, C>E, F>B, F>E couleurs: émetteurs ``` %% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]] > > | [[Code et Développement/Programmation/Graphes/01_Introduction aux graphes\|← Introduction aux graphes]] | [[Code et Développement/Programmation/Graphes/03_Parcours en largeur (BFS)\|Parcours en largeur – BFS →]] | > |:---|---:| %% nav-fin %%