Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:holmesr:section_3.1 [2018/02/06 04:37] – holmesr
+++ courses:cs211:winter2018:journals:holmesr:section_3.1 [2018/02/06 04:53] (current) – holmesr
@@ Line 57: / Line 57: @@
 The strong component is an analog to the connected component in an undirected graph. The strong component in a graph G is the set of nodes //n// which are mutually reachable from the nodes //s//. The a set of nodes is a strong component if that set is returned by a BFS started at node //n// on graph G and also returned by a BFS started at node //n// on a graph G<sup>rev</sup> (the graph G with the directions of the edges reversed.) The strong component also has an analogous property to the connected component of undirected graphs that it is identical or disjoint for two nodes.
+===== Section 3.6 DAGS and Topological Orderings  =====
+A Directed Acyclic Graph (DAG) is just what it sounds like, a directed graph containing no cycles. These are useful for representing precedence relations and dependencies because they don't contain cycles. A cycle in a dependency relation would mean that one process could not start until another had taken place, which would never happen because none could start first.
+These types of graphs have can also be represented by a structure known as a topological ordering, which the book defines as "an ordering of the nodes v<sub>1</sub>,...,v<sub>n</sub> such that for every edge (v<sub>i</sub>,v<sub>j</sub>), i<j". Every topological ordering represents a DAG since a topological ordering must have directed edges of course, and these edges can not be in a cycle because eventually that would violate the condition that for every edge (v<sub>i</sub>,v<sub>j</sub>), i<j.
+It is also true that every DAG has a topological ordering, since there must be a node that has no incoming edges due to the fact that there are no cycles in a DAG. Once this node has been removed and removing a node cannot create a cycle, then there is a DAG remaining with all the nodes that were in the previous DAG, except the removed node. This truth can be used to devise an algorithm that runs in O(n<sup>2</sup>) time:
+.find the node with no incoming edges
+.delete this node
+.recursively compute the topological ordering of the DAG without the removed node and add this after the deleted node.
+There is yet a faster, linear-time method to computing the topological ordering of the DAG, but I could not quite grasp what this was. It dealt with active nodes and edges coming from those nodes into the current node.