Graphes orientés, DAG et ordonnancement

Ce que les flèches changent

Dans un graphe orienté, chaque sommet a deux voisinages distincts, et la plupart des erreurs viennent de leur confusion.

Sur un graphe orienté, la somme des degrés sortants vaut le nombre d'arcs, et la somme des degrés entrants aussi. Il n'y a pas de facteur 2 : chaque arc n'est compté qu'une fois de chaque côté.

Un plan de circulation en sens uniques en donne l'exemple le plus parlant.

Le dessin est d'un seul tenant, mais un véhicule parti du port n'a aucun moyen de rejoindre la gare : le graphe est faiblement connexe, pas fortement. Pour tester la forte connexité, deux parcours suffisent, depuis un même sommet quelconque : l'un en suivant les arcs, l'autre en les remontant, c'est-à-dire sur le graphe inverse du chapitre 2. Le graphe est fortement connexe si et seulement si chacun des deux atteint tous les sommets : tout sommet peut alors rejoindre le sommet de départ, puis n'importe quel autre. Ici, depuis Gare, on atteint tout en suivant les arcs, mais en les remontant on n'atteint ni Port ni Usine. Les groupes de lieux qui communiquent dans les deux sens, coloriés sur la figure, sont les composantes fortement connexes de la fin du chapitre.

Les DAG

C'est la structure des dépendances, et elle est partout : tâches d'un projet, prérequis d'un cours, modules d'un programme, cellules d'un tableur, commits d'un dépôt Git, étapes d'une chaîne d'intégration.

Un circuit dans un graphe de dépendances est une contradiction. Si A doit être fait avant B, B avant C, et C avant A, aucun ordre n'existe. Ce n'est pas un problème d'algorithme, c'est un problème d'énoncé.
C'est pourquoi la détection de circuit n'est pas un raffinement : c'est la première chose à faire sur un graphe de dépendances. Les outils réels le font, et c'est exactement ce que signale un gestionnaire de paquets qui parle de dépendance circulaire.

Le tri topologique

L'algorithme de Kahn est le plus lisible : on prend une source, c'est-à-dire un sommet sans prédécesseur, celui dont la colonne est vide dans la matrice d'adjacence du chapitre 2 ; on la sort, on la retire du graphe, et l'on recommence. Pour savoir qui devient source, il suffit de tenir à jour le degré entrant de chaque sommet : retirer un sommet fait baisser d'un celui de chacun de ses successeurs, et un sommet dont le degré tombe à 0 entre dans une file des sommets prêts.

La figure reprend le graphe du début du chapitre, lu comme six tâches A à F et leurs contraintes : C <- A, B se lit « C attend A et B », c'est-à-dire les arcs A -> C et B -> C. Chaque tâche porte, sous son nom, son degré entrant.

L'ordre obtenu, A B C D E F, respecte toutes les flèches. Il n'est pas unique : B A C E D F conviendrait aussi. Quand plusieurs sommets sont prêts en même temps, on peut prendre n'importe lequel, et c'est même une information utile : ces tâches-là peuvent être menées en parallèle.

Exhiber le circuit

Kahn dit qu'il y a un circuit, pas lequel. Sur le graphe ci-dessous, les arcs A -> B, B -> C, C -> D, D -> B et A -> E, il sort A, puis E, et s'arrête : les trois sommets restants gardent chacun un prédécesseur. La figure s'ouvre sur cet arrêt ; l'arc D -> B, qui referme le circuit, est dessiné en retour.

Ce circuit épaissi, Kahn ne le fournit pas : la figure le cherche par la méthode qui suit.

Pour dire quel circuit, et donc quelle contrainte retirer, on revient au parcours en profondeur du chapitre 3, avec une précision : chaque sommet passe par trois états. Il est neuf tant qu'on ne l'a pas atteint, en cours tant qu'on explore ce qui part de lui, terminé quand tout ce qui part de lui a été exploré. Les sommets en cours forment exactement le chemin qu'on est en train de descendre. Un arc vers un sommet en cours referme donc ce chemin sur lui-même : c'est un circuit, et la liste des sommets en cours le donne. Un arc vers un sommet terminé, au contraire, rejoint seulement un chemin déjà exploré, comme le second des deux arcs qui mènent à F sur le premier graphe du chapitre : ce n'est pas un circuit.

Sur le graphe du chapitre, la fonction ne trouve rien, à juste titre. Sur un planning où la recette a été placée par erreur avant la base de données, elle nomme les trois tâches du circuit : c'est l'une de ces trois contraintes qu'il faut retirer.

Ordonnancer un projet

Le tri topologique dit dans quel ordre faire les choses. Avec des durées, il dit aussi quand, et surtout combien de temps prendra l'ensemble.

Ce calcul se fait en une seule passe dans l'ordre topologique : quand on arrive à un sommet, tous ses prédécesseurs sont déjà calculés. C'est la raison profonde pour laquelle on trie d'abord.

Le calcul ne sert pas qu'aux plannings. Une chaîne d'intégration continue est le même graphe, avec des travaux à la place des tâches, et son chemin critique dit où une optimisation fera gagner du temps et où elle n'en fera gagner aucun.

Voici un projet de sept tâches, dont les durées sont données en jours. Dans la figure, chaque tâche porte sa durée à droite de son nom et, dessous, ses débuts au plus tôt et au plus tard, puis sa marge ; un arc va d'une tâche vers une tâche qui l'attend. Rien n'y est dessiné à la main : les dates, les marges et le chemin critique sont calculés, et le restent quand on change une durée ou une contrainte.

