graphlib — Functionality to operate with graph-like structures

Código fuente: Lib/graphlib.py

---

class graphlib.TopologicalSorter(graph=None)

Provee una funcionalidad para ordenar topológicamente un grafo de nodos hashable.

Un ordenamiento topológico es un ordenamiento lineal de los vértices en un grafo de modo que para cada arista dirigida u -> v desde el vértice u al vértice v, el vértice u viene antes del vértice v en el ordenamiento. Por ejemplo, los vértices del grafo pueden representar tareas a realizar y las aristas pueden representar restricciones de que una tarea debe realizarse antes que otra; en este ejemplo, un ordenamiento topológico es solo una secuencia válida para las tareas. Es posible un ordenamiento topológico completo si y solo si el grafo no tiene ciclos dirigidos, es decir, si es un grafo acíclico dirigido.

Si se proporciona el argumento opcional graph, este debe ser un diccionario que represente un grafo acíclico dirigido donde las claves son nodos y los valores son iterables de todos los predecesores de ese nodo en el grafo (los nodos que tienen las aristas que apuntan al valor clave). Se pueden agregar nodos adicionales al grafo utilizando el add() method.

En el caso general, los pasos necesarios para realizar el ordenamiento de un grafo son los siguientes:

• Cree una instancia TopologicalSorter con un grafo inicial opcional.

• Agregue nodos adicionales al grafo.

• Llame a prepare() en el grafo.

• Mientras is_active() is True, itere sobre los nodos retornados por get_ready() y procéselos . Llame a done() en cada nodo a medida que finaliza el procesamiento.

En caso de que sólo se requiera una ordenación inmediata de los nodos del grafo y no haya paralelismo, se puede utilizar directamente el método de conveniencia TopologicalSorter.static_order().

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

La clase está diseñada para soportar fácilmente el procesamiento en paralelo de los nodos a medida que estén listos. Para la instancia:

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)

Añade un nuevo nodo y sus predecesores al grafo. Tanto el node como todos los elementos de predecessors deben ser hashable.

Si se llama varias veces con el mismo argumento del nodo, el conjunto de dependencias será la unión de todas las dependencias pasadas.

Es posible añadir un nodo sin dependencias (no se proporciona predecessors) o proporcionar una dependencia dos veces. Si un nodo que no se ha proporcionado antes se incluye entre los predecessors, se añadirá automáticamente al grafo sin predecesores propios.

Provoca ValueError si se llama después de prepare().

prepare()

Marca el grafo como terminado y comprueba si existen ciclos en el grafo. Si se detecta algún ciclo, se lanzará CycleError, pero se puede seguir utilizando get_ready() para obtener tantos nodos como sea posible hasta que los ciclos bloqueen más el progreso. Después de una llamada a esta función, el grafo no puede ser modificado, y por lo tanto no se pueden añadir más nodos utilizando add().

is_active()

Retorna True si se puede avanzar más y False en caso contrario. Se puede avanzar si los ciclos no bloquean la resolución y, o bien todavía existen nodos listos que aún no han sido retornados por TopologicalSorter.get_ready() o el número de nodos marcados con TopologicalSorter.done() es menor que el número que han sido retornados por TopologicalSorter.get_ready().

El método __bool__() de esta clase defiere a esta función, por lo que en lugar de:

if ts.is_active():
    ...

es posible hacer simplemente:

if ts:
    ...

Lanzar ValueError si se llama sin llamar previamente a prepare().

done(*nodes)

Marca un conjunto de nodos retornados por TopologicalSorter.get_ready() como procesados, desbloqueando cualquier sucesor de cada nodo en nodes para ser retornado en el futuro por una llamada a TopologicalSorter.get_ready().

Lanza ValueError si algún nodo de nodes ya ha sido marcado como procesado por una llamada anterior a este método o si un nodo no fue añadido al grafo usando TopologicalSorter.add(), si se llama sin llamar a prepare() o si el nodo aún no ha sido retornado por get_ready().

get_ready()

Retorna una tupla con todos los nodos que están listos. Inicialmente retorna todos los nodos sin predecesores, y una vez que éstos se marcan como procesados llamando a TopologicalSorter.done(), las llamadas posteriores devolverán todos los nuevos nodos que tengan todos sus predecesores ya procesados. Una vez que no se puede avanzar más, se retornan tuplas vacías.

Lanzar ValueError si se llama sin llamar previamente a prepare().

static_order()

Retorna un iterable de nodos en un ordenamiento topológico. El uso de este método no requiere llamar a TopologicalSorter.prepare() o TopologicalSorter.done(). Este método es equivalente a:

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

El orden concreto que se retorna puede depender del orden específico en que se insertaron los elementos en el grafo. Por ejemplo:

>>> 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]

Esto se debe a que «0» y «2» están en el mismo nivel en el gráfico (habrían sido retornados en la misma llamada a get_ready()) y el orden entre ellos está determinado por el orden de inserción.

Si se detecta algún ciclo, se lanzará CycleError.

Added in version 3.9.

Excepciones

El módulo graphlib define las siguientes clases de excepción:

exception graphlib.CycleError

Subclase de ValueError planteada por TopologicalSorter.prepare() si existen ciclos en el grafo de trabajo. Si existen múltiples ciclos, sólo se informará de una elección indefinida entre ellos y se incluirá en la excepción.

Se puede acceder al ciclo detectado a través del segundo elemento del atributo args de la instancia de la excepción y consiste en una lista de nodos, tal que cada nodo este, en el grafo, un predecesor inmediato del siguiente nodo en la lista. En la lista reportada, el primer y el último nodo serán el mismo, para dejar claro que es cíclico.