get_ready() method of Topologicalsorter in Python

The method get_ready() returns the nodes that can be visited in a DAG. The Python example prints the topological ordering for a version tree using two worker threads and a main thread.

Topologicalsorter Updated 27 Jul 2021 1 min read

Overview

  • The method get_ready() returns the nodes that can be visited without any dependency in a DAG.

Example

python
# A Python example doing parallel sorting

            # of the nodes of a version tree in topological order

            # Number of worker threads: Two

            import threading

            import queue

            from graphlib import TopologicalSorter

# The queues

            versionQueue = queue.Queue()

            doneQueue    = queue.Queue()

# Worker thread function

            def worker():

                    while True:

                        print("Id of worker thread:%d"%threading.get_native_id())

                        version = versionQueue.get()

                        versionQueue.task_done()

                        doneQueue.put(version)

# Creation of worker threads

            workerThread1 = threading.Thread(target=worker, daemon=True)

            workerThread2 = threading.Thread(target=worker, daemon=True)

# Start the workers

            workerThread1.start()

            workerThread2.start()

# Version tree as a DAG

            versions =   {"v2":{"v1"},

                           "v4":{"v2"},

                           "v3":{"v2"},

                           "v5":{"v3","v4"},

                           "v6":{"v5"},

                           }

            topologicalSorter = TopologicalSorter(versions)

            topologicalSorter.prepare()

# Loop till all the versions are printed

            while topologicalSorter.is_active():

                # Get a version that is ready

                for version in topologicalSorter.get_ready():

                    versionQueue.put(version)

    # Mark the completed version as done

                vertex = doneQueue.get()

                topologicalSorter.done(vertex)

                print("From the main thread:%s"%vertex)

# Wait for the worker threads to complete

            versionQueue.join()

print("Any version is yet to be done:%s"%topologicalSorter.is_active())

Outlook

python
Id of worker thread:2988733

Id of worker thread:2988734

Id of worker thread:2988734

From the main thread:v1

Id of worker thread:2988734

From the main thread:v2

Id of worker thread:2988733

Id of worker thread:2988734

From the main thread:v4

From the main thread:v3

Id of worker thread:2988733

From the main thread:v5

Id of worker thread:2988734

From the main thread:v6

Any version is yet to be done:False