Solved–Lab Assignment 5– Solution

Description

Goals:

1. Understanding of hashing.

2. Understanding of graphs.

3. Understanding of strongly-connected components (Notes 14).

Requirements:

1. Design, code, and test a C program to determine strongly connected components for a directed graph. You may modify http://ranger.uta.edu/~weems/NOTES2320/dfsSCC.c

1. 1. Input is to be read from standard input (like the first four assignments):

1. 1. 1. The first line is two integer values: n, the number of vertices, and m, the number of edges.

1. 1. 2. The remaining m lines will each contain two values defining an edge: a tail name (string of no more than 25 characters) and a head name (another string).

1. 2. While reading the input, new vertex names should be stored in a double hash table along with consecutively assigned vertex numbers. The first line of your output should indicate the size of your double hash table.

In addition to the double hash table, a table of vertex names will be needed. This is needed when printing your results for the end user.

If the input does not have exactly n different names, give a disparaging message and stop. The assigned vertex numbers are used to build compressed adjacency lists (Notes 14).

1. 3. Perform Kosaraju’s SCC algorithm (Notes 14). The elements of each SCC must be output using the vertex names, not numbers.

2. Submit your C program on Blackboard 10:45 am (section 004) or 1:45 pm (section 003) on November 27. One of the comment lines should include the compilation command used on OMEGA.

Getting Started:

1. Your double hash table should have the smallest prime size to assure a load factor no larger than 90%. You will need code for a simple function to compute this value.

2. The SCCs for a given graph are unique, but the output order could vary.