Topological Sorting
Background
Provided it is a Directed Acyclic Graph, top-logical ordering, or topological sorting is a linear sorting process whereby in a vertex V1, V2…Vn, in a pattern that edge Vi is directed towards Vj, then Vi comes before Vj. If every consecutive node in topological ordering does not have an edge the DAG will NOT Have unique order. It can be seen as an hierarchical process of executing a task, in which the topmost task must be done before the second order can be done. The reason we use this sorting system is to quickly compute shortest paths through a weighted directed acyclic graph.
As example, topological ordering of this graph is in order B, A, D, C, E.
Terms
A Sink is a vertex with no outgoing edges. In Fig.1, the arrow-head indicates where the edge is moving to, and E is glaringly the sink here.
A Source on the other hand, is a vertex with no incoming edges. an example of this is edge B, only has outgoing edges.
Ordering
Starting ordering priority from the source of the graph which is B, then looking for the next source after removing B and its edges. A will be left out as the new source, then repeating the same process. D then becomes the next source, removing its edges, C and the E.
Algorithm
The first thing done here is to import defaultdict. This works exactly like a normal dict, but it is initialized with a function (“default factory”) that takes no arguments and provides the default value for a nonexistent key. It is imported from collections; which contains many useful data structures to store information in memory. Basically this is used to add edge to the graph.
The topological sort is a recursive function of O(n),
and the it satisfies the 3 laws of recursion.
Application
Application of Topological Sort includes Building Systems that are dependent of each other, Advance Packaging Tools(apt-get) for packing and uninstalling and installing softwares in linux , Prerequisite Problems like prerequisite(s) of a course in schools, Task Scheduling of inter-dependent task in order of execution.
References:https://www.geeksforgeeks.org/topological-sorting/ https://en.wikipedia.org/wiki/Topological_sorting https://www.coursera.org/lecture/algorithms-on-graphs/topological-sort-jf9lY https://www.hackerearth.com/practice/algorithms/graphs/topological-sort/tutorial/ https://www.accelebrate.com/blog/using-defaultdict-python/ https://www.google.com/search?client=ubuntu&hs=yAt&channel=fs&ei=M9ebW8P3NKuNlwSS27XQDA&q=how+to+use+topological+sort&oq=how+to+use+topological+&gs_l=psy-ab.3.0.33i22i29i30k1.2009679.2024207.0.2026386.39.32.5.0.0.0.661.5574.2-7j4j1j3.15.0....0...1.1.64.psy-ab..20.19.5327...0j0i67k1j35i39k1j0i131k1j0i22i30k1.0.b4hK0W2-PPY#kpvalbx=1
