Turn in homework online
Loosely speaking, a biconnected component of an undirected graph G = (V,E) is a maximal subset of the vertices with the property that there are two independent paths between any pair of vertices in the component. (Maximal means you can't enlarge the subset without destroying that property.) More formally, a pair of vertices u != v are in the same biconnected component if there is no third vertex x whose removal disconnects u from v.
For example, the biconnected components of the following graph:
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. (It also has some similarity to the strongly connected components algorithm, in particular in how it lists the vertices in each component.)
Your assignment is:
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.
To simplify your job doing the timing measurements, we'll give you (by early next week) a program that generates random graphs of various sizes in that format.
Update, 3/11/02:Here is the random graph generator:
C source code
Linux binary (ELF)
NT binary
The program generates (somewhat) random graphs in such a
way as to produce (hopefully) interesting examples for the
project. It is a command-line program, and takes three
parameters: the number of vertices, the expected degree of the
graph (expected average number of edges connected to each vertex),
and a random number seed (any integer between 0 and 2^32). To
generate a graph with twelve vertices and expected degree of 6,
you could enter "rndgraph 12 6 6942". (6942 is an arbitrary seed
for the random number generator.)
The generator outputs lines containing integers. The first
line contains the number of vertices in the graph; each successive
line will consist of a pair of numbers, representing an edge
between those two vertices. To save random graph data, pipe the
output to a file, like this:
rndgraph 12 6 6942 > graph-data
The file "graph-data" will then contain the random graph data.
Timing: 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, you may want to disable output formatting and printing during you timing runs. (But let us know if this is the case.)
You may (but don't have to) work in pairs on this assignment. If you do, turn in a clear statement of who worked on the project, and, if you didn't literally work side by side on all phases of the project, who did which parts.
Also implement any other algorithm you like for solving the problem, e.g. the simple but slow one outlined below.
The definition of a biconnected component immediately provides another algorithm for finding them: Namely for every pair of vertices u,v, see whether there is some other vertex x that separates them. You could perhaps use a modified depth-first search algorithm to test whether there is a path fron u to v that does not pass through a specified "forbidden" vertex x.