L2 MIASHS : Graphes

Cours sur les graphes en L2 MIASHS - UCO de Rezé:
- Le Poly et les sources TEX du chapitre.
- Le Diapo
- la Page GITHUB du cours
- Le début de la classe graphe :

Python
#!/usr/bin/python
# -*- coding: utf-8 -*-
 
from graphviz import Graph
from dataclasses import dataclass
from typing import Dict, Set
 
 
@dataclass
class Graphe:
        """
        On définit un graphe à l'aide du dictionnaire des adjacents
        Par exemple :
        g = Graphe({{'1': {'2', '4', '3'}, '2': {'3'}, '3': {'4'}}})
        """
        dict_adj: Dict[str, Set[str]]
                
        def sommets(self) -> Set[str]:
                """
                Donne l'ensemble des sommets
                """
                s = set(self.dict_adj.keys())
                for v in self.dict_adj.values():
                                s |= v
                return s
        
        def adjacents(self, a):
                """
                Méthode pour avoir l'ensemble des adjacents d'un sommet
                """
                s = set([])
                if a in self.sommets():
                        if a in self.dict_adj:
                                s = set(self.dict_adj[a])
                        for v in self.dict_adj:
                                if a in self.dict_adj[v]:
                                        s |= {v}
                return s
        
        def __repr__(self):
                """ Affichage dans le terminal"""
                r = ''
                for v in sorted(list(self.sommets())):
                        r += ('\t' + v + ' -> { ')
                        for u in sorted(list(self.adjacents(v))):
                                r += (u + ' ')
                        r += '}\n'
                return r
                
        def dot(self, name: str = 'graphe') -> None:
                """
                Sortie graphique, ici au format PNG, à l'aide de Graphviz
                """
                d = Graph()
                d.node_attr.update(style='filled', color="#00ff005f")
                for v in self.dict_adj:
                        d.node(v)
                        for u in self.dict_adj[v]:
                                d.edge(v, u)
                d.render(name, view=True, format='png')

qui s'utilise ainsi:

Python
In [74]: g = Graphe({'1': {'2', '4', '3'}, '2': {'3'}, '3': {'4'}})
 
In [75]: g
Out[75]: 
        1 -> { 2 3 4 }
        2 -> { 1 3 }
        3 -> { 1 2 4 }
        4 -> { 1 3 }
 
In [76]: g.dot('graphe1')
 
In [77]: g.sommets()
Out[77]: {'1', '2', '3', '4'}
 
In [78]: g.adjacents('4')
Out[78]: {'1', '3'}

courtesy of webmatter.de