Practice Exercise

Your task is to write a function, hasCycle, that determines whether or not the given graph contains a cycle. It should return true if the graph contains a cycle, and false otherwise.

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 hasCycle.c).
• Vertices are numbered from \(0\) to \(n - 1\), 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/hasCycle/downloads/hasCycle.zip

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

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

hasCycle returned: FALSE

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

hasCycle returned: TRUE

Testing

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

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