Directed Graphs and Cycles: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
=Internal=
=Internal=
* [[Graph_Concepts#Directed_Graphs_Cycles|Graph Concepts | Directed Graphs Cycles]]
* [[Graph_Concepts#Directed_Graphs_Cycles|Graph Concepts | Directed Graphs Cycles]]
( [[Topological_Sort_of_a_Directed_Acyclic_Graph#Overview|Topological Sort of a Directed Acyclic Graph]]
* [[Topological_Sort_of_a_Directed_Acyclic_Graph#Overview|Topological Sort of a Directed Acyclic Graph]]


=Overview=
=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.
<syntaxhighlight lang='py'>
    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
</syntaxhighlight>
<font color=darkkhaki>TO PROCESS: https://www.geeksforgeeks.org/detect-cycle-in-directed-graph-using-topological-sort/</font>

Latest revision as of 21:29, 19 July 2022

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/