Pour pouvoir utiliser les algorithmes programmés au chapitre 13, il est nécessaire de disposer d'une implémentation Python des types abstraits centré-arêtes et centré-sommets. Nous donnons ci-dessous un exemple d'implémentation possible pour chacun des deux types abstrait.
Les deux types abstraits centré-sommets et centrés-arêtes utilisent la même classe c_edge pour décrire les arêtes et ont en commun les opérations NB_NODES(G, i), EDGE_END(a, i), MARK_NODE(s), UNMARK_NODE(s), NODE_MARKED(s), MARK_EDGE(a), UNMARK_EDGE(a), FOLLOW_EDGE(s, a). Ces parties communes sont regroupées dans le module graph.
Les deux modules vgraph et egraph implémentent respectivement
les deux types abstraits centré-sommets et centré-arêtes.
Après importation des parties communes (from graph import *
)
les classes c_node représentant un sommet et c_graph
représentant un graphe du type correspondant sont suivies des opérations
spécifiques au type. À la fin des modules, l'instruction
execfile("utils.py")
inclut le code du fichier utils.py
.
Ce fichier contient des opérations utiles qui n'utilisent que la partie commune aux deux types abstraits.
En particulier, la fonction make_graph(paths) permet de fabriquer facilement un graphe du type chargé à partir d'une liste contenant pour chaque sommet une liste constituée du sommet lui-même suivi de sommets adjacents. Par exemple, l'instruction g1.py construit le graphe de la figure A.1.
Pour obtenir une arête étiquetée entre le sommet et un sommet adjacent, il suffit de remplacer le sommet adjacent pas le couple constitué du sommet adjacent et de l'étiquette de l'arête. Par exemple, l'instruction tgv.py construit le graphe de la figure A.2.
Nous présentons maintenant les deux modules vgraph
et egraph
qui implémentent respectivement le type centré-sommets et le type centré-arêtes.