# Lab Assignment 4

Goals:

1. Understanding of Warshall’s algorithm.

2. Understanding of strongly connected components.

Requirements:

1. Write a program, based on Warshall’s algorithm with successors, to find a leader for each strongly

connected component of a directed graph. The leader of a strongly connected component is the

smallest numbered vertex appearing in that SCC. The input will be formatted as follows:

a. The first line will contain an integer V giving the number of vertices. V will not exceed 50.

b. Tail and head for each edge, one edge per line. The tail and head will be in the range 0 ...

V - 1.

c. A line with -1 -1.

2. Your program’s output for each vertex i will be either 1) the fact that vertex i is a leader or 2) a path

from vertex i to its leader and a path from the leader to vertex i. Your program must also output the

intermediate matrices from your Warshall-based technique.

3. Submit your program source file on Blackboard by 10:45 am on December 4. One of the comment

lines should include the compilation command used on OMEGA.

Getting Started:

1. Review Warshall’s algorithm with successors. Also, consider the usual transitivity diagram and how

it relates to this problem.

2. Test files are available on the course web page. Other cases may be used when your submissions are

checked.

3. Since SCCs treat the graph as being reflexive (e.g. self-loops), each diagonal entry A[i][i] is

initialized to i. If there is an edge from i to j (i!=j), then A[i][j] is initialized to min(i,j).

If there is no edge from i to j, then A[i][j] is initialized to -1 (or some other value depending on

your code).

4. Based on this initialization, Warshall’s algorithm may be modified to terminate with the leader for

the SCC of vertex i stored at A[i][i].

5. Your code must execute in O(V3) time.

6. Static allocation (i.e. no mallocs) is allowed.

7. You may modify http://ranger.uta.edu/~weems/NOTES2320/warshall.c to do this assignment.

1. Understanding of Warshall’s algorithm.

2. Understanding of strongly connected components.

Requirements:

1. Write a program, based on Warshall’s algorithm with successors, to find a leader for each strongly

connected component of a directed graph. The leader of a strongly connected component is the

smallest numbered vertex appearing in that SCC. The input will be formatted as follows:

a. The first line will contain an integer V giving the number of vertices. V will not exceed 50.

b. Tail and head for each edge, one edge per line. The tail and head will be in the range 0 ...

V - 1.

c. A line with -1 -1.

2. Your program’s output for each vertex i will be either 1) the fact that vertex i is a leader or 2) a path

from vertex i to its leader and a path from the leader to vertex i. Your program must also output the

intermediate matrices from your Warshall-based technique.

3. Submit your program source file on Blackboard by 10:45 am on December 4. One of the comment

lines should include the compilation command used on OMEGA.

Getting Started:

1. Review Warshall’s algorithm with successors. Also, consider the usual transitivity diagram and how

it relates to this problem.

2. Test files are available on the course web page. Other cases may be used when your submissions are

checked.

3. Since SCCs treat the graph as being reflexive (e.g. self-loops), each diagonal entry A[i][i] is

initialized to i. If there is an edge from i to j (i!=j), then A[i][j] is initialized to min(i,j).

If there is no edge from i to j, then A[i][j] is initialized to -1 (or some other value depending on

your code).

4. Based on this initialization, Warshall’s algorithm may be modified to terminate with the leader for

the SCC of vertex i stored at A[i][i].

5. Your code must execute in O(V3) time.

6. Static allocation (i.e. no mallocs) is allowed.

7. You may modify http://ranger.uta.edu/~weems/NOTES2320/warshall.c to do this assignment.

You'll get 1 file (871.9KB)