[JOSS-Review] Code Implementation

[ProbShin]

This is part of openjournals/joss-reviews#1843. This post is about code implementation.

The author implements a coloring algorithm based on iteratively recoloring schema. For each iteration, the algorithm first finds a clique and colors the clique. This part can be understood as coloring the subgraph local optimally. And then for the rest of the graph, sort the vertices (dynamically) according to the degree and coloring the vertices using different heuristics. This part can be understood as recolor the remaining part of the graph to have less number of colors.

The author implements the algorithm using Java. It is a good contribution to the combinatorics community and the overall implementation is very good. However, there are a few concerns the reviewer wants to point out as below.

---

1. Debug information during the runtime.

I recommend the author to close debug information during the runtime, or at least set a flag enabling to close debug information. For example, for file Backtracking.java line 219. Move the print line out of the function or set a flag to let users select whether to display the debug information or not.

The separation between the debug-part and the coloring-part makes the code structure clear, readable and easy to maintenance in the future.

---

2 The hard-coded value of the variable KNOWN_K.

The author uses a KNOWN_K variable, defined in Constants.java, to indicate an initial guess on the number of colors k in the file Backtracking.java. However, it seems that the variable KNOWN_K is hard-coded.

Since an upbound of the chromatic number could be a better guess than the hard-coded value. The reviewer recommends using a very simple yet useful upbound largest degree + 1. And this value could be easily calculated during the reading of the graph almost without any extra time and space expense. For example, the author could update this KNOWN_K value somewhere in the file GraphReader.java

---

3 Memory usage

When reading the graph, the author allocates the memory as if the graph is a complete graph (dense matrix), not a sparse graph (sparse matrix). So each public class Graph object would

• use a 2-dimension integer array of size n x n. (n is the number of nodes of the graph.) . This makes the space complexity to be O(n^2).
• use a 1-dimension Node array of size n to store the n nodes of the graph. However, for each public class Node itself, there will be a LinkedHasSet of integers which is of size degree and an ArrayList of integers which is of the size of an upper bound of the chromatic number. This makes the space complexity to be O(n*(degree+MaxDegree+1)) = O(n*MaxDegree);

Even though treating the spare graph as a complete graph benefits the runtime performance because of the cache hitting and simple data structure, it might also limit the program to run only on small graphs of which has sizes in the unit of KB(KiloByte) unless the machine has a tremendous memory.

However, since the above implement does not affect the correctness of the code, the reviewer option on this implementation depends on the goal of this project. if this project is mainly for showing the correctness of the algorithm, the space complexity would be a trivial issue, and the reviewer would accept this implementation. However, if this project's goal is to create an efficient java software package for public use. Then the reviewer would suggest the author modify class Graph and class Node to either support a sparse way to manipulate the graph (such as CSR/CSC formatting ) or provide a brief declaration within the writing introduction about this space limitation.

---

In a nutshell, the reviewer put out 3 points,

• The 1st entry is required to modify.
• The 2nd entry is recommended but not required to modify.
• The 3rd entry is dependent. The relative modification should be taken based on the real situation.

[shah314]

@ProbShin @jedbrown

• I have added a verbose option to both Backtracking.java and GraphColoring.java (heuristic). But I think some basic information, like what coloring was found should be still outputted.

• The KNOWN_K is actually a lower bound. If known, the backtracking algorithm will spend time on coloring the graph with this chromatic number. It is initialized to the clique size which is a lower bound on the chromatic number of the graph. The algorithm iteratively increments this number and tries to color the graph with this incremented number of colors.

• I have removed the adjacency matrix from the graph. This was only used by the clique algorithm and was not absolutely essential to computing the clique.

Let me know your thoughts. Thank you!

[ProbShin]

Great.

• Yes, you are right. the number of colors and the color of the vertex are both the output of the algorithm. Since the vertex colors have been stored in the class Graph :: class Node, the number of colors could be output in an integer variable. Print the relative information to the screen can be considered as a debug operation by the users or the developers since this function is independent of the algorithms.

• I see. KNOWN_K is the lower bound. Thanks leading me out. And the clique size is a lower bound of the chromatic number. But unfortunately, there is not an efficient way to get this number out in constant or linear time for general graphs.

• Good, that's also my observation, it seems that the adjacency matrix is not used within the function of colorings.

In all, I am fine with all the modifications. Thanks.