Python Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph

This is a Python program to print a topological sorting of a DAG using DFS.

Problem Description

The program allows the user to print a topological sorting of a directed acyclic graph (DAG).

Problem Solution

1. The algorithm works by performing a DFS traversal of the entire graph. This means performing DFS traversal starting at some node in the graph and after the traversal, performing DFS on one of the unvisited nodes if some are still left. This is done until there are no unvisited nodes. Then the finished times corresponding to each node sorted in descending order gives a topological ordering of the DAG.
2. Create classes for Graph and Vertex.
3. Create a function get_topological_sorting_helper that takes a Vertex object v, a set visited, a set on_stack and a list tlist as arguments.
4. It stores a topological sorting in tlist and returns False iff the graph is found to be not a DAG.
5. The set on_stack keeps track of the nodes that are on the stack of the DFS traversal.
6. The functions begins by testing if v is in on_stack and if so, a cycle is present and and False is returned.
7. Otherwise, it adds v to on_stack.
8. For each neighbour of v that is not in visited, get_topological_sorting_helper is called.
9. If the above call returns False, the graph is not a DAG and False is returned.
10. After the loop finishes, v is removed from on_stack and added to visited.
11. The key of v is prepended to tlist.
12. True is returned to indicate that no cycles were found.
13. Create a function get_topological_sorting that takes a graph object as argument.
14. The function returns a topological sorting in a list and returns None if the graph is not a DAG.
15. The function begins by creating an empty list called tlist to store the topological sorting.
16. For each vertex in the graph that has not been visited, it calls get_topological_sorting_helper with tlist.
17. If a call to the helper function returns False, None is returned.
18. If the loop finishes, tlist is returned.

Program/Source Code

Here is the source code of a Python program to print a topological sorting of a DAG. The program output is shown below.

class Graph:
    def __init__(self):
        # dictionary containing keys that map to the corresponding vertex object
        self.vertices = {}
 
    def add_vertex(self, key):
        """Add a vertex with the given key to the graph."""
        vertex = Vertex(key)
        self.vertices[key] = vertex
 
    def get_vertex(self, key):
        """Return vertex object with the corresponding key."""
        return self.vertices[key]
 
    def __contains__(self, key):
        return key in self.vertices
 
    def add_edge(self, src_key, dest_key, weight=1):
        """Add edge from src_key to dest_key with given weight."""
        self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
 
    def does_edge_exist(self, src_key, dest_key):
        """Return True if there is an edge from src_key to dest_key."""
        return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])
 
    def __iter__(self):
        return iter(self.vertices.values())
 
 
class Vertex:
    def __init__(self, key):
        self.key = key
        self.points_to = {}
 
    def get_key(self):
        """Return key corresponding to this vertex object."""
        return self.key
 
    def add_neighbour(self, dest, weight):
        """Make this vertex point to dest with given edge weight."""
        self.points_to[dest] = weight
 
    def get_neighbours(self):
        """Return all vertices pointed to by this vertex."""
        return self.points_to.keys()
 
    def get_weight(self, dest):
        """Get weight of edge from this vertex to dest."""
        return self.points_to[dest]
 
    def does_it_point_to(self, dest):
        """Return True if this vertex points to dest."""
        return dest in self.points_to
 
 
def get_topological_sorting(graph):
    """Return a topological sorting of the DAG. Return None if graph is not a DAG."""
    tlist = []
    visited = set()
    on_stack = set()
    for v in graph:
        if v not in visited:
            if not get_topological_sorting_helper(v, visited, on_stack, tlist):
                return None
    return tlist
 
 
def get_topological_sorting_helper(v, visited, on_stack, tlist):
    """Perform DFS traversal starting at vertex v and store a topological
    sorting of the DAG in tlist. Return False if it is found that the graph is
    not a DAG. Uses set visited to keep track of already visited nodes."""
    if v in on_stack:
        # graph has cycles and is therefore not a DAG.
        return False
 
    on_stack.add(v)
    for dest in v.get_neighbours():
        if dest not in visited:
            if not get_topological_sorting_helper(dest, visited, on_stack, tlist):
                return False
    on_stack.remove(v)
    visited.add(v)
    tlist.insert(0, v.get_key()) # prepend node key to tlist
    return True
 
 
g = Graph()
print('Menu')
print('add vertex <key>')
print('add edge <src> <dest>')
print('topological')
print('display')
print('quit')
 
while True:
    do = input('What would you like to do? ').split()
 
    operation = do[0]
    if operation == 'add':
        suboperation = do[1]
        if suboperation == 'vertex':
            key = int(do[2])
            if key not in g:
                g.add_vertex(key)
            else:
                print('Vertex already exists.')
        elif suboperation == 'edge':
            src = int(do[2])
            dest = int(do[3])
            if src not in g:
                print('Vertex {} does not exist.'.format(src))
            elif dest not in g:
                print('Vertex {} does not exist.'.format(dest))
            else:
                if not g.does_edge_exist(src, dest):
                    g.add_edge(src, dest)
                else:
                    print('Edge already exists.')
 
    elif operation == 'topological':
        tlist = get_topological_sorting(g)
        if tlist is not None:
            print('Topological Sorting: ', end='')
            print(tlist)
        else:
            print('Graph is not a DAG.')
 
    elif operation == 'display':
        print('Vertices: ', end='')
        for v in g:
            print(v.get_key(), end=' ')
        print()
 
        print('Edges: ')
        for v in g:
            for dest in v.get_neighbours():
                w = v.get_weight(dest)
                print('(src={}, dest={}, weight={}) '.format(v.get_key(),
                                                             dest.get_key(), w))
        print()
 
    elif operation == 'quit':
        break
Program Explanation

1. An instance of Graph is created.
2. A menu is presented to the user to perform various operations on the graph.
3. To print a topological sorting of the graph, get_topological_sorting is called.
4. If it returns None instead of a list, the graph is not a DAG.

advertisement
advertisement
Runtime Test Cases
Case 1:
Menu
add vertex <key>
add edge <src> <dest>
topological
display
quit
What would you like to do? add vertex 1
What would you like to do? add vertex 2
What would you like to do? add vertex 3
What would you like to do? topological
Topological Sorting: [3, 2, 1]
What would you like to do? add edge 1 2
What would you like to do? topological
Topological Sorting: [3, 1, 2]
What would you like to do? add edge 2 3
What would you like to do? topological
Topological Sorting: [1, 2, 3]
What would you like to do? add vertex 4
What would you like to do? add vertex 5
What would you like to do? add vertex 6
What would you like to do? add vertex 7
What would you like to do? add edge 4 5
What would you like to do? topological
Topological Sorting: [7, 6, 4, 5, 1, 2, 3]
What would you like to do? add edge 4 6
What would you like to do? topological
Topological Sorting: [7, 4, 5, 6, 1, 2, 3]
What would you like to do? add edge 5 7
What would you like to do? topological
Topological Sorting: [4, 5, 7, 6, 1, 2, 3]
What would you like to do? add edge 3 4
What would you like to do? topological
Topological Sorting: [1, 2, 3, 4, 5, 7, 6]
What would you like to do? quit
 
Case 2:
Menu
add vertex <key>
add edge <src> <dest>
topological
display
quit
What would you like to do? add vertex 1
What would you like to do? topological
Topological Sorting: [1]
What would you like to do? add vertex 2
What would you like to do? add vertex 3
What would you like to do? add edge 1 2
What would you like to do? add edge 2 3
What would you like to do? topological
Topological Sorting: [1, 2, 3]
What would you like to do? add edge 3 2
What would you like to do? topological
Graph is not a DAG.
What would you like to do? quit

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.