Practice Exercise

Furthest Reachable Vertex

Your task is to write a function, furthestReachable, that returns the furthest vertex that is reachable from a given source vertex. If there are multiple furthest vertices, return the one with the largest vertex number. If the source vertex is not connected to any other vertices, return the 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 furthestReachable.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/furthestReachable/downloads/furthestReachable.zip

If you're working at home, download furthestReachable.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
testFurthestReachable.c	Contains the main function, which reads in a graph from standard input, calls `furthestReachable` and prints out the result
furthestReachable.c	Contains `furthestReachable`, 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

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

Enter the source vertex: 10
Furthest vertex reachable from vertex 10: 12
Enter the source vertex: 12
Furthest vertex reachable from vertex 12: 2
Enter the source vertex: 5
Furthest vertex reachable from vertex 5: 9
Enter the source vertex: 6
Furthest vertex reachable from vertex 6: 13
Enter the source vertex:

./testFurthestReachable
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 10
5 9
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: 0
Furthest vertex reachable from vertex 0: 1
Enter the source vertex: 3
Furthest vertex reachable from vertex 3: 4
Enter the source vertex: 5
Furthest vertex reachable from vertex 5: 11
Enter the source vertex: 6
Furthest vertex reachable from vertex 6: 6
Enter the source vertex:

Hints

Only look at these hints if you are stuck. Note that hints like this will not be supplied in the exam.

One way to start would be to find the distances of each vertex from the starting vertex.

Testing

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

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