| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2018:journals:melkersonr:chapter3 [2018/02/06 22:27] – [Section 3.5] melkersonr | courses:cs211:winter2018:journals:melkersonr:chapter3 [2018/02/06 22:33] (current) – [Section 3.6] melkersonr |
|---|
| |
| * **Summary & Motivations:** Section 3.6 is Directed Acyclic Graphs and Topological Ordering. A directed acyclic graph (DAG), is a directed graph with no cycles. A common example of a DAG is a dependency network - like for course prerequisites, or a list of tasks where some must be done before others or the output of some is the input of others. We represent such relationships by giving each task a node, and for each instance where task i must be done before task j we have the directed edge (i,j). Presented with a DAG that represents dependencies, it's natural to ask for a valid ordering of the tasks. Such an ordering is called a topological ordering. Theorem **3.18** says that "If G has a topological ordering, then G is a DAG" (p 101). We now ask whether every DAG has a topological ordering and if it does how we can find it. | * **Summary & Motivations:** Section 3.6 is Directed Acyclic Graphs and Topological Ordering. A directed acyclic graph (DAG), is a directed graph with no cycles. A common example of a DAG is a dependency network - like for course prerequisites, or a list of tasks where some must be done before others or the output of some is the input of others. We represent such relationships by giving each task a node, and for each instance where task i must be done before task j we have the directed edge (i,j). Presented with a DAG that represents dependencies, it's natural to ask for a valid ordering of the tasks. Such an ordering is called a topological ordering. Theorem **3.18** says that "If G has a topological ordering, then G is a DAG" (p 101). We now ask whether every DAG has a topological ordering and if it does how we can find it. |
| * **About the Algorithms:** An algorithm to answer our question above does exist. Finding that topological ordering involves first selecting a node with no incoming edges, for we know that it doesn't depend on the completing of any other task. We know that there is always at least one node with no incoming edges because otherwise there would be a cycle in the graph and it wouldn't be a DAG. Furthermore, every DAG does have a topological ordering, which the authors prove by induction. Once we find this node that has no incoming edges, we delete it from the graph. Doing so does only removes edges, rather than adding them, so no cycle could be created and the graph is still a DAG. We continue the process of finding a node with no incoming edges and deleting that node, adding that node after the one before, until all nodes are deleted. We end up with a topological ordering for the DAG, but there could be multiple valid orderings. This algorithm is O(n^2) without any cleverness in finding a node with no incoming edges. If we're clever, though, we can get O(n+m) runtime. We facilitate this cleverness by maintaining knowledge about which nodes haven't been deleted yet ("active" nodes): for each node, the number of incoming edges from active nodes; and a set of all active nodes that have no incoming edges from other active nodes. Then we simply select a node to delete from that set, go through the nodes to which it had an edge, and subtract one from its value for the number of active incoming nodes. If that number drops to zero, we add that node to the set. | * **About the Algorithms:** Finding a topological ordering involves first selecting a node with no incoming edges, for we know that it doesn't depend on the completion of any other task. We know that there is always at least one node with no incoming edges because otherwise there would be a cycle in the graph and it wouldn't be a DAG. Furthermore, every DAG does have a topological ordering, which the authors prove by induction. Once we find this node that has no incoming edges, we delete it from the graph. Doing so does only removes edges, rather than adding them, so no cycle could be created and the graph is still a DAG. We continue the process of finding a node with no incoming edges and deleting that node, adding that node after the one before, until all nodes are deleted. We end up with a topological ordering for the DAG, but there could be multiple valid orderings. This algorithm is O(n^2) without any cleverness in finding a node with no incoming edges. If we're clever, though, we can get O(n+m) runtime. We facilitate this cleverness by maintaining knowledge about which nodes haven't been deleted yet ("active" nodes): for each node, maintain the number of incoming edges from active nodes; and a set of all active nodes that have no incoming edges from other active nodes. Then we simply select a node to delete from that set, go through the nodes to which it had an edge, and subtract one from its value for the number of active incoming nodes. If that number drops to zero, we add that node to the set. |
| * **My Questions:** | * **My Questions:** Is there a reason to talk about directed cyclic graphs? |
| * **Second Time Around:** We weren't able to cover the part where we improve the runtime for finding a topological ordering form O(n^2) to O(n+m) in class. It's a good example of first finding a brute force solution (and a solution that works), and then improving it. | * **Second Time Around:** We weren't able to cover the part where we improve the runtime for finding a topological ordering form O(n^2) to O(n+m) in class. It's a good example of first finding a brute force solution (and a solution that works), and then improving it. |
| * **Note to Self:** If a graph depicting dependencies contained a cycle C, "there would be no way to do any of the tasks in C: since each task in C cannot begin until some other one complete, no task in C could ever be done, since none could be done first" (p 100). That makes sense, but I'm not sure I would have thought of it without being asked, "If there were a cycle, could any of the tasks in the cycle be completed?" | * **Note to Self:** If a graph depicting dependencies contained a cycle C, "there would be no way to do any of the tasks in C: since each task in C cannot begin until some other one complete, no task in C could ever be done, since none could be done first" (p 100). That makes sense, but I'm not sure I would have thought of it without being asked, "If there were a cycle, could any of the tasks in the cycle be completed?" |
| * **Readability:** | * **Readability:** 9 - I thought this section was pretty straightforward. |
