Directed Graphs and Cycles

From NovaOrdis Knowledge Base
Revision as of 21:29, 19 July 2022 by Ovidiu (talk | contribs) (→‎Detect Cycles using Topological Sort)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Internal

Overview

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/