Directed Acyclic Graphs (DAG) and Topological Sorting in Pythonic Art

Part III of the Holidays Coding Series.

Directed Acyclic Graphs are Graphs without cycles with the property that an edge E exists between any two nodes u, v such that E= {u, v} but *not* {v, u} and no back edges. This property makes DAGs suitable for building dependency chains used in many versatile applications including, but not limited to Crypto-currencies (Distributed Ledgers) both stand-alone (IoTA) and in combination with block chain, Package dependency management for building large software systems (Gradle), Task flow scheduling for Batch processing (e.g. Apache Airflow), Networking protocols such as RPL for Internet of Things among others.

Topological sorting Algorithm for DAG returns a linear ordering of nodes such that for every directed edge uv, node ‘u’ precedes v in order. Topological sorting only works if the DAG is indeed Acyclic.

Depth First Search (DFS) Recursion Stack