|
CSE 417, Wi '05: Assignment #5, Due: Monday, February 28, 2005 |
|
 CSE Home |
About Us |
Search |
Contact Info |
This assignment is part written, part programming. It all focuses on the articulation points algorithm presented in class, and the related problem of decomposing a graph into its biconnected components. I strongly recommend that you do parts 1, 2 and 3 before you start the programming portion, and do them soon so you have time to ask questions before you get immersed in coding.
A vertex in a connected undirected graph is an articulation point if removing it (and all edges incident to it, i.e. touching it) results in a non-connected graph. As important special cases, a graph having a single vertex has no articulation points, nor does a connected graph having just two vertices (which of course must be joined by an edge, otherwise it isn't connected).
A connected graph is biconnected if it has no articulation points. A biconnected component of an undirected graph G = (V,E) is a maximal subset B of the edges with the property that the graph GB = (VB,B) is biconnected, where VB is the subset of vertices incident to (touched by) edges in B. (Maximal means you can't enlarge B without destroying its biconnected property.)
Above, I noted that a graph consisting of single edge is biconnected. Consequently, every edge in G is part of some biconnected component. In fact, every edge is part of exactly one biconnected components (basically because if it were part of two, their union would also be biconnected, contradicting the "maximality" condition). So, the biconnected components partition the edges.
For example, the biconnected components of this graph
are the five sets of edges:
There is a very close relationship between biconnected components and articulation points. Namely, the articulation points are exactly the vertices at which two biconnected components are connected. Given this fact, it shouldn't be a big surprise that there is a linear time algorithm that identifies the biconnected components of a graph, and in fact this algorithm is quite similar to the articulation point algorithm.
Find the articulation points in this graph
by simulating
the algorithm presented in class. Redraw the graph showing tree
edges, back edges, the DFS number and LOW value assigned to each
vertex. For definiteness, start your DFS at vertex C and
whenever the algorithm has a choice of which edge to follow
next, pick the edge to the alphabetically first vertex among the
choices.
Find the biconnected components of the graph in part 1.
Give a modification of the articulation-points algorithm that finds biconnected components. Describe the algorithm (in English; should only take a few sentences). Simulate it on the example in part 1, showing enough of a trace of the algorithm's execution to demonstrate that it finds exactly the components you found in part 2. [Hints: look carefully at the order in which the articulation points algorithm in part 1 explores edges and discovers articulation points, and relate this to which edges are part of which biconnected components. Initially, focus on the first biconnected component to be completely explored by the depth-first search.]
Implement, test, and time the algorithm you found in part 3.
Input format: To keep things simple, assume the input will consist of a positive integer "n" followed by some number of pairs of integers in the range 0 to n-1. "N" represents the number of vertices in the graph, and each pair u v represents an edge between vertices u and v. Although a good program really should check for the following malformed inputs, you may simply assume that you never get: negative numbers, numbers outside the range 0 to n-1, an even number of integers in total (i.e. the last pair is unfinished), or a pair u v where u=v, or where either (u,v) or (v,u) duplicates a previous pair in the list.
Output Format: Print out the number of nodes, number of edges, number of biconnected components, number of articulation points, list the articulation points, list the edges in each biconnected component, and the algorithm's run time (excluding input/output; see below).
Timing: Also run it on a variety of graphs of different sizes and different densities (average number of edges per vertex) and measure its run time on each.
Write a brief report (2-3 pages, say) summarizing your measurements. Include a graph (old fashioned scatter plot) of run time versus problem size. Compare to the theoretical big-O bounds for your sample graphs. Are your observations in line with the dogma I've been spouting all quarter about the utility of big-O analysis? Are there discrepancies? Can you explain them? Does number of edges versus number of vertices have any bearing on performance? Also, if possible, give us a quick summary of the kind of processor on which you ran your timing tests. E.g., "233 Mhz Intel Pentium II with 64k cache and 96Mb RAM."
To simplify your job doing the timing measurements, we have provided a program that generates random graphs of various sizes in that format.
Two hints on timing measurements: it may be so fast on small graphs that you can't get accurate times. If so, rerun it several times on the same input and measure total time. Also, record separately or exclude from your timing measurements the time spent reading inputs, since this may dominate the interesting part. Similarly, except for the summary parameters giving numbers of vertices, edges and components, you may want to disable output formatting and printing during you timing runs.
Electronic Turn In: Turn in your code online via one of the following web forms. (Please do not email them to me this time.)
Paper turn in: parts 1-3, the the test case from 4a, the written report from 4b, and program listings.
Also implement any other algorithm you like for solving the problem, e.g. the simple but slow one outlined below. It turns out that two (different) edges are in the same biconnected component if and only there is a simple cycle in G that includes both. So, you could do something like this: for every pair of edges, try to find a path from one to the other (maybe by DFS or BFS), and then try to find a path back, excluding the edges in the path already taken.
 |
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to cse417-webmaster@cs.washington.edu] |