| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionvi [2012/02/21 00:57] – [Designing And Analyzing the Algorithm] mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionvi [2012/02/21 01:34] (current) – [Designing And Analyzing the Algorithm] mugabej |
|---|
| ====== 3.6 Directed Acyclic Graphs and topological Ordering ====== | ====== 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.\\ | 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 ==== | ==== 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.\\ | 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.\\ | In addition, if G is a DAG, then G has a topological ordering.\\ |
| \\ | \\ |
| === Algorithm ===\\ | |
| |
| | **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. |
| |
| >>>>>>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// | |