Le chemin en gras est le plus long du début à la fin du projet : c'est le chemin critique, Analyse, Modele, Base, Service, Recette, pour 30 jours. La branche par la maquette et l'interface est plus courte, elle dispose donc d'une marge, hachurée sur le diagramme de Gantt. Le tableau reprend toutes les dates, comptées en jours depuis le début du projet.

La colonne « au plus tôt » se remplit de haut en bas, avec le maximum : Service attend Base, finie au jour $13 + 6 = 19$, et Interface, finie au jour $8 + 2 = 10$ ; il commence donc au jour 19. La colonne « au plus tard » se remplit de bas en haut, avec le minimum : Recette doit commencer au jour $30 - 4 = 26$, donc Service au jour $26 - 7 = 19$ ; Interface, qui dure 2 jours, peut alors commencer jusqu'au jour 17, et Maquette, qui doit être finie avant, jusqu'au jour 14, soit 9 jours après sa date au plus tôt.

Un plus long chemin, calculé comme un plus court. Porter la durée de chaque tâche sur les arcs qui en partent (l'arc de Modele vers Base pèse alors 8, et un sommet Fin ajouté après Recette reçoit un arc de poids 4) fait du graphe des tâches un graphe pondéré ordinaire. La formule de la date au plus tôt devient alors le relâchement du chapitre sur les plus courts chemins, où le minimum est remplacé par un maximum : on cherche le chemin le plus long, et non le plus court.
Sur un graphe sans circuit, une seule passe dans l'ordre topologique suffit, exactement comme pour les plus courts chemins sur un tel graphe. Sur un graphe quelconque, en revanche, chercher le plus long chemin qui ne repasse par aucun sommet est un problème difficile, comme la coloration du chapitre suivant : c'est l'absence de circuit qui rend l'ordonnancement facile.

Cette façon de faire, où chaque tâche est un sommet et chaque arc une contrainte d'antériorité, s'appelle la méthode des potentiels. La méthode PERT, plus ancienne, place au contraire les tâches sur les arcs ; les deux donnent les mêmes dates. La marge calculée ici est la marge totale. La marge libre est le retard qu'une tâche peut prendre sans retarder le début d'aucun de ses successeurs : Maquette a 9 jours de marge totale mais aucune marge libre, puisque tout retard de Maquette repousse Interface ; Interface, elle, a 9 jours de marge libre.

Les composantes fortement connexes

Le plan de sens uniques du début du chapitre se découpait en deux groupes de lieux qui communiquent dans les deux sens. Ces groupes portent un nom, et se calculent aussi vite qu'un parcours.

Sur le plan de sens uniques, le centre (Gare, Mairie, Marché) et le port (Port, Usine) sont les deux composantes, et le graphe des composantes se réduit à un seul arc, du centre vers le port. À l'autre extrême, dans un DAG, aucun sommet n'en atteint un autre qui puisse revenir vers lui : chaque sommet est seul dans sa composante. Une composante de plus d'un sommet contient donc toujours un circuit. Dans un graphe de dépendances, c'est un paquet de modules qui dépendent les uns des autres en boucle, et qu'il faudra traiter ensemble.

Deux parcours en profondeur : l'algorithme de Kosaraju

Le premier parcours en profondeur, sur le graphe, note l'ordre dans lequel les sommets se terminent : un sommet est terminé quand tout ce qui part de lui a été exploré. Le second parcours se fait sur le graphe inverse, où chaque arc est retourné, et repart des sommets dans l'ordre inverse de fin, du dernier terminé au premier. Chaque parcours lancé dans cette seconde phase ramasse exactement une composante.

La raison tient en deux phrases. Le sommet terminé en dernier appartient à une composante de tête, dans laquelle aucun arc n'entre depuis une autre composante ; en remontant les arcs depuis lui, on ne peut donc pas sortir de sa composante, et l'on ramasse tous ses sommets, et eux seuls. On la met de côté, et parmi les sommets restants, le dernier terminé joue le même rôle.

Sur le plan de sens uniques, le premier parcours part de Gare et descend Mairie, Marché, Port, Usine : les sommets se terminent dans l'ordre Usine, Port, Marché, Mairie, Gare. Le second parcours part donc de Gare, en remontant les arcs : il atteint Marché, puis Mairie, et s'arrête, car aucun arc ne remonte du port vers le centre. C'est la première composante. Le sommet suivant qui n'a pas encore été ramassé, dans l'ordre inverse de fin, est Port : en remontant, il atteint Usine. C'est la seconde.

Les composantes sortent dans l'ordre d'un tri topologique du graphe des composantes : le centre avant le port, et, sur le DAG du chapitre, chaque sommet seul, dans l'ordre B A C E D F, qui est bien un tri topologique : c'est celui que la section sur Kahn citait en exemple. L'algorithme de Tarjan obtient les mêmes composantes en un seul parcours en profondeur, au prix d'une comptabilité plus fine : il numérote les sommets dans l'ordre où il les découvre et retient, pour chacun, le plus petit numéro qu'il permet d'atteindre parmi les sommets pas encore rangés dans une composante. Il rend les composantes dans l'ordre inverse d'un tri topologique du graphe des composantes. Les deux coûtent $O(n + m)$, comme un simple parcours. Le parcours Logique et solveurs SAT s'en sert pour décider en temps linéaire si un problème 2-SAT a une solution : voir les fragments faciles.

Mettre en pratique