MTH 607 Graph Theory Assignment 3

General

In this assignment you will implement the Block finding algorithm on a weighted graph G. The block finding algorithm can be found in the Connectivity Handout. Your program will be tested against digraphs as well, the algorithm given should work without modification.

Input

The input will be a (di)graph. (See the preamble for information on how the graph should be input and its format.)

Name

Note your submitted file should be named block.c

Output

Your program should write a file for each block of the graph, containing that component in our standard format (see the preamble). You should use write_graph to write your output files.

These output files should have the file names block.i, where i is an index, from 0 up to the number of blocks - 1. So for example, if there where 4 blocks you would create the files:
block.0 block.1 block.2 block.3

Return Value

Your program should return the number of blocks found.

Notes

You will have to find the size of each block to pass to write_graph.
Note that your arrays for write_graph must have size MAX_N.

In order to use write_graph to write your output files you will have to create a file handle to the file you want to write to. To do this you must include the standard C header file stdio.h and declare a pointer to a file handle. Remember to fclose a file handle before reassigning it. The code to open a file named "foo.bar" for writing looks something like this:

#include < stdio.h >

FILE *fhandle

int get_handle(char *filename)

{

if((fhandle = fopen(filename, "w")) == NULL)

{

	`printf("Error opening write file %s\n", filename);`
	`return -1;`

}

return 0;

}

int write_block()

{

if(get_handle("foo.bar"))

return -1;

write_graph(fhandle, block, block_size);

fclose(fhandle);

return 0;

}

Note that this code is only meant to be illustrative. Using exit() on error is probably better (try man 3 exit).

Maintained by: P. Danziger, March 2008