graphlib
--- Functionality to operate with graph-like structures¶
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 parget_ready()
pour les traiter. Appelerdone()
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èsprepare()
.
- 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 maisget_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é avecadd()
.
- is_active()¶
Renvoie
True
si une progression peut être faite etFalse
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 parTopologicalSorter.get_ready()
ou que le nombre de nœuds marquésTopologicalSorter.done()
est inférieur au nombre qui a été renvoyé parTopologicalSorter.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 utilisantTopologicalSorter.add()
, si l'appel est fait sans appel àprepare()
ou si le nœud n'a pas encore été renvoyé parget_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()
anddone()
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.
Ajouté 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 parTopologicalSorter.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.