next up previous contents index
suivant: Programmation d'algoritmes les graphes monter: Programmation précédent: Exercices   Table des matières   Index

Programmation des types abstraits

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.


\begin{cadre}{utils.py}
\vspace{-1mm}
\verbatimtabinput{utils.py}
\end{cadre}

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.

Figure A.1: Graphe g1
\begin{figure}\begin{center}
\input g1.pstex_t
\end{center}\end{figure}

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.

Figure A.2: Graphe TGV
\begin{figure}\begin{center}
\input tgv.pstex_t
\end{center}\end{figure}

Nous présentons maintenant les deux modules vgraph et egraph qui implémentent respectivement le type centré-sommets et le type centré-arêtes.


\begin{cadre}{vgraph.py}
\vspace{-1mm}
\verbatimtabinput{vgraph.py}
\end{cadre}


\begin{cadre}{egraph.py}
\vspace{-1mm}
\verbatimtabinput{egraph.py}
\end{cadre}


next up previous contents index
suivant: Programmation d'algoritmes les graphes monter: Programmation précédent: Exercices   Table des matières   Index