Directed Graphs and Cycles

Internal

• Graph Concepts | Directed Graphs Cycles
• Topological Sort of a Directed Acyclic Graph

Detect Cycles using Topological Sort

Topologically sort a directed graph, then scan the vertices and ensure that each directed edge complies with the topological order. If there are cycles, there will be at least one that does not.

    def has_cycles(self):
        # iterate over vertices and ensure that each directed edge satisfies
        # the topological sort condition
        for i, v in enumerate(self.adj):
            if v.topological_sort_index == -1:
                raise IllegalStateError(f'unsorted vertex: {i}')
            for head_index in v.heads:
                head_topological_sort_index = \
                    self.adj[head_index].topological_sort_index
                if head_topological_sort_index == -1:
                    raise IllegalStateError(f'unsorted vertex: {head_index}')
                if v.topological_sort_index >= head_topological_sort_index:
                    return True
        return False

TO PROCESS: https://www.geeksforgeeks.org/detect-cycle-in-directed-graph-using-topological-sort/