Testing Document

Several tests were performed to guarantee the correctness of the algorithm and the good performance of the applet. The test cases are presented in this document, along with links to execute them or download the graph input corresponding to the test.

Test Cases

For most of the following test cases, graphs have been provided. Selecting the execution link for the graphs will start the applet, and after the applet appears, it will automatically download and attempt to solve the graph.

Keep in mind that applets cannot access files on different servers, and these test cases are located on uhunix2. This means many of the following tests will not run succesfully when the applet is executed from a file system path. All tests do run and produce the expected output, however, from my site.

Note that in the test case descriptions that follow, non-obstacles are shown using the '·' character instead of spaces to improve the readability of the file in a browser. The actual files do not contain these symbols and instead use spaces. Each file is available for download by clicking the “download graph” links at the bottom of each test case.

Functionality of a Component Grabing Input Data

These tests ensure the applet properly handles bad input regarding URL formatting, file validity, and file availability.

Test Case 1
The amount of c values is less than the amount of p values.
3,3
···
···
···
1,1
0	1	1
1	2	1
5	6	7
10
1	2
2	1	1
2	3	2
download graph
execute test
Test Case 2
The amount of p values is less than the amount of c values.
3,3
···
···
···
1,1
0	1
1	2	1
5	6	7
10
1	2	1
2	1	1
2	3	2
download graph
execute test
Test Case 3
The root vertex is out of bounds.
3,3
···
···
···
4,4
0	1	1
1	2	1
5	6	7
10
1	2	1
2	1	1
2	3	2
download graph
execute test
Test Case 4
The c and p matrices do not match the graph size defined on the first line.
3,3
···
···
···
1,1
0	1	1	1
1	2	1	1
5	6	7	1
10
1	2	1	1
2	1	1	1
2	3	2	1
download graph
execute test
Test Case 5
The matrix of obstacles does not match the graph size defined on the first line.
3,3
····
····
····
1,1
0	1	1
1	2	1
5	6	7
10
1	2	1
2	1	1
2	3	2
download graph
execute test
Test Case 6
The file contains a non-ASCII character; in this case, the value 0x1b.
3,3
···
···
···
1,1
0	1	^]
1	2	1
5	6	7
10
1	2	1
2	1	1
2	3	2
download graph
execute test
Test Case 7
The file contains a non-digit character.
3,3
···
···
···
1,1
0	1	b
1	2	1
5	6	7
10
1	2	1
2	1	1
2	3	2
download graph
execute test
Test Case 8
Syntactically wrong string (not URL).
foo://bar
execute test
Test Case 9
Syntactically correct URL, but a file doesn’t exist at the URL (or denied).
http://www.jade-cheng.com/uh/missing.graph
execute test
Test Case 10
Handling of empty string for URL.
execute test

Functionality of a Component Executing the Chosen Algorithm

These tests ensure the applet solves valid graph files and all special cases appropriately.

Test Case 11
There is only one vertex in the graph, and it is the base.
1,1
·
1,1
0
10
1
download graph
execute test
Test Case 12
The root is isolated by obstacles from the rest of the graph.
3,3
·x·
x··
···
1,1
0	1	1
1	2	1
5	6	7
10
1	2	1
2	1	1
2	3	2
download graph
execute test
Test Case 13
The capacity C for the graph is not large enough to clean even one vertex.
3,3
···
···
···
1,1
0	1	1
1	2	1
5	6	7
5
1	6	7
5	5	6
4	7	8
download graph
execute test
Test Case 14
The capacity C for the graph is large enough to clean the entire map.
2,3
···
···
1,1
0	1	2
1	2	1
30
1	6	3
5	5	4
download graph
execute test
Test Case 15
The graph is very large.
8,8
········
··x·····
········
······x·
··x·x·x·
········
·x······
··x·····
1,5
43	91	94	66	0	80	67	31
26	57	0	11	75	8	66	55
24	80	97	63	65	57	84	44
13	95	10	6	54	33	0	62
8	29	0	61	0	95	0	57
84	61	74	60	16	6	78	71
85	0	65	73	48	26	66	60
34	73	0	73	27	64	63	87
1186
30	46	20	91	0	58	67	25
68	46	0	13	32	98	26	45
8	1	25	51	19	4	66	35
72	88	23	65	5	57	0	32
35	55	0	12	0	83	0	21
87	69	9	8	97	17	93	19
33	0	96	31	70	4	50	14
4	20	0	35	57	42	59	85
download graph
execute test

Other Considerations

Many small graphs were created and solved manually and were compared to the results of the applet. For all cases, the solutions match the expected output. Large cases are difficult to solve manually, but after so much thorough testing of the applet, I am extermely confident that the results it displays are accurate.

Links

Valid HTML 4.01 Valid CSS