Topological Sorting is a linear ordering for vertices of Directed Acyclic Graph. For every directed edge u v, vertex u comes before v in the topological sorting.
Python’s module graphlib introduced in Python 3.9.0, gives the topological sorting of a graph, where the graph is represented in a dictionary. Assume the graph with no parallel edges, the graph can be represented by a dictionary with vertices as keys and values are the nodes to which they are connected.
To install this module run this command into your terminal.
pip install graphlib
We will use class graphlib. TopologicalSorter(graph= None), and the following functions with the TopologicalSorter instance:
add( node, *predecessors ):
Adds a new node and it’s dependencies to a graph. For example, ts.add(3, 2, 1) adds key value 3 and it’s predecessors 2, 1 to the graph.
static_order():
Returns an iterable of nodes in a topological order.
Check the programs below for topological sorting with graphlib.TopologicalSorter()
Example 1: Topological sorting using TopologicalSorter with graph not initialized.
Python3
# Python 3.9.0 program for # topological sorting using # graphlib module from graphlib import TopologicalSorter # creating an instance of TopologicalSorter # initial graph is optional ts = TopologicalSorter() # adding vertex and it's nodes ts.add(3, 2, 1) # adding more node and predecessor ts.add(1, 0) # printing the topological order # returned by static_order() print([*ts.static_order()]) |
Output:
[2, 0, 1, 3]
Example 2: Topological sorting using TopologicalSorter using graph initialized.
Python3
# Python program for topological sorting # through graphlib module from graphlib import TopologicalSorter # making graph graph = {2: {3}, 3: {1}, 4: {0, 1}, 5: {0, 2}} # creating an instance of TopolocialSorter # with initial graph(initial graph is optional) ts = TopologicalSorter(graph) # printing the topological order # returned by static_order() print([*ts.static_order()]) |
Output:
[1, 0, 3, 4, 2, 5]
