CONCEVOIR DES ALGORITHMES GENERIQUES POUR LA RECHERCHE OPERATIONNELLE Package de test

Le rapport de recherche discute de différents problèmes rencontrés dans la conception d'algorithmes réutilisables, extensibles, pour la recherche opérationnelle. Il explique comment utiliser les concepts orientés objet et la notion de généricité pour concevoir des algorithmes qui sont indépendants des structures de données et des algorithmes qu'ils manipulent, mais pouvant néanmoins interagir fortement entre eux. Le principal but est d'expliquer comment concevoir des algorithmes qui sont à la fois génériques et efficaces. Les solutions discutées dans ce rapport ont été implémentées dans le langage C++, et un package de test est proposé pour permettre une comparaison de l'efficacité des différentes conceptions.

Le package est décomposé en plusieurs fichiers, correspondant à la discussion dans le rapport. Il implémente trois structures de graphe et la plupart des tests sont réalisés en utilisant un algorithme de plus court chemin.

• common.hpp
  Contient les éléments communs du package.

• data.hpp
  Définit des données qui seront portées par les structures de graphe.

• iterator.hpp
  Définit des itérateurs sur les structures de graphe.

• graph.hpp - graph.cpp
  Définit une structure de graphe non-template générique.

• tgraph.hpp
  Définit une structure de graphe template.

• extension.hpp
  Définit un mécanisme d'extension pour les structures de données.

• extend_tgraph.hpp
  Définit une structure de graphe template extensible.

• visitor.hpp
  Définit des visiteurs pour l'algorithme de plus court chemin.

• shortest_path.hpp
  Définit l'algorithme de plus court chemin pour les diverses approches d'extension.

• test.cpp
  Contient la procédure de test des divers concepts présentés dans le rapport.

La première série de tests compare l'efficacité des approches par héritage et par généricité pour concevoir une structure de graphe. L'impact de l'usage des itérateurs est également mesuré.

• Test (1): Teste la vitesse d'accès à la méthode getFlow() de la donnée d'un arc dans une structure de graphe non-template. L'indispensable conversion descendante est réalisée par une conversion dynamique.

• Test (2): Teste la vitesse d'accès à la méthode getFlow() de la donnée d'un arc dans une structure de graphe non-template. L'indispensable conversion descendante est réalisée par une conversion statique.

• Test (3): Teste la vitesse d'accès à la méthode getFlow() de la donnée d'un arc dans une structure de graphe template.

• Test (4): Teste la vitesse d'accès à la méthode getFlow() de la donnée d'un arc dans une structure de graphe template utilisant les itérateurs.

La deuxième série de tests compare l'efficacité des approches par méthode virtuelle, par visiteur abstrait et par interface de visiteur pour étendre un algorithme. L'algorithme de plus court chemin est étendu pour calculer soit le plus court chemin en distance, soit le plus court chemin en temps.

• Test (a): Teste la vitesse de l'algorithme de plus court chemin avec l'approche par méthode virtuelle.

• Test (b): Teste la vitesse de l'algorithme de plus court chemin avec l'approche par visiteur abstrait.

• Test (c): Teste la vitesse de l'algorithme de plus court chemin avec l'approche par interface de visiteur.

• Test (d): Teste la vitesse de l'algorithme de plus court chemin avec l'approche classique (i.e. deux algorithmes séparés).

La troisième série de tests mesure l'impact sur l'efficacité du mécanisme d'extension proposé dans le rapport pour permettre aux algorithmes d'étendre des structures de données sans briser leur encapsulation. Les tests (3), (4) et (a) à (d) sont à nouveau réalisés, afin de mesurer l'impact du mécanisme d'extension quand il est disponible mais pas effectivement utilisé. Ensuite, des tests utilisant le mécanisme d'extension sont réalisés.

• Test (e): Teste la vitesse de l'algorithme de plus court chemin avec l'approche par interface de visiteur et le mécanisme d'extension (utilisant la conversion dynamique pour accéder aux extensions).

• Test (f): Teste la vitesse de l'algorithme de plus court chemin avec l'approche par interface de visiteur et le mécanisme d'extension (utilisant la conversion statique pour accéder aux extensions).

Voici les résultats (en secondes) obtenus par un processeur Athlon XP 1800+, avec un compilateur GCC 3.2 sous l'environnement Cygwin, et l'option -O2 activée.

Vous pouvez télécharger le du package et réaliser vos propres tests. Nous ne l'avons vérifié que sur des compilateurs GCC, mais il doit fonctionner sur d'autres, avec seulement quelques modifications mineures (comme la façon de mesurer le temps).