Practice Exercise

Your task is to write a function, numWithin, that determines the number of vertices that are within a given distance of the given source vertex.

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 numWithin.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/numWithin/downloads/numWithin.zip

If you're working at home, download numWithin.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
Queue.c	Contains the implementation of a Queue ADT
Queue.h	Contains the interface of a Queue ADT
testNumWithin.c	Contains the main function, which reads in a graph from standard input, calls numWithin and prints out the result
numWithin.c	Contains numWithin, 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

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

Enter the source vertex and maximum distance: 0 5
numWithin(g, 0, 5) = 11
Enter the source vertex and maximum distance: 0 4
numWithin(g, 0, 4) = 11
Enter the source vertex and maximum distance: 0 3
numWithin(g, 0, 3) = 10
Enter the source vertex and maximum distance: 0 2
numWithin(g, 0, 2) = 8
Enter the source vertex and maximum distance: 0 1
numWithin(g, 0, 1) = 5
Enter the source vertex and maximum distance: 0 0
numWithin(g, 0, 0) = 1
Enter the source vertex and maximum distance: 

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

Enter the source vertex and maximum distance: 1 1
numWithin(g, 1, 1) = 3
Enter the source vertex and maximum distance: 1 2
numWithin(g, 1, 2) = 7
Enter the source vertex and maximum distance: 1 3
numWithin(g, 1, 3) = 10
Enter the source vertex and maximum distance: 1 4
numWithin(g, 1, 4) = 11
Enter the source vertex and maximum distance: 4 1
numWithin(g, 4, 1) = 2
Enter the source vertex and maximum distance: 4 4
numWithin(g, 4, 4) = 8
Enter the source vertex and maximum distance: 

Testing

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

make                             # compiles the program
./testNumWithin                  # tests with manual input, outputs to terminal
./testNumWithin < input-file     # tests with input from a file, outputs to terminal
./testNumWithin < 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.