The Main and Other Primary Methods of the Program
To solve this problem of calculating Ramsey numbers, we created a program that would search for subgraphs of user-determined sizes within a larger graph of a guessed number of nodes, which is essentially a guess at the value of the Ramsey number for the inputted subgraph sizes. The program creates a representation of the guess-sized graph in the computer and cycles through all possible coloring schemes. In all the schemes, the program tries to find a coloring that has no monochromatic colorings of either size of subgraph, what we defined to be a “good” coloring. If it finds such a coloring, then the program will exit knowing that that the Ramsey number is larger than the guess. If the program finds no colorings with no monochromatic subgraphs of either color, then the program reports that the Ramsey number is less than or equal to the guess. (For a visual representation of the steps taken by the program, see Appendix A, Figure 1 for a flowchart. Please refer to this diagram throughout this section of the report.)
In writing the program to solve our problem, we considered various programming languages and ultimately chose Java. Java provided features like portability that were important for our project. While we planned to run the program on home PCs, we have plans to also run the program on a supercomputer, many of which use UNIX. Therefore, being able to move our code from machine to machine with ease is essential. Additionally, features like garbage collection and object orientated capabilities helped with processor and memory management as well as program simplification. Java also can easily output data graphically, which would be useful for such a visual problem like ours. It should be noted that Java is sometimes criticized for its possibly slower performance compared to languages like C++ because it has an additional layer between the code and the processor: the Java Virtual Machine. However the performance differences between Java and other languages has been significantly reduced in previous years, and therefore, we ultimately found that Java’s benefits outweighed any shortcoming for our applications.
The program to calculate Ramsey numbers starts by requesting three inputs, all positive integers. (Input windows: Appendix B, Figure 1) The inputs are:
- A guess at the value of the Ramsey number the user would like to calculate. This would be the number of nodes in the larger graph, the graph within which the program would search for monochromatic subgraphs. This value is saved to a variable named ptsInMap. (Here in, we will refer to this graph that we search inside as the “larger graph” because it is larger than the subgraphs discussed next.)
- The values r and b in the expression R(r,b). These are the sizes of the subgraphs that the program will be searching for within the larger graph. The program saves these values to two variables named submapSize1 and submapSize2. SubmapSize1 is always made to be the larger of the two if the two are not equal.
Note that the program has error catching and logic checks to ensure that all inputs are possible.
After these values are inputted and saved, the program goes on to create the array that will represent the larger graph. While initially we considered using advanced dynamic data structures like Java’s hash map, we determined while keeping with the motto “keep it simple” that a simple array would have used less overhead processing time, thus making the program more efficient and thereby fulfilling a major goal of the project.
The array that represented the larger graph is called theMap. In principle, it represents and contains all the information about the edges between all of the nodes in the graph. It is an unbalanced, two-dimensional, Boolean array (see Appendix A, Figure 2 for a concise and visual explanation of the array). In Java, multi-dimensional arrays are stored as arrays of arrays. Our first array that contained the sub-arrays was as long as the number of points in the graph (ptsInMap). The sub-arrays were as long as their index in the first array. Note that in doing this, the program is essentially assigning each node an index value going from 0 to ptsInMap. Each edge of the graph is then represented by a cell in theMap whose indices are the two nodes at the ends of the edge. The edge’s color is determined by the Boolean value of its cell in the array: the two “colors” are true and false.
Note that this array is unbalanced so that only one cell represents each edge (there is only one cell that shares the same two indices). This helps in multiple ways. First, no extra and possibly conflicting data is stored in the array representation of the larger graph. Secondly, the program does not have to waste valuable time saving superfluous and repeated information. This approach forced us as programmers to be much more careful when calling the array by always calling it with the larger index first, but the investment in carefulness paid out in improved performance, a worthy sacrifice.
The program then moves into setting up the array for testing colorings. We initially set all connections to the last node (with index ptsInMap – 1) to “color” false. Afterwards, the program defines variables to keep track its status in terms of solving the problem. These variables tell, for instance, whether there are colorings of the larger graph left to test or whether the program has found a graph that allows it to quit a while loop early.
After all of this initial setup, the program starts the first, outermost while loop that cycles through all possible colorings of theMap. The program changes the colorings of theMap by changing the values of its cells to true or false, our two “colors”. As previously stated, “good” colorings are defined to be those that have no monochromatic subgraphs of either color in it. By finding even one good coloring scheme, the program can definitively declare that the real Ramsey number of the given values of r and b is greater than the guess. The real Ramsey number or guesses above the real value will by definition only result in graph colorings that have monochromatic subgraphs in it.
The color-switching occurs in a method called fillTheMap. The color-rotating algorithm works by generating all permutations for the different possible coloring schemes. This uses an object of the class ColoringGenerator, which as the name implies, will generate all colorings. We will discuss this class and the coloring generation process in detail later.
For each coloring, the program then calls the method testColoringForASize for each “color” true or false and its respective subgraph size. TestColoringForASize, while keeping a coloring constant, goes through the graph and searches for monochromatic subgraphs of a specific subgraph size and “color” (true or false) passed to it. If the method does not find a single monochromatic subgraph within theMap with its current coloring, testColoringForASize returns false. If it finds a monochromatic subgraph, however, it returns true. TestColoringForASize is called twice within the Boolean statement of an if statement. First, it is passed the smaller subgraph size, submapSize2, (this subgraph size was set to be the smaller subgraph when the program queried the user for its inputs) with a color of false. The program checks for smaller monochromatic subgraphs first because it will take less time to find smaller monochromatic subgraphs within a coloring than to find larger ones, allowing the program to potentially be able to draw a conclusion earlier. Secondly, the program calls testColoringForASize and passes submapSize1 and true as the color. Note that the if statement uses short-circuit evaluation to save time; if testColoringForASize returns false for the first set of parameters, the program does not even check the second set of parameters because there is no way that the expression in the if’s Boolean statement will come out to be true. This is achieved using the “&&” operator instead of the “&” operator for standard evaluation.
TestColoringForASize is a function within the Ramsey class, the same class as the program’s main. As stated, it tests a coloring for a subgraph of a specified size and color. Inside testColoringForASize are two while loops. The first (i.e. outermost) of the two loops cycles through all the possible combinations of nodes in the larger graph to create subgraphs of the specified size. In order to cycle though all possible subgraphs, the function uses the class CombinationGenerator, which returns all possible combinations of the nodes in theMap in sets sized to the number of nodes in the subgraph for which the program is searching. This class in described in further detail below.
The second (i.e. inner) loop rotates through the different edges in the specific subgraph. It rotates through the different edges by using CombinationGenerator as well; this time, it tries to finds all possible pairs of nodes in the submap.
If in the inner loop of the program ever finds an edge that is not of the passed color, then it immediately exits the inner loop and continues to cycle through the other subgraphs, trying to find one that is monochromatic. If the inner loop only finds edges of the color passed by the calling method and goes through all the edges in the subgraph, then the program can determine that the coloring indeed has monochromatic subgraphs. Therefore, testColoringForASize immediately returns false, telling the calling method, the main, that it needs to continue to cycle through colorings as this coloring is not void of monochromatic subgraphs. If, however, testColoringForASize goes through all the subgraphs and does not find a single one that is monochromatic, then the program has found a coloring without monochromatic versions of the specified subgraph in the specified color. In this case, testColoringForASize returns true.
When the main calls testColoringForASize for both colors/subgraph sizes and is returned true both times, the program will know that there are no monochromatic subgraphs inside the current coloring. As previously stated, when testColoringForASize returns true, it means that there are no monochromatic colorings of the passed color/subgraph size. When this function returns true for both sets of parameters, it makes sense that there should be no monochromatic colorings of any type in the graph with its present coloring.
If at any time in the program testColoringForASize returns true for both sets of parameters, then the program immediately reports its findings: having found a graph with no monochromatic subgraphs, it knows that the Ramsey number must be, by definition, greater than the guess. (Example of this output: Appendix B, Figures 3 and 7) If however the program goes through all the colorings and finds that they all have monochromatic subgraphs within them, then by definition the program knows that the Ramsey number is less than or equal to the guess. (Example of this output: Appendix B, Figure 6)
After determining its findings, the program finally outputs the information to the screen. If the Ramsey number is known to be greater than the guess, then the program will also output an Edge Sequence Key. This key contains the information about the coloring so that it can be graphed using the separate program that we have developed for the task. The graphics and calculation portions of the project were separated in order to allow the calculations to occur on a supercomputer, most of which do not support GUIs. The graphics part was added to visually verify and prove the findings of the calculation part of the project. The workings of the graphics program are described in greater detail below.
ColoringGenerator Class and the fillTheMap Function
(Code for ColoringGenerator class is in Appendix E and code for fillTheMap function is in Appendix D)
Together, the class ColoringGenerator and the method fillTheMap cycle theMap through its different possible colorings. The function fillTheMap uses an object of the ColoringGenerator class in order to generate all the possible permutations of colorings.
The class ColoringGenerator creates the permutations in a function called getNext. This function returns an integer array full of ones and zeros. This array is as long as the number of edges in the graph since we need to figure out the colorings of all of the edges. Therefore, each cell represents a certain edge. The algorithm in getNext will cycle through all possible permutations of the array with 1s and 0s in order to find all of the colorings of the graph.
The generation of these permutations is achieved by using an algorithm by Donald E. Knuth from his well regarded texts, The Art of Computer Programming. These books contain algorithms with the primary goal of reducing the processing time to solve the problem at hand. A reasonable question to ask would be why we did not generate the algorithms to create permutations on our own. The answer is that we could have; creating a simplistic algorithm is a relatively trivial problem. We could have, for instance, created a program that incremented a counter and every time the method getNext was called, the program converted the value of the counter into a binary string. This would not have been very efficient, however. Knuth’s algorithms are, to the contrary, very efficient and fulfill the tasks we need in the least amount of time. In fact, his algorithm only involves five assignment steps for every call to getNext. As researchers, it is important to make use of our resources and past findings by other more established computer scientists. For these reasons, we felt it was justified to consult and make use of the algorithms so we could spend time doing “new” research. In the end, while this is an important part of the program, these algorithms do not form the core ideas behind the code, all of which are original.
(We developed all the code for this class; generally as in this case, Knuth only provides algorithms, not code.)
Despite how fast it is for the program to generate colorings, it still takes a significant amount of time to analyze the colorings. Therefore, instead of calling getNext directly, fillTheMap instead calls the method nextColoring, which calls getNext, but also analyzes the coloring before returning it to the calling method. One of the large time-saving methods is that the program counts the number of each binary digit in the array returned by getNext. If there are not enough 0s or 1s to make a graph with no monochromatic subgraph colorings, then the program will skip the whole coloring, resulting in significant time savings.
Another even larger time saver occurs in the method that calls he function nextColoring. This method and the class ColoringGenerator act as if theMap is actually one node smaller than it really is. The idea is that the automatic permutation generator will only systematically go through all the edges containing all the nodes except one. For all the connections going to the last node, a for loop in fillTheMap smartly rotates the colorings of the edges with the last node so that some colorings that are just repeats of other colorings are skipped. One of the ways that it can become repeated is if the graph is only rotated. Because position does not matter, one can remove the other colorings that are just rotated. This theoretically should result in very significant time savings.
CombinationGenerator Class
(Class CombinationGenerator's code is in Appendix F)
The CombinationGenerator class is used to cycle through the different subgraphs in a coloring and to cycle through the different edges within a subgraph. In order to perform these operations, the class must generate combinations.
In order to generate these combinations, this class makes use of the algorithms of a renowned computer scientist as well. Like in the previous class, we could have made an algorithm to complete the task, however it would be very unlikely that we could make our algorithm as fast as a professional and renowned computer scientist could. For this class, we made use of Kenneth H. Rosen and his book Discrete Mathematics and Its Applications. Using Rosen’s algorithm, the program in the method getNext can get the next combination in as little as four or five assignment operations, much faster than the algorithm that we would have developed.
In order to use the class CombinationGenerator, the program had to first create a temporary “holding” array containing all the nodes for which we were creating a combination, whether it was to generate a subgraph or to select an edge between two nodes in a subgraph. GetNext outputs an array that tells the program the locations of the nodes in the temporary holding array. The two arrays are then correlated, the node indices extracted, and then the subgraph or edge used in the subsequent calculations.
Note: the class CombinationGenerator was adapted from code made available to programmers free on the internet. The class is quite bare as it essentially only contains Rosen’s algorithm and a few supporting methods and functions. More information about the exact attribution of this code is available in the source code. We created all the code that utilizes the class and that integrates it into our program. The problem of generating combinations is also trivial like generating permutations, but it is definitely unlikely that we would be able to create an algorithm more efficient than one from a renowned computer scientist. As with ColoringGenerator, this code is not part of the principle ideas behind our program. For these reasons, we felt it was justified to use the code.
Additional Comments on Performance Enhancements
As a primary goal, the program was supposed to find as many ways to reduce the time needed to calculate a Ramsey number. We implemented these ideas in trying to reduce the number of coloring tested, for instance, by pre-analyzing and eliminating colorings that we know we do not need to analyze for one reason or another. Throughout the project, we also realized that it makes sense to reduce the time spent in the innermost while loop of the function testColoringForASize (the while loop that gets the color of specific edges themselves) as this is the part of the code that will by far be run the most times and thus will be the largest contributor to total processing time. So when trying to reduce processing time, we made use of this observation so we could reduce time spent on the process that inherently take the most time.
The program also makes use of other simple, yet remarkably effective ideas to reduce processing time. For instance, at many point in the loops, if a “special” case has been found, the program does not need to continue to look through the different cases. For instance, once the program has found a coloring without any monochromatic colorings, it immediately stops goring through the various colorings and loops. Therefore, one of the simple yet very important time savers is the break command in Java (or the return command depending on the circumstances) that will allow the program to immediately terminate loops and move on rather than make calculation after an accurate generalization can already be made.
Other simple yet very helpful time savers include short-circuit evaluation for Boolean statements. This concept is related to the idea behind the break: stop doing a calculation whenever you have enough information to generalize. Specifically, short-circuit evaluation allows the program to know that a statement has to be either true or false after it has only evaluated part of the Boolean expression. Instead of continuing to evaluate, the program can instead stop, draw its conclusion, and move on. One specific example of our use of short-circuit evaluation is when the program searched for subgraphs within a coloring. If we found a monochromatic coloring of the first color, then we would not even look at the second color, as it would bear no influence on the conclusion about that coloring: it contained monochromatic subgraphs. We only looked at the second coloring if it was possible that it could influence the outcome of the Boolean statement. For example, if we did not find a monochromatic subgraph of the first color, we would not check for the second color since it does not matter.
The Graphing Program
(The code for the graphing program's class, GraphPlotter, is in Appendix H)
The second program in our project is the graphing program, which can be used to visually prove that a graph of a guessed number of nodes can indeed contain no monochromatic subgraphs if the calculation program has found this to be true. This program takes the Edge Sequence Key and visually displays the coloring.
After obtaining the key from the user (Example of prompt: Appendix B, Figure 4), the program decomposes the string into the different variables contained within it: the guess (the number of nodes in the larger graph), the sizes of the subgraphs, and then finally the binary string representing the edge coloring.
The program first divides the circumference of a circle into as many arcs as there were points in theMap in the calculation program. The program then gets the polar coordinates of the endpoints of these arcs and converts them to Cartesian coordinates. It plots small circles at each of these points to represent the nodes.
Then, through a series of for loops, the program does exactly what the calculation program does to convert the binary array from the class ColoringGenerator into a real coloring, but instead of an integer array, the program is dealing with a String, essentially an array of characters. For every zero, the program draws a red line between the nodes, and for every one, the program draws a blue line. After this process, the program prints essential information to the screen (like what the guess and subgraph sizes were) alongside the graph. (Example of the window after graphed and text drawn: Appendix B, Figures 5 and 8)