done() method of the TopologicalSorter class in Python

The done() method of the TopologicalSorter class, marks the vertex of a DAG as visited.

Topologicalsorter Updated 27 Jul 2021 2 min read

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

python
# 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

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

Main Thread id:3169171

Worker Thread id:3169172

From the main thread:D6

Worker Thread id:3169172

From the main thread:D7