====== 3.6 Directed Acyclic Graphs and topological Ordering ======
\\

If a directed graph has no cycles, it's called a //Directed Acyclic Graph//(DAG). DAGS can be used to implement dependencies or precedence relations and are widely used in Computer Science.For instance, we can have a set of tasks {1, 2, 3,…, n} to be performed, the condition being that for certain tasks //i// and //j//, //i// must be performed before  //j//. Each task is represented by a node, and there is an edge from //i// to //j// if //i// must be performed before //j//. In this kind of relation, the resulting graph must a DAG since there must be a task that is performed first, otherwise we would have a cycle which would mean that no task could ever be done.A //topological ordering// is an order in which the tasks could be performed so that all dependencies are respected. In other words, for every edge //(v<sub>i</sub> , v<sub>j</sub>)//, we have //i// < //j// and all edges point forward in the ordering. Thus, in a topological order, whenever we come to a task //v<sub>j</sub>//, all the tasks preceding //v<sub>j</sub>// have already been performed. If G has a topological ordering, then G is a DAG. The main problem we have when dealing with a DAG is to find the efficiency of the algorithm that finds its topological ordering.\\

==== Designing And Analyzing the Algorithm ====
\\
 The first node //v<sub>1</sub> in a topological order doesn't have any incoming edge.Every DAG has a node with no incoming edges.\\ 
 In addition, if G is a DAG, then G has a topological ordering.\\
\\

 **Algorithm** \\
\\

To computer a topological ordering on G:\\
Find a node //v// with no incoming edges and order it first\\
Delete //v// from G\\
Recursively compute a topological ordering G-{//v//}\\
and append this order after //v//\\
\\

**Analysis**:\\
\\
-->Identifying a node //v// with no incoming edges takes O(n) time. Thus for n iterations, we get a O(n<sup>2</sup>) time.\\
--> If G contains Θ(n²) edges, then it's linear in the size of the input and the running time is not really bad\\
--> But if we have a number of edges m less than n<sup>2</sup>, a running time of O(m+n) is a much more improvement over Θ(n²).\\
\\
To get a O(m+n) time:\\
\\
--> We declare a node to be "active" if it has not yet been deleted by the algorithm and we keep two things:\\
-->For each node //w//, the number of incoming edges that //w// has from active nodes \\
--> And a set S of all active nodes in G that have no incoming edges from other active nodes.\\
\\
At the start, we initialize both of the above things with a single pass through the graph since all of the nodes are active. Thus S consists of all of the nodes in G.\\
--> With each iteration, we select a node //v// from the set S and delete it.\\
-->After deleting //v// from S, we go through all of the nodes //w// to which //v// had an edge, and subtract one from the number of active incoming edges that we are maintaining for //w//.\\
\\
--> If this causes the number of active edges to //w// to drop to zero, then we add //w// to the set //w//.\\
--> Proceeding in this way, we keep track of nodes eligible for deletion at all times, while spending constant work per edge during the execution of the algorithm.\\
Thus we get a O(m+n) time. \\
\\
Since I wrote this after doing Problem set 4, everything made more sense and the section became really interesting. I give it a 9/10.