# `graphlib` — Fonctionnalités pour travailler avec des structures de type graphe

Code source: Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)

  Provides functionality to topologically sort a graph of hashable nodes.

  L'ordre topologique est un ordre linéaire des sommets d'un graphe afin que pour chaque arête u → v d'un sommet u à un sommet v, cet ordre va placer le sommet u avant le sommet v. Par exemple, les sommets d'un graphe peuvent représenter une tâche à faire et une arête peut représenter la contrainte comme quoi telle tâche doit être réalisée avant telle autre. Dans cet exemple, un ordre topologique est simplement une séquence valide pour ces tâches. Cet ordre n'est possible que si le graphe n'a pas de circuit, c'est-à-dire si c'est un graphe orienté acyclique.

  Si l'argument optionnel graph est fourni, cela doit être un dictionnaire représentant un graphe acyclique avec comme clés les nœuds et comme valeurs des itérables sur les prédécesseurs de ces nœuds dans le graphe (les nœuds qui ont des arêtes qui pointent vers la valeur de la clé). Les nœuds s'ajoutent en utilisant la méthode `add()`

  De manière générale, les étapes nécessaires pour trier un graphe donné sont les suivantes :

  - créer une instance de la classe `TopologicalSorter` avec éventuellement un graphe initial ;

  - ajouter d'autres nœuds au graphe ;

  - appeler `prepare()` sur le graphe ;

  - tant que `is_active()` est à `True`, itérer sur les nœuds renvoyés par `get_ready()` pour les traiter. Appeler `done()` sur chaque nœud une fois le traitement terminé.

  Si vous souhaitez simplement trier des nœuds du graphe sans parallélisme, la méthode `TopologicalSorter.static_order()` peut être utilisée directement :

      >>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
      >>> ts = TopologicalSorter(graph)
      >>> tuple(ts.static_order())
      ('A', 'C', 'B', 'D')

  La classe est conçue pour prendre facilement en charge le traitement en parallèle des nœuds quand ils deviennent disponibles. Par exemple :

      topological_sorter = TopologicalSorter()

      # Add nodes to 'topological_sorter'...

      topological_sorter.prepare()
      while topological_sorter.is_active():
          for node in topological_sorter.get_ready():
              # Worker threads or processes take nodes to work on off the
              # 'task_queue' queue.
              task_queue.put(node)

          # When the work for a node is done, workers put the node in
          # 'finalized_tasks_queue' so we can get more nodes to work on.
          # The definition of 'is_active()' guarantees that, at this point, at
          # least one node has been placed on 'task_queue' that hasn't yet
          # been passed to 'done()', so this blocking 'get()' must (eventually)
          # succeed.  After calling 'done()', we loop back to call 'get_ready()'
          # again, so put newly freed nodes on 'task_queue' as soon as
          # logically possible.
          node = finalized_tasks_queue.get()
          topological_sorter.done(node)

  add(node, *predecessors)

    Add a new node and its predecessors to the graph. Both the node and all elements in predecessors must be hashable.

    S'il est appelé plusieurs fois avec le même nœud en tant qu'argument, l'ensemble des dépendances sera l'union de toutes les dépendances qui auront été transmises.

    Il est possible d'ajouter un nœud sans dépendance (predecessors n'est pas fourni) ou de fournir une dépendance deux fois. Si un nœud qui n'a jamais été fourni auparavant est inclus dans predecessors il sera automatiquement ajouté au graphe sans prédécesseur lui-même.

    Lève une `ValueError` si appelée après `prepare()`.

  prepare()

    Indique que le graphe est terminé et vérifie les circuits du graphe. Si un circuit est détecté, une `CycleError` est levée mais `get_ready()` peut encore être utilisée pour obtenir autant de nœuds que possible avant que les circuits ne bloquent la progression. Après un appel de cette fonction, le graphe ne peut pas être modifié, et donc aucun nœud ne peut être ajouté avec `add()`.

  is_active()

    Renvoie `True` si une progression peut être faite et `False` dans le cas contraire. La progression est possible si des circuits ne bloquent pas la résolution ou qu'il reste des nœuds prêts qui n'ont pas encore été renvoyés par `TopologicalSorter.get_ready()` ou que le nombre de nœuds marqués `TopologicalSorter.done()` est inférieur au nombre qui a été renvoyé par `TopologicalSorter.get_ready()`.

    The `__bool__()` method of this class defers to this function, so instead of:

        if ts.is_active():
            ...

    il est plus simple de faire :

        if ts:
            ...

    Lève une `ValueError` si l'appel à `prepare()` n'a pas été fait au préalable.

  done(*nodes)

    Marque un ensemble de nœuds renvoyé par `TopologicalSorter.get_ready()` comme traités, permettant aux successeurs de chaque nœud de nodes d'être renvoyés lors d'un prochain appel à `get_ready()`.

    Lève une `ValueError` si n'importe quel nœud dans nodes a déjà été marqué comme traité par un précédent appel à cette méthode ou si un nœud n'a pas été ajouté au graphe en utilisant `TopologicalSorter.add()`, si l'appel est fait sans appel à `prepare()` ou si le nœud n'a pas encore été renvoyé par `get_ready()`.

  get_ready()

    Renvoie un n-uplet avec tous les nœuds prêts. Renvoie d'abord tous les nœuds sans prédécesseurs, et une fois marqués comme traités avec un appel de `TopologicalSorter.done()`, les autres appels renvoient tous les nouveaux nœuds dont tous les prédécesseurs sont traités. Une fois que la progression n'est plus possible, des tuples vides sont renvoyés.

    Lève une `ValueError` si l'appel à `prepare()` n'a pas été fait au préalable.

  static_order()

    Returns an iterator object which will iterate over nodes in a topological order. When using this method, `prepare()` and `done()` should not be called. This method is equivalent to:

        def static_order(self):
            self.prepare()
            while self.is_active():
                node_group = self.get_ready()
                yield from node_group
                self.done(*node_group)

    Le tri obtenu peut dépendre de l'ordre dans lequel les éléments ont été ajoutés dans le graphe. Par exemple :

        >>> ts = TopologicalSorter()
        >>> ts.add(3, 2, 1)
        >>> ts.add(1, 0)
        >>> print([*ts.static_order()])
        [2, 0, 1, 3]

        >>> ts2 = TopologicalSorter()
        >>> ts2.add(1, 0)
        >>> ts2.add(3, 2, 1)
        >>> print([*ts2.static_order()])
        [0, 2, 1, 3]

    Ceci est dû au fait que "0" et "2" sont au même niveau dans le graphe (ils auraient été renvoyés dans le même appel à `get_ready()`) et l'ordre entre eux est déterminé par l'ordre lors de l'insertion.

    Si un circuit est détecté alors une `CycleError` est levée.

  Nouveau dans la version 3.9.

## Exceptions

Le module `graphlib` définit les classes d'exceptions suivantes :

exception graphlib.CycleError

  Une classe héritant de `ValueError` levée par `TopologicalSorter.prepare()` si un circuit existe dans le graphe courant. Si plusieurs circuits existent, un seul est inclus dans l'exception.

  The detected cycle can be accessed via the second element in the `args` attribute of the exception instance and consists in a list of nodes, such that each node is, in the graph, an immediate predecessor of the next node in the list. In the reported list, the first and the last node will be the same, to make it clear that it is cyclic.