Graphes orientés, DAG et ordonnancement

Où on va

Dès qu'une relation cesse d'être symétrique, il faut des flèches : cette tâche précède celle-là, ce module dépend de cet autre, cette page renvoie vers celle-ci. Et dès qu'il y a des flèches, une question se pose avant toutes les autres : y a-t-il un circuit ? Un graphe orienté sans circuit, ce qu'on appelle un DAG, se range dans un ordre linéaire, se calcule en une passe, et se prête à des choses que les autres graphes ne permettent pas.

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.

Définitions

Les successeurs de $u$ sont les sommets $v$ tels que l'arc $(u, v)$ existe. Les prédécesseurs sont les $v$ tels que $(v, u)$ existe.

Le degré sortant $d^+(u)$ compte les successeurs, le degré entrant $d^-(u)$ compte les prédécesseurs.

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é.

Graphe orienté6 sommets, 7 arêtes

L'accessibilité n'est pas symétrique

Dans ce graphe, on va de A à F, mais jamais de F à A. Dire « ces deux sommets sont reliés » n'a plus de sens : il faut préciser le sens.
Beaucoup d'algorithmes du chapitre 3 restent valables en suivant les arcs, mais leur interprétation change. Un BFS orienté donne les sommets accessibles depuis le départ, ce qui n'est pas la composante connexe.

Forte connexité

Un graphe orienté est fortement connexe si, pour toute paire $(u, v)$ , il existe un chemin de $u$ vers $v$ et un chemin de $v$ vers $u$ .

Il est faiblement connexe si le graphe non orienté obtenu en effaçant les flèches est connexe.

Les DAG

Définition

Un DAG (directed acyclic graph), ou graphe orienté sans circuit, est un graphe orienté ne contenant aucun circuit : on ne peut jamais revenir à son point de départ en suivant les flèches.

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

Définition

Un tri topologique est un ordre linéaire des sommets tel que, pour tout arc $(u, v)$ , $u$ apparaisse avant $v$ .

Un tel ordre existe si et seulement si le graphe est un DAG.

L'algorithme de Kahn est le plus lisible : on prend un sommet sans prédécesseur, on le sort, on le retire du graphe, et l'on recommence.

Graphe orienté6 sommets, 7 arêtes

0 / 6

Rien n'est encore visité.

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.

Le tri topologique détecte le circuit gratuitement

Si l'algorithme s'arrête alors qu'il reste des sommets, c'est qu'aucun d'eux n'a de degré entrant nul : ils forment donc un circuit, ou en contiennent un.
Aucun calcul supplémentaire n'est nécessaire. Le nombre de sommets sortis, comparé à $n$, est le test.

main.py

Sortie

>_ Prêt à exécuter…

Vérification rapidesans note, on peut se reprendre

1.Un tri topologique existe…

2.L'algorithme de Kahn s'arrête avec trois sommets non sortis. Que conclure ?

3.Une tâche a trois prédécesseurs. Sa date de début au plus tôt est…

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.

Date au plus tôt

La date de début au plus tôt d'une tâche est la plus grande des dates de fin de ses prédécesseurs :

\text{début}(v) = \max_{u \to v} \big( \text{début}(u) + \text{durée}(u) \big)

Une tâche sans prédécesseur commence à 0.

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.

Une seconde passe, en sens inverse cette fois, donne les dates au plus tard : la dernière date à laquelle une tâche peut commencer sans retarder le projet. La différence entre les deux dates est la marge.

Chemin critique

Le chemin critique est le chemin le plus long, en durée cumulée, du début à la fin du projet. Sa longueur est la durée totale minimale du projet.

Une tâche est critique quand sa marge est nulle : date au plus tôt et date au plus tard coïncident. La retarder d'un jour retarde tout le projet d'un jour.

Graphe orienté7 sommets, 7 arêteschemin mis en évidence

Le chemin en gras est le chemin critique : Analyse, Modele, Base, Service, Recette. La branche par la maquette et l'interface est plus courte, elle dispose donc d'une marge.

main.py

Sortie

>_ Prêt à exécuter…

Le maximum, pas la somme

Une tâche qui a trois prédécesseurs ne commence pas après la somme de leurs durées : elle commence après le dernier d'entre eux. D'où le maximum dans la formule.
L'erreur inverse, additionner, donne des projets deux fois trop longs et se repère à ce qu'aucune tâche ne se déroule jamais en parallèle.

Exercices type

Quand un tri topologique existe-t-il, et que faire s'il n'existe pas ?

Il existe si et seulement si le graphe est un DAG, c'est-à-dire sans circuit.

S'il n'existe pas, l'algorithme de Kahn s'arrête avec des sommets non sortis : ceux-là appartiennent à un circuit ou en dépendent.

Ce n'est pas un défaut de l'algorithme mais un défaut des données : un ensemble de contraintes contradictoires, du type « A avant B, B avant C, C avant A ». Il faut retirer une contrainte, pas changer d'algorithme.

Le tri topologique est-il unique ?

Non, sauf cas particulier.

Chaque fois que plusieurs sommets ont un degré entrant nul en même temps, n'importe lequel peut être choisi, ce qui donne des ordres différents, tous valides.

L'ordre est unique si et seulement si, à chaque étape, exactement un sommet est disponible : cela revient à dire que le DAG contient un chemin hamiltonien, un chemin passant par tous les sommets.

Les sommets simultanément disponibles sont d'ailleurs une information précieuse : ce sont les tâches parallélisables.

Pourquoi calcule-t-on les dates au plus tôt dans l'ordre topologique ?

Parce que la date d'une tâche dépend de celles de tous ses prédécesseurs.

Dans l'ordre topologique, quand on arrive à un sommet, tous ses prédécesseurs ont déjà été traités : leur date est définitive, et une seule passe suffit.

Dans un autre ordre, il faudrait recalculer plusieurs fois, ou faire de la programmation dynamique avec mémoïsation, pour un résultat identique et un code plus compliqué.

Quelle différence entre connexe et fortement connexe ?

Faiblement connexe : en effaçant les flèches, on obtient un graphe connexe. Autrement dit, le dessin est d'un seul tenant.

Fortement connexe : pour toute paire $(u, v)$ , il existe un chemin de $u$ vers $v$ et un chemin de $v$ vers $u$ , en respectant les flèches.

Un DAG non trivial n'est jamais fortement connexe : s'il l'était, il contiendrait un circuit. Un graphe peut donc être d'un seul tenant sans que ses sommets communiquent dans les deux sens.

Une tâche du chemin critique prend un jour de retard. Que se passe-t-il ?

Le projet entier prend un jour de retard.

C'est la définition même du chemin critique : ses tâches n'ont aucune marge, donc tout retard s'y propage jusqu'à la fin.

À l'inverse, une tâche hors chemin critique dispose d'une marge égale à la différence entre la durée totale et sa propre date de fin au plus tôt. Elle peut glisser dans cette limite sans conséquence, mais au-delà elle devient critique à son tour, et le chemin critique change.

Comment détecter un circuit dans un graphe orienté ?

Deux méthodes, également valables.

Par Kahn : on lance le tri topologique et on compare le nombre de sommets sortis à $n$ . S'il en manque, il y a un circuit. C'est gratuit puisqu'on veut souvent le tri de toute façon.

Par DFS : on marque les sommets en cours de traitement, distincts de ceux terminés. Rencontrer un arc vers un sommet en cours signale un circuit, et la pile courante en donne les sommets.

La seconde méthode a l'avantage d'exhiber le circuit, ce qui est bien plus utile qu'un simple « il y en a un » dans un message d'erreur.

La méthode

Sépare successeurs et prédécesseurs dès la construction du graphe.
Cherche le circuit en premier sur tout graphe de dépendances.
Trie topologiquement avant tout calcul qui remonte les dépendances.
Prends le maximum, jamais la somme, pour une date de début.
Note qui impose la date si tu veux pouvoir remonter le chemin critique.
Repère les sommets simultanément prêts : ce sont tes parallélisations.
Exhibe le circuit plutôt que de signaler son existence.

En résumé

Un graphe orienté a des successeurs et des prédécesseurs, deux voisinages distincts.
L'accessibilité n'est pas symétrique : préciser le sens devient obligatoire.
Un DAG est un graphe orienté sans circuit ; c'est la structure des dépendances.
Un tri topologique existe si et seulement si le graphe est un DAG.
L'algorithme de Kahn sort les sommets de degré entrant nul, un par un.
Le tri détecte le circuit gratuitement : il reste des sommets non sortis.
Les sommets prêts en même temps sont parallélisables.
La date au plus tôt est un maximum sur les prédécesseurs, calculé en une passe.
Le chemin critique est le plus long chemin ; ses tâches n'ont aucune marge.

Et ensuite ? On sait maintenant ordonner des tâches liées par des dépendances. Le chapitre suivant traite l'autre grande question d'ordonnancement : quand des tâches se gênent au lieu de se précéder, il faut les colorer.