Finds the transitive closure of a graph. reference: https:en.wikipedia.orgwikiTransitiveclosureIngraphtheory This class represents a directed graph using adjacency lists No. of vertices default dictionary to store graph To store transitive closure Adds a directed edge to the graph A recursive DFS traversal function that finds all reachable vertices for source Mark reachability from source to target as true. Find all the vertices reachable through target The function to find transitive closure. It uses recursive dfsutil Call the recursive helper function to print DFS traversal starting from all vertices one by one
class Graph:
    """
    This class represents a directed graph using adjacency lists
    """
    def __init__(self, vertices):
        # No. of vertices
        self.vertex_count = vertices

        # default dictionary to store graph
        self.graph = {}

        # To store transitive closure
        self.closure = [[0 for j in range(vertices)] for i in range(vertices)]

    def add_edge(self, source, target):
        """
        Adds a directed edge to the graph
        """
        if source in self.graph:
            self.graph[source].append(target)
        else:
            self.graph[source] = [target]

    def dfs_util(self, source, target):
        """
        A recursive DFS traversal function that finds
        all reachable vertices for source
        """

        # Mark reachability from source to target as true.
        self.closure[source][target] = 1

        # Find all the vertices reachable through target
        for adjacent in self.graph[target]:
            if self.closure[source][adjacent] == 0:
                self.dfs_util(source, adjacent)

    def transitive_closure(self):
        """
        The function to find transitive closure. It uses
        recursive dfs_util()
        """

        # Call the recursive helper function to print DFS
        # traversal starting from all vertices one by one
        for i in range(self.vertex_count):
            self.dfs_util(i, i)

        return self.closure
