Testing Document

Several forms of testing were performed to guarantee the correctness of the algorithm and the good performance of the applet. At the lowest level, many unit tests were executed on the code. In fact, all methods not directly related to the user interface were tested using JUnit. A total of 143 unit tests were implemented.

Running unit tests is helpful, but it is important to know if all the code has been tested. In other words, it does not help to test 5% of the code with lots of duplicate tests. To verify the code was unit tested thoroughly, EclEmma was used to test code coverage. Together with JUnit, EclEmma guaranteed that nearly 100% of the code was unit tested successfully.

Test Data and I/O

At a higher level, the applet was tested using a number of test cases. Most cases were provided by the instructor, but others were created to gain confidence that the algorithm solves all possible graphs optimally.

The following test cases were run, and you can click any of the following links to execute them. 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 on 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.

Functionality of a Component Grabing Input Data

• Sample1 — the sample input text file provided by the grader.

  This graph is solved optimally, and it is animated because it is a small graph.

• Case 1 (a) — syntactically wrong string (not URL).

  The applet flashes in the status label, “Syntactically wrong string (not URL)”.

• Case 1 (b) — syntactically correct URL, but a file doesn't exist at the URL (or denied).

  The applet flashes in the status label, “File doesn't exist at the URL (or denied)”.

• Case 2 (a) — whether there is a limit on the length of input string.

  The applet does not restrict the number of characters on the input string, but there is a theoretical limit placed on the length by the JRE. The path specified here does not exist, but it is valid, so the applet displays the same result as Case 1 b.

• Case 2 (c) — what to do if the empty string is input.

  The applet displays “Please specify a URL before downloading”.

• Case 3.1 (a) — non-ASCII file (binary file, text file including control characters, etc.)

  The applet displays “Non-ASCII file detected”.

• Case 3.1 (b) — non-digit character (alphabetical characters, non-alphanumeric characters, etc.) except delimiters \t and comma

  The applet displays “Invalid character 's' detected”.

• Case 3.2 (a.1) and Case 3.2 (a.2) — the number n of vertices doesn't match with the number of integers appearing on the 3rd line of the test file.

  The applet displays “Invalid graph (inconsistent vertex count)”.

• Case 3.2 (b.1) and Case 3.2 (b.2) — an integer larger than n appears on the 4th line or below.

  The applet displays “Invalid graph (vertex index for edge too large)”.

• Case 3.3 (a.1) and Case 3.3 (a.2) — the number m of edges doesn't match with the number of lines regarding edges starting from the 4th line.

  The applet displays “Invalid graph (inconsistent edge count)”.

• Case 3.4 (a) — there is a line representing a self-loop.

  The applet displays “Invalid edge (self-loop detected at vertex 1)”.

• Case 3.4 (b) — there are duplicated lines representing the same edges.

  The applet displays “Invalid graph (duplicate edge 1..2 detected)”.

• Case 3.4 (c) — a graph represented by the text file is not connected.

  The applet displays “Invalid graph (unconnected graph detected)”.

• Case 3.5 — mixed EOL (End of Line) code such as \n, \r, and both

  The applet loads and solves the graph successfully in all circumstances.

• Case 3.6.1 and Case 3.6.2 — how to process any other syntax error respect to the format of the input text file described in Assignment 2 (e.g., whether rejecting a text file including unnecessary space characters)

  The applet loads and solves the graph successfully in most cases. For example, it will allow extra whitespace at the end of the file as long as there are no more characters in the file. It will also allow whitespace around the commas when readin the edges. The applet does not allow extra tabs around the definition for the vertex weights, though.

Functionality of a Component Executing the Chosen Algorithm

• Case 1.1 — a graph G=(V,E) consisting of a single vertex and no edge; in the text file, n=1 and m=0.

• Case 1.2 — a graph G consisting of 2 vertices and a single edge; in the text file, n=2 and m=1.

• Case 1.3.1 — A graph G consisting of 3 vertices; m=2 --> G is acyclic, i.e., a tree

• Case 1.3.2 — A graph G consisting of 3 vertices; m=3 --> G is cyclic

• Case 2.1 — all weights are 0.

• Case 2.2 — all weights are 1.

• Case 2.3 — each weight is either 0 or 1, at least one vertex with 0, and at least one vertex with 0

• Case 3.1 — m=n-1, i.e., G is a tree

• Case 3.2 — G is generated by generating a tree and then adding k_n edges to it where k is a small positive real number such as 0.3, 0.7 and 1.5

• Case 4.1 — complete graph K_n

• Case 4.2 — G is generated by removing qn(n-1) edges from from K_n where q is a small positive real number such as 0.001, 0.01, 0.05 and 0.2

• Case 5^* — how a large graph G is handled: (a) whether there is a limit on the number n of vertices; (b) huge graph with 1000 or more vertices

  There is no limit placed on the size of the graph, and the applet will solve graphs will 1000 or more vertices (after a short delay). The length of time to solve the graph depends on the speed of the machine executing the applet, but on my Windows XP 2.0 GHz PC at home, a graph with 1000 vertices with 125,637 edges is solved in approximately 59 seconds.

  The visual display of these graphs becomes a problem, however, and the applet does not attempt to draw more than 500 connecting lines.

  If better performance is needed, then it would make sense to implement the graph solver using C or using an algorithm capable of using multiple processors.

  ^*Due to quota limitations, I can no longer provide this test. If you would like a copy, please contact me.

• Case 6 — ordinary graphs G=(V,E) generated as random graphs usage of random number generators; better to use “random numbers” than “pseudorandom numbers”.

  I have provided a button on the applet to solve a pseudo-random graph at any time. The random graph has between 2 and 32 vertices.

  At one time, I had downloaded a large set of truly random numbers from http://www.random.org/, but I found this overcomplicated the code, and I eventually removed it. A user will not notice the difference, and I did not use randomness to prove the correctness of my algorithm. I instead decided to take the (more difficult) approach by providing unit tests and functional tests and by proving my algorithm mathematically in my paper. I left the pseudo-random graph generator in the applet only for the entertainment of the user.

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. Unit testing, functional testing, and user testing have all been performed, and the applet performs as expected.

Links

• Return to the main page.

• View the readme.

• View the operation/user’s manual.

• View the reference manual.