Practice Exercise

Your task is to write a function, numReachable, that returns the number of vertices that are reachable from a source vertex in the given graph, including the source vertex itself.

Assumptions and Constraints

• The graph contains at least one vertex.
• The graph uses the adjacency list representation, and the graph struct is defined in Graph.h (and is therefore accessible from numReachable.c).
• Vertices are numbered from \(0\) to \(n - 1\), where \(n\) is the number of vertices.
• The source vertex is between \(0\) and \(n - 1\) (inclusive), where \(n\) is the number of vertices.
• The given graph should not be modified.

Download

While in your practice exercises directory, run the following command:

unzip /web/cs2521/practice-exercises/graphs/numReachable/downloads/numReachable.zip

If you're working at home, download numReachable.zip by clicking on the above link and then unzip the downloaded file.

Files

Graph.c	Contains code for creating and printing a Graph
Graph.h	Contains the definition of the Graph data structure and function prototypes
testNumReachable.c	Contains the main function, which reads in a graph from standard input, calls numReachable and prints out the result
numReachable.c	Contains numReachable, the function you must implement
Makefile	A makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic tests
autotest	A script that uses the tests in the tests directory to autotest your solution. You should only run this after you have tested your solution manually.

Examples

./testNumReachable
Enter number of vertices: 12
Enter number of edges: 11
Enter 11 edges in the form `v w` (no quotes):
0 8
0 3
3 8
0 10
10 2
1 9
1 5
5 9
4 6
4 7
4 11
Number of vertices: 12
Number of edges: 11
Edges:
 0: 3 8 10
 1: 5 9
 2: 10
 3: 0 8
 4: 6 7 11
 5: 1 9
 6: 4
 7: 4
 8: 0 3
 9: 1 5
10: 0 2
11: 4

Enter the source vertex: 2
Number of vertices reachable from vertex 2: 5
Enter the source vertex: 1
Number of vertices reachable from vertex 1: 3
Enter the source vertex: 4
Number of vertices reachable from vertex 4: 4
Enter the source vertex: 

./testNumReachable
Enter number of vertices: 12
Enter number of edges: 7
Enter 7 edges in the form `v w` (no quotes):
0 1
2 3
3 4
5 9
5 10
9 11
10 11
Number of vertices: 12
Number of edges: 7
Edges:
 0: 1
 1: 0
 2: 3
 3: 2 4
 4: 3
 5: 9 10
 6:
 7:
 8:
 9: 5 11
10: 5 11
11: 9 10

Enter the source vertex: 1
Number of vertices reachable from vertex 1: 2
Enter the source vertex: 3
Number of vertices reachable from vertex 3: 3
Enter the source vertex: 6
Number of vertices reachable from vertex 6: 1
Enter the source vertex: 9
Number of vertices reachable from vertex 9: 4
Enter the source vertex: 

./testNumReachable
Enter number of vertices: 11
Enter number of edges: 12
Enter 12 edges in the form `v w` (no quotes):
0 5
1 2
1 3
1 4
2 3
2 4
3 4
5 6
6 7
7 8
8 9
9 10
Number of vertices: 11
Number of edges: 12
Edges:
 0: 5
 1: 2 3 4
 2: 1 3 4
 3: 1 2 4
 4: 1 2 3
 5: 0 6
 6: 5 7
 7: 6 8
 8: 7 9
 9: 8 10
10: 9

Enter the source vertex: 3
Number of vertices reachable from vertex 3: 4
Enter the source vertex: 9
Number of vertices reachable from vertex 9: 7
Enter the source vertex: 

Testing

You can compile and test your function using the following commands:

make                                # compiles the program
./testNumReachable                  # tests with manual input, outputs to terminal
./testNumReachable < input-file     # tests with input from a file, outputs to terminal
./testNumReachable < tests/01.in    # for example, tests with input from tests/01.in
                                      # (then manually compare with tests/01.exp)

After you have manually tested your solution, you can autotest it by running ./autotest. This will run some basic tests on your program, as well as check for memory leaks/errors.

It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note that you will need to check the output yourself.