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.