*** LONGEST PATH *** Il s'agit de trouver le plus long chemin simple d'un graphe G supposé connexe, quoique cette dernière hypothèse ne soit pas nécessaire. Un chemin simple est un chemin qui ne passe pas deux fois par le même sommet. On commence par calculer une décomposition particulière du graphe à l'aide d'un parcours en profondeur du graphe depuis un sommet racine arbitraire. Les sommets correspondant à une feuille lors du parcours sont ordonnés dans l'ordre où ils ont été visités. Et on note B_i le chemin allant de la i-ème feuille à la racine. Le temps de l'algorithme est très dépendant de la taille de la plus longue branche. Une optimisation consiste donc à choisir une racine produisant la plus petite profondeur. En notant G_i = B_1 ∪ ... ∪ B_i le graphe composé de l'union des i premières branches, il vient que G = G_f = B_1 ∪ ... ∪ B_f où f est le nombres de feuilles. C'est la décomposition qui nous intéresse. Pour des raisons techniques, on ajoute à cette décomposition deux branches fictives vides: B_0 et B_{f+1}. L'observation importante liée au parcours en profondeur est que les seules arêtes de G connectant un sommet de B_i avec un sommet de B_j sont dans l'intersection B_i ∩ B_j. Ainsi tout chemin allant de G_i à G\G_i doit couper B_i ∩ B_{i+1}. On dit pour cela que B_i ∩ B_{i+1} est un séparateur. C'est en fait la seule propriété qui nous intéresse, et le fait que B_i est un chemin ne va plus jouer aucun rôle. La décomposition de G en union de B_i s'appelle une décomposition en chemin. On considère un ensemble B de sommets de G. On notera B* la clique sur B, le graphe composé de B et de toutes les arêtes possibles entres les sommets de B. Soit P un chemin de G ∪ B*. P contient potentiellement des arêtes de B* qui ne sont pas dans G. La ** valeur de P **, notée valeur(P), est simplement de nombre d'arêtes de G que contient P. On considère les chemins comme étant orientés, les chemins 1-2-3 et 3-2-1 étant considérés comme deux objets différents. La ** signature de P ** vis à vis de (G,B) est la liste ordonnée des sommets de B ∩ P obtenue en parcourant P, chaque sommet v ∈ B ∩ P étant "signé" par les arêtes de G ∩ P incidentes à v. Prenons un exemple de chemin P dans un graphe G d'une dizaine de sommets et pour un ensemble B = {1,...,7}: P = 0-3-9-1+5-8-2+4+6-7 Ici on note i-j une arête de G entre les sommets i et j, et i+j une non-arête de G, c'est-à-dire une arête de B* qui n'est pas dans G. Les sommets de B sont visités par P dans l'ordre 3,1,5,2,4,6,7. En notant les arêtes/non-arêtes entrantes et sortantes sur chacun des sommets cela donne la signature (-3-,-1+,+5-,-2+,+4+,+6-,-7) que l'on peut compacter en: S = -3-1+5-2+4+6-7 Plusieurs chemins peuvent avoir la même signature. La valeur d'une signature S, notée valeur(S), est le maximum des valeurs des chemins ayant pour signature S. La signature vide S=() est celle d'un chemin qui ne contient aucun sommet de B. Cette signature n'est pas à négliger puisqu'il est possible que le plus long chemin n'utilise aucun sommet de B. C'est aussi la seule signature possible lorsque B={}. On se servira de la signature de ** l'opposé ** d'un chemin P pour (G,B). Il s'agit de la signature du chemin où les rôles des arêtes et non-arêtes sont inversés. Dans l'exemple P=0-3-9-1+5-8-2+4+6-7, le chemin opposé est 0+3+9+1-5+8+2-4-6+7 dont la signature est +3+1-5+2-4-6+7 ce qui correspond à la signature d'origine où l'on a simplement inversé les signes. Le nombre maximum de signatures possibles pour (G,B) ne dépend que de la taille de B (supposée petite), alors que le nombre de chemins dépend de G. Le codage exact de la signature aura finalement assez peu d'impact sur les performances de l'algorithme du moment qu'elle est représentable par une structure (liste ou tableau) de taille O(k). Le principe de l'algorithme est de maintenir, par programmation dynamique, une table T_i des signatures de tous les chemins possibles de (G_i,B_i ∩ B_{i+1}). Donc les entrées de T_i ressemblent à: T_i[S] = valeur(S) où S est la signature d'un des chemins du graphe G_i ∪ (B_i ∩ B_{i+1})*. Au départ, pour i=0, la table T_0 est vide puisque G_0 et B_0 sont vides. L'objectif est de calculer T_f qui par définition est la table des signatures de tous les chemins de (G_f,B_f ∩ B_{f+1}) = (G,{}). Notez que T_f ne contient qu'une seule signature, la signature vide qui représente donc la solution cherchée. Il ne reste donc qu'à expliquer comment calculer T_i à partir de T_{i-1}. Pour alléger la description, on pose X et Y les séparateurs respectivement entre G_{i-1} et G_i, et G_i et G_{i+1}. Donc X = B_{i-1} ∩ B_i et Y = B_i ∩ B_{i+1}. On pose aussi H le graphe B_i dans lequel on a supprimé toutes les arêtes qui sont dans G_{i-1}. Il va falloir générer tous les chemins P du graphe H' = X* ∪ H ∪ Y*, c'est-à-dire le graphe H où les deux séparateurs ont été complété. De manière exhaustive, il faut pour chaque sommet r et chaque longueur t<|V(H)|, générer tous les chemins de H' commençant en r et de longueur t. Pour chaque chemin P de H', on calcule sa signature S vis à vis de (X* ∪ H,Y). Donc ici les non-arêtes de P sont celles de Y*. Celles de X* sont considérées comme appartenant au graphe. Dans un premier temps on fait donc comme si P pouvait utiliser librement les arêtes de X* qui ne sont évidemment pas dans H (c'est dans la définition de H). Ces arêtes correspondent potentiellement à des chemins de G_{i-1} dont la longueur totale se trouve justement dans T_{i-1}, si ces chemins existent bien dans G_{i-1}. Pour le savoir et obtenir le plus long, on calcule la signature S' opposée de P vis à vis de (H ∪ Y*,X). Donc ici sont considérées comme arêtes de P celles de X* et les non-arêtes celles de H ∪ Y*. Si S' n'existe pas dans T_{i-1}, alors P ne peut pas être étendu dans G_{i-1} et on a rien à faire. P ne contribue pas à la valeur de S dans T_i, il faudra trouver un autre chemin pour cela. Sinon, on "combine" T_{i-1}[S']=valeur(S') avec valeur(P) pour créer ou mettre à jour T_i[S], en faisant attention aux détails. Parmi ces détails, il y a les signatures vides et les chemins commençant et/ou terminant dans X: il est possible que le chemin de G correspondant commence réellement "avant X", dans G_{i-1}\X. Pour avoir une complexité raisonnable, on s'aperçoit qu'il est important de pouvoir chercher et insérer rapidement une signature dans une table. Il faut viser une complexité au plus logarithmique en le nombre de signatures stockées. Une table de hachage ou un arbre AVL sont alors les bienvenues. Pour la gestion mémoire, on s'aperçoit aussi qu'il n'y a que deux tables à maintenir: celle déjà calculée (T_{i-1}) et la prochaine (T_i).