Introduction à une série en 3 parties
En mathématiques, et plus précisément en théorie des graphes, un graphe orienté est un graphe constitué d’un ensemble de sommets (souvent appelés nœuds) reliés par des arêtes orientées (souvent appelées arcs).
La nature orientée du graphe est utile dans bien des cas car elle permet de décrire précisément les relations entre n’importe quels sommets du graphe.
Vous manipulez déjà des graphes orientés sans le savoir
Saviez-vous que vous créiez des graphes orientés chaque fois qu’un mécanisme d’import est utilisé en coulisses ?
Prenez par exemple l’image ci-dessus avec quatre sommets, chacun représentant un fichier JavaScript.
La question est maintenant : quelles sont les relations entre ces fichiers ? Dans tous les langages de programmation, un fichier peut en importer un ou plusieurs autres. Chaque fois qu’un fichier en importe un autre, une relation implicite est créée.
src/hello.js
export function sayHello() { }src/main.js
import { sayHello } from "hello.js";Comme vous pouvez le voir ci-dessus, main.js importe hello.js pour utiliser la fonction sayHello. L’import statique crée une relation implicite entre les deux fichiers.
Dans le domaine des graphes, cette relation peut être modélisée comme une arête orientée allant de main.js vers hello.js (que l’on peut écrire main.js ---> hello.js). On dit que main.js est adjacent à hello.js mais, plus généralement, on peut se permettre de dire que main.js dépend de hello.js.
Étant donné deux sommets A et B, s’il existe une arête orientée X partant de A vers B, alors on peut dire que A est adjacent à B.
Nous pouvons maintenant mettre à jour le graphe avec nos arêtes représentées :
Au fond, ce graphe nous dit que :
- FileA dépend directement de FileD et FileB
- FileA dépend indirectement de FileC (à travers FileD et FileB)
- FileD dépend directement de FileC
- FileB dépend directement de FileC
- FileC ne dépend de rien
Cette structure peut sembler simple mais elle permet en réalité de modéliser des schémas très complexes. Examinons trois exemples de cas d’usage intéressants pour les graphes orientés.
1. Analyse statique des dépendances
=> Détection des dépendances cycliques par ESLint pour JavaScript Plugin no-cycle d’ESLint
Les dépendances circulaires peuvent faire planter votre programme ou introduire des incohérences de bien des manières, ce n’est donc pas quelque chose à sous-estimer. Heureusement, dans Node.js, la plupart des systèmes de modules connus savent résoudre les cycles de dépendances et éviter à votre programme de planter (certains systèmes de modules s’en sortent mieux que d’autres, cela dit).
Néanmoins, les dépendances circulaires sont souvent le signe d’une erreur de conception plus ou moins profonde dans votre projet, c’est pourquoi je conseille toujours de résoudre les dépendances circulaires.
Pour aller plus loin dans la détection des dépendances circulaires :
2. Tâches incrémentales / affectées
=> Les outils de bundling et de monorepo en font un usage intensif (ex. : le build/test/lint affecté de NX…)
Un graphe orienté peut aussi servir à établir des motifs affected. Le motif affected consiste à analyser le code source et à déterminer ce qui peut être affecté par chaque changement de code.
Sur l’image ci-dessus, on peut voir un projet utilisant une stratégie affected pour ne builder que ce qui devait réellement être rebuildé. Lors du build de la Main App après le changement de Library 2, seules Library 1 et Library 2 doivent être rebuildées. Le reste du graphe (Library 3, Library 4, Library 5) reste non affecté, et la version en cache de ces bibliothèques peut donc être utilisée dans le build final (inutile de les rebuilder).
Dans un monorepo ou dans des configurations de projets personnalisées, ce motif affected peut réduire drastiquement le temps pris par des tâches triviales comme build/test/lint.
Pour aller plus loin dans le motif Affected :
Voir une implémentation d’un motif affected utilisant la bibliothèque digraph-js que j’ai écrite
3. Orchestration de tâches
Dans le contexte de l’orchestration et de l’ordonnancement de tâches, les graphes orientés peuvent eux aussi être très précieux.
Prenez par exemple un outil que tout le monde connaît : Microsoft Excel. Vous êtes-vous déjà demandé comment la modification de la formule d’une cellule pouvait affecter directement d’autres cellules dépendant de cette formule ? J’espère que vous ne serez pas déçu d’apprendre qu’il ne s’agit pas d’une boucle infinie tournant sous le capot.
Dans ce contexte, notre graphe orienté possède un sommet pour chaque cellule à mettre à jour et une arête entre deux d’entre elles chaque fois que l’une doit être mise à jour avant l’autre.
Comme nous devons ordonnancer de manière cohérente les tâches impliquées, nous ne pouvons pas avoir de cycles dans notre graphe. Les graphes de dépendances sans dépendances circulaires forment des graphes orientés acycliques (DAG).
Cette contrainte d’acyclicité nous permet de rester cohérents quant à l’ordre des différentes opérations impliquées par les mises à jour.
Dans un autre contexte d’orchestration de tâches, nous pouvons brièvement évoquer l’ordonnancement de tâches, qui inclut les motifs séquentiels par opposition aux motifs parallèles.
Grâce aux DAG, nous pouvons facilement déterminer quelles tâches peuvent être exécutées en parallèle (aucune dépendance commune dans le graphe) et quelles tâches doivent être exécutées séquentiellement (l’une après l’autre, car l’une dépend de l’autre).
Des problèmes similaires d’ordonnancement de tâches se posent dans les makefiles pour la compilation de programmes, dans les fichiers YAML pour la CI/CD et dans l’ordonnancement d’instructions pour l’optimisation de programmes informatiques de bas niveau.
La suite de cette série
Le prochain chapitre présente des cas d’usage concrets construits par-dessus la bibliothèque digraph-js, en commençant par une reproduction pratique du motif incrémental / affected.