"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()".

      La méthode "__bool__()" de cette classe renvoie à cette fonction
      donc au lieu de :

         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.

   On accède au circuit détecté via le second élément de l'attribut
   "args" de l'instance de l'exception. Cet attribut est une liste de
   nœuds où chaque nœud est, dans le graphe, un prédécesseur immédiat
   du nœud suivant de la liste. Dans la liste renvoyée, le premier et
   le dernier nœud sont les mêmes afin de bien indiquer que c'est un
   circuit.
