done() method of the TopologicalSorter class in Python

Overview:

The done() method of the TopologicalSorter class marks a node of a Directed Acyclic Graph(DAG) as visited.
As all the nodes of the DAG are marked as visited, a TopologicalSorter instance becomes inactive. For example, as a workflow gets complete the workflow becomes inactive.

Citation Graph as a Directed Acyclic Graph

Example:

# A Python example for the parallel sorting
# of nodes from a citation graph in topological order
# Number of worker threads: One
import threading
import queue
from graphlib import TopologicalSorter

# The queues
documentQueue = queue.Queue()
doneQueue = queue.Queue()

# Worker thread function
def worker():
while True:
print("Worker Thread id:%d"%threading.get_native_id())
version = documentQueue.get()
documentQueue.task_done()
doneQueue.put(version)

# Create a worker thread
workerThread1 = threading.Thread(target=worker, daemon=True)

# Start the worker thread
workerThread1.start()

# Citation graph as a Directed Acyclic Graph(DAG)
documents = {"D2":{"D1"},
"D4":{"D1"},
"D4":{"D3"},
"D5":{"D1"},
"D5":{"D4", "D2"},
"D6":{"D5"},
"D7":{"D5", "D4", "D2"}}

topologicalSorter = TopologicalSorter(documents)
topologicalSorter.prepare()

# Loop through the documents
while topologicalSorter.is_active():
# Get a document node that can be visited
for version in topologicalSorter.get_ready():
documentQueue.put(version)
print("Main Thread id:%d"%threading.get_native_id())

# Mark the visited document node as done
vertex = doneQueue.get()
topologicalSorter.done(vertex)
print("From the main thread:%s"%vertex)

# Main thread waiting for worker threads to finish
documentQueue.join()

Output:

Worker Thread id:3169172

Main Thread id:3169171

Worker Thread id:3169172

Main Thread id:3169171

Worker Thread id:3169172

From the main thread:D1

Main Thread id:3169171

Worker Thread id:3169172

From the main thread:D3

Main Thread id:3169171

From the main thread:D2

Worker Thread id:3169172

From the main thread:D4

Main Thread id:3169171

Worker Thread id:3169172

From the main thread:D5

Main Thread id:3169171

Worker Thread id:3169172

From the main thread:D6

Worker Thread id:3169172

From the main thread:D7

Done() method of the TopologicalSorter class in Python

Overview:

Example:

Output: