# AP2 · 6 — Des arbres aux dépendances (facultatif) ## Notre question Dans les arbres précédents, nous suivions les enfants d'une expression. Pour un tableur ou un outil de construction, plusieurs résultats peuvent dépendre de la même donnée. Un *graphe* conserve ces dépendances partagées : ses *nœuds* sont des noms, et une *arête* relie un nom à chaque résultat dont il dépend. ```text let price = 12.0 let quantity = 3.0 let total = price * quantity let tax = total * 0.2 let invoice = total + tax invoice ``` Dans notre langage, ces `let` s'exécutent dans l'ordre écrit. Pour cet atelier, nous étudions **un autre modèle**, où l'on fournit un graphe de formules dont l'ordre n'est pas fixé. Ce n'est pas une modification cachée de la sémantique de `let`. Nous cherchons un ordre de calcul à partir des dépendances. Aucun module précédent n'est nécessaire : ce notebook est autonome. Un nœud est un nom ; ses enfants sont les résultats dont il dépend. Les nombres constants ont une liste de dépendances vide. Dessinez les flèches et prédisez un ordre possible pour obtenir `invoice`. Remarquez que `total` est utilisé deux fois, par `tax` et par `invoice` : dans un arbre, il serait recopié ; dans le graphe, il n'apparaît qu'une fois. > **Repères.** Facultatif, après les cinq étapes ou hors séance ; [slide 54](https://ap-2026.noce.fr/slides/AP2.html#54). Elixir : maps `%{}`, `MapSet`, le pipe `|>`, expliqués au point d'emploi. Prolongement facultatif, valorisable en bonus. > 💡 Cette étape permet d'approfondir notre interpréteur. > Selon notre rythme, nous pourrons la travailler ensemble ou la > garder pour la suite. Le travail à rendre sera annoncé en cours ; > les prolongements non demandés restent des bonus facultatifs. > **Sauvegardez-le dès maintenant sous `AP2/ap2-06-graphes.livemd`.** Les vérifications de ce notebook utilisent `assert`, fourni par Elixir via ExUnit : une condition fausse arrête la cellule et affiche la valeur obtenue à côté de celle attendue. Évaluez la cellule d'import une fois, puis réévaluez votre code avant ses tests après chaque modification. ```elixir import ExUnit.Assertions ``` Nous représentons le graphe par une *map*, une structure que nous n'avions pas encore utilisée. > 💡 Une map associe une clé à une valeur : `%{"price" => []}` associe le nom > à ses dépendances. `Map.fetch(map, key)` rend `{:ok, valeur}` ou `:error` si > la clé manque. `Map.put(map, key, value)` produit une nouvelle map avec cette > association en plus. `MapSet.new(["a", "a"])` construit un *ensemble* > contenant seulement `"a"` ; `MapSet.member?(set, x)` teste l'appartenance, > `MapSet.put(set, x)` ajoute un élément. Les maps et les ensembles sont > immuables, comme nos listes : chaque opération rend une nouvelle valeur. ```elixir graph = %{ "price" => [], "quantity" => [], "total" => ["price", "quantity"], "tax" => ["total"], "invoice" => ["total", "tax"] } ``` ## Concevoir un parcours qui ne recalcule pas tout Écrivez `Dependencies.order(graph, root)`. Le résultat est `{:ok, noms}` : chaque nœud atteignable depuis `root` apparaît une seule fois, après ses dépendances. Un tel ordre s'appelle un *ordre topologique* ; plusieurs ordres peuvent être corrects. Les nœuds sans lien avec la racine ne font pas partie du résultat. Commencez par le graphe ci-dessus, puis cherchez ce qui se passe si `tax` dépend de `invoice` : le parcours reviendrait sur un nœud qu'il est en train de visiter, c'est un *cycle*. Une simple liste de « déjà vus » suffit-elle à distinguer un partage normal, comme `total`, d'un cycle ? Décidez quel état transmettre avant d'écrire l'algorithme. Rendez `{:error, {:cycle, nom}}` pour un cycle atteignable et `{:error, {:unknown_node, nom}}` si une dépendance n'existe pas. ```elixir defmodule Dependencies do def order(_graph, _root), do: {:error, :not_implemented} # Écrivez le parcours et ses fonctions auxiliaires. end ``` Les vérifications acceptent tout ordre correct : elles testent les propriétés du résultat, pas une liste fixée. > 💡 Dans les tests, `order |> Enum.with_index() |> Map.new()` associe chaque > nom à sa position : le *pipe* `|>` place la valeur à gauche en premier argument > de l'appel suivant, `Enum.with_index/1` produit des couples `{nom, indice}`, et > `Map.new/1` en fait une map. `positions[nom]` lit alors la valeur d'une clé. > Deux générateurs dans `for` visitent chaque nœud puis chacune de ses > dépendances. `Enum.sort/1` trie, `Enum.uniq/1` retire les doublons, > `length/1` compte. Enfin, `&(&1 == "d")` est la forme courte de > `fn name -> name == "d" end` : `&1` désigne son argument ; `Enum.count/2` > compte les éléments qui satisfont cette fonction. ```elixir {:ok, order} = Dependencies.order(graph, "invoice") assert Enum.sort(order) == ["invoice", "price", "quantity", "tax", "total"] assert length(order) == length(Enum.uniq(order)) positions = order |> Enum.with_index() |> Map.new() for {node, dependencies} <- graph, dependency <- dependencies do assert positions[dependency] < positions[node] end assert Dependencies.order(%{"alone" => []}, "alone") == {:ok, ["alone"]} assert Dependencies.order(%{"a" => ["absent"]}, "a") == {:error, {:unknown_node, "absent"}} assert {:error, {:cycle, _}} = Dependencies.order(%{"a" => ["a"]}, "a") assert {:error, {:cycle, _}} = Dependencies.order(%{"a" => ["b"], "b" => ["a"]}, "a") ``` ### Si vous bloquez Premier indice : ajoutez un nom au résultat **après** avoir visité ses dépendances. Deuxième indice : séparez les nœuds dont l'exploration est terminée et ceux encore présents sur le chemin courant. Revenir à un nœud du chemin courant révèle un cycle ; retrouver un nœud terminé indique seulement du partage. `MapSet.new/0`, `MapSet.put/2` et `MapSet.member?/2` permettent de représenter ces ensembles. ### Pour aller plus loin Construisez un graphe en losange pour vérifier qu'une dépendance partagée n'est pas signalée comme un cycle. Ajoutez un cycle inaccessible depuis la racine : votre algorithme doit-il le signaler au regard du contrat ? Expliquez votre réponse. Vous pouvez ensuite rendre le chemin complet d'un cycle, ou construire automatiquement les dépendances d'une formule arithmétique en parcourant ses nœuds `{:name, nom}`. > 💡 `hd(liste)` rend la tête d'une liste, `List.last(liste)` son dernier élément. ```elixir diamond = %{"a" => ["b", "c"], "b" => ["d"], "c" => ["d"], "d" => [], "unused" => ["unused"]} {:ok, order} = Dependencies.order(diamond, "a") assert Enum.sort(order) == ["a", "b", "c", "d"] assert Enum.count(order, &(&1 == "d")) == 1 assert hd(order) == "d" assert List.last(order) == "a" ``` ## Garder une trace de votre exploration Expliquez la différence entre une arête de partage et une arête qui ferme un cycle. Joignez votre contre-exemple dessiné. Quel lien voyez-vous avec les dépendances d'un projet logiciel, une feuille de calcul ou les cellules de Livebook ? Ce prolongement est facultatif. Si vous le joignez dans `AP2/` au rendu du cycle le 6 décembre 2026 à 23 h 59 (Paris), une exploration expliquée et testée peut apporter un bonus. Il ne remplace pas les étapes annoncées en cours. Si un bout de syntaxe Elixir vous manque en route, les chapitres 1 à 4 du [poly](https://ap-2026.noce.fr/poly/poly-elixir.pdf) se consultent au besoin ; ils ne sont pas un prérequis de cette étape. Pour toute question, vous pouvez me contacter par email : [aurelien.noce@minesparis.psl.eu](mailto:aurelien.noce@minesparis.psl.eu).