Chapter 3 - Graphs

Summary: Section 3.1 is Basic Definitions and Applications. Graphs consist of nodes and edges, where the edges join two nodes. Graphs can be undirected or directed, and graphs are assumed to be undirected unless stated otherwise. Technically, an edge between nodes u and v in an undirected graph is represented as the set {u,v}, but the authors warn that the notation for a directed edge, (u,v), will sometimes be used even for undirected edges. The directed edge (u,v) is an edge from u to v. Transportation, communication, information, social, and dependency networks are examples the authors provide for where graphs are used. The section also addresses paths (simple or cyclical), connectivity (including strong connectivity for directed graphs), and shortest path/distance between two nodes. Trees are connected graphs that have no cycles - they're “the simplest kind of connected graph: deleting any edge from a tree will disconnect it” (p77). While on the topic of trees, the authors state that “rooted trees are fundamental objects in computer science, because they encode the notion of a hierarchy” (p78). The section closes with a list of three statements about undirected graphs with n nodes, such that if any two are true so also is the third.

My Questions: Not exactly a question, but I wonder why the authors introduced trees in this section after we've already seen balanced binary trees when talking about the heap implementation of the priority queue. For example, it's an information repeat to tell us about parents and children.

Second Time Around: Honestly, everything in this chapter I'd seen before in MATH301 (except the Note to Self) and/or it was crystal clear in class.

Note to Self: In the information networks example (p75), it says that search engines use hyperlink edges between webpage nodes to determine what webpages are the most important. I didn't know that, but makes sense and it's certainly cool.

Readability: 10 - super straightforward. A relief after section 2.5.

Summary: Section 3.2 is Graph Connectivity and Graph Traversal. Given two nodes s and t of a graph G = (V,E), connectivity is defined as there being a path from s to t. There are two algorithms for answering whether s and t are connected: breadth-first search (BFS) and depth-first search (DFS). BFS starts with node s, and then adds nodes in layers based on them being connected to the node(s) in the previous layer. Layer zero, then, is just node s. Layer one consists of all nodes connected to s. Layer two consists of all nodes connected to the nodes connected to s. And so on, until there are no nodes left that aren't already in a layer. Because the distance between two nodes is defined as the “minimum number of edges on a path joining them” and a node will be absent from all layers “if and only if there is no path to it” (p 80), BFS not only determines if there is a path between nodes s and t, but it also determines the shortest path. BFS is also a method for finding a connected component, which is the set of all nodes reachable from a starting node. Another method for finding a connected component is DFS. In DFS, you traverse as deeply as possible and only backtrack when you hit a dead end. While the BFS tree shows the shortest path from s to t and ends up being short and bushy, the DFS tree will usually be long and spindly. Finally, we can also determine the set of all connected components. Because for two nodes in a graph their connected components will either be identical or disjoint (3.8), we can start with any node, find its connected component, then if there were any nodes not visited in that search we find its connected component. If we continue until all nodes are visited, we will find the set of all connected components of the graph.

My Questions: So, how do we say that two search trees are equal? Or is that even a question that we ask? Are two BFS trees equal if the same nodes appear in the same layers, or must the connections all be identical? This relates to question 1.d. on PS 3.

Second Time Around: Theorem 3.4, which says that if (x,y) is an edge in the graph, then the layers in which they appear for BFS differ by at most 1, made more sense the second time around. In class, I was a little lost, but now that I've seen it twice I think I've got it.

Note to Self: I want to remember Theorem 3.8. It makes sense, I just hadn't thought about it before.

Readability: 7. I think the u's, v's, s's, and t's running around the section were hard to keep track of at times.

Summary: Section 3.3 is Implementing Graph Traversal Using Queues and Stacks. This section finally addresses using lists vs arrays to represent graphs, and whether a queue or a stack is better for implementing BFS and DFS. There are two ways to represent a graph: adjacency matrix or adjacency list. While the authors introduce both, they choose to use the adjacency list. Before weighing the pros and cons of using an adjacency matrix vs list, the authors comment on using both input parameters (number of nodes and number of edges) to determine runtime because it is difficult to say, for example, whether O(m^2) or O(n^3) is better. It depends on the relationship between the number of nodes and edges. Since we aim for polynomial runtime in general, we aim for O(m+n) runtimes in this section. In terms of space requirements, the adjacency list wins. The adjacency matrix requires O(n^2) space, whereas the adjacency list require O(m+n) space. In terms of accessing information, the authors also argue in favor of the adjacency list. They say that “if the algorithm is currently looking at a node u, it can read the list of neighbors in constant time per neighbor” (p 89), which leads to a natural sense of “exploring” the graph. Before moving on to the implementation details of BFS and DFS, the section reviews queues and stacks: queues are FIFO, stacks are LIFO, and both can be implemented with a doubly-linked list which keeps pointers to both the head and the tail. BFS will be implemented using a queue, and DFS with a stack.

My Questions: The authors note: “a running time of O(m+n) is the same as O(m), since m >= n-1” (p 87). Why, then, do we bother saying runtimes are O(m+n) when, according to the authors, it's the same as O(m)? Also, why did the authors decide to only write out a partial DFS algorithm? The algorithm on page 93 does not include the processes involved with adding edges to the tree, which is annoying.

Second Time Around: I don't think I was aware the first time talking about BFS in class that we're representing the layers like an adjacency list: an array of lists. That's clear to me now.

Note to Self: The subsection about finding the set of all connected components made a comment that BFS and DFS “spend work only on edges and nodes in the connected component containing the starting node. (they never see any of the other nodes or edges)” (p 94). That's why finding the set of all connected components is still O(m+n) even though the algorithms to find one connected component (BFS or DFS) are O(m+n) themselves.

Readability: 6. I don't think the authors did a great job of making the algorithm implementations clear. I had to read a few things multiple times. For example, its not clear whether the sentence, “The adjacency list data structure is ideal for implementing breadth-first search” (p 90), refers to having the graph in that form or making the layer data structure an adjacency list, or both. Also, the sentence, “each node occurs on at most one list” (p 91), confused me at first because I was thinking of the graph's adjacency lists where each node is actually represented twice, but it's talking about the layers. It's true that each node appears in only one layer. Other things are stated without much explanation. “Note that there are at most n lists L[i]” doesn't have an explanation, but I presume it's because in the worst case the graph is a line and there is only one node per layer. Also, “we spend O(1) time considering each edge” doesn't have an explanation, but I presume that's true because we're assuming the graph is represented using an adjacency list and you can get to the next edge in the list of a node's edges in constant time.

Summary & Motivations: Section 3.4 is Testing Bipartiteness: An Application of Breadth-First Search. A graph is bipartite if the nodes can be partitioned into two sets, call them X and Y, where every edge connects one node in X and one node in Y. The problem presented in this chapter is figuring out a way to determine if a graph is bipartite. Theorem 3.14 states that a graph with an odd cycle cannot be bipartite, but the authors ask, “Are there other, more complex obstacles to bipartiteness?” (p 95).

About the Algorithms: The algorithm for determining whether or not a graph is bipartite involves coloring the starting node red, its neighbors blue, its neighbors' neighbors red, and so on in layers. If we end up with a valid coloring, the graph is bipartite; if we do not, the graph is not. At the implementation level, all we have to do is modify the BFS algorithm. We add an array Color over the nodes, then in BFS when “we are adding a node v to a list L[i+1], we assign Color[v] = red if i + 1 is an even number, and Color[v] = blue if i + 1 is an odd number” (p 96). At the end, we scan the edges and determine if any edge has both ends in the same color, which would be an invalid coloring. The authors analyze this algorithm to show that it both correctly determines if a graph is bipartite and “shows that we can find an odd cycle in G whenever it is not bipartite” (p 96).

My Questions: Not a question, but I wish the authors were more explicit when giving the runtime of algorithms. On page 96, they say, “At the end of this procedure, we simply scan all the edges and determine whether there is any edge for which both ends received the same color. Thus, the total running time for the coloring algorithm is O(m+n), just as it is for BFS.” I wish they would break the process down a little more and say where the components of the runtime come from.

Second Time Around: I could have sworn we talked in class about doing BFS first, and then coloring the layers that were produced in order to implement the algorithm to determine a graph's bipartiteness. I was uncomfortable with that idea. I wanted to just do everything at the same time. After reading, though, it sounds like that's what we're supposed to do because we add a Color array and assign nodes colors as we go. It makes more sense now.

Note to Self: It's possible to build off of algorithms that we already know. Here, we're starting with BFS and modifying it to answer our question about a graph's bipartiteness.

Readability: 8 - pretty easy read, but like I said in “My Questions,” I wish the authors would break things down a little more.

Summary: Section 3.5 is Connectivity in Directed Graphs. We recall that directed graphs have edges with directionality. An edge (u,v) is said to go from node u to node v. There is not necessarily also an edge (v,u) from v to u. Even though our edges now have a direction, we can still talk about BFS and DFS. First, the matter of representing a directed graph. We still us an adjacency list, but now we have two lists for each node: one for the nodes to which it has edges, another for the nodes from which it has edges. BFS and DFS work almost exactly the same for directed graphs as for undirected graphs, except that we follow edges based on their directionality. For BFS, we follow the edges out of nodes and ignore the edges in. For DFS, “when DFS is at a node u, it recursively launches a depth-first search, in order, for each node to which u has an edge” (p 98). The last subsection is about strong connectivity, which means that for every two nodes in the graph, there is a path between them in both directions (every pair of nodes is “mutually reachable”). We can determine in linear time whether a graph is strongly connected: run BFS on G and on G_{rev}, and if either of the searches “fails to reach every node, then clearly G is not strongly connected” (p 98). Finally, say the graph is not strongly connected. We can find the strong component by taking the intersection of the nodes reached by BFS on G and G_{rev}.

My Questions: Is there such a thing as bipartiteness for a directed graph?

Second Time Around: At first, I thought that you might end up adding nodes multiple times to a BFS tree of a directed graph or have some weird structure other than a tree if a later node goes back to an earlier node. Then I recalled that the BFS algorithm prescribes adding a node to a layer only if it not already Discovered.

Note to Self: Finding the set of nodes with paths to s, rather than the set of nodes to which s has paths (p 98) has a clever solution: do some preprocessing to arrive at a new graph, G_{rev}, where all edges of G are reversed, and then run BFS or DFS.

Readability: 9 - pretty smooth sailing here, and my confusion was resolved.

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: 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: 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.

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: 9 - I thought this section was pretty straightforward.