shah314 / graphcoloring Goto Github PK

This is part of openjournals/joss-reviews#1843.

First of all, as an reviewer, there are two parts, one is the implementation of the code and the other is the writing paper part. I am not sure which part should I focus on or both? And this post is only about the paper part.

• First of all, For the result of benchmark instances, the table contains columns of graph name, number of vertices, Optimum result, best result, and the worst result. Those information is very useful, showing the basic property of the graph and the capacity of the algorithm. However, could the author add one more column about the number of edges? Since both numbers of vertices and the number of edges together give a general idea of how large and dense the graph is. And also that graph size and graph density play an important role in the chromatic number. For example, a very dense graph, we know that the chromatic number would be close to the number of vertices while for a very sparse graph, the chromatic number would be very small. Plus, the number of edges is very easy to get :)

• Second of all, I was confused by the term Found-Best and Found-Worst. Could the author put a few words to make it a little bit clear? For example, The best/worst results are picked from how many repeated test results; What's the mean reason for the algorithm generating a non-deterministic result for a different run. Is it by the different random seed, or a different number of iterations, or even by the operating system's scheduling?

• Then, what's the mean reason for the Table3 of the ColPack comparison part. The table only contains a subset of 9 graphs. Or why does the author picked these 9 graphs? Is there any particular reason? or just random? Could the author help me out?

• In the end, since the tests result have a very well structured result. I recommend the author also provide the "Geometric Mean" at the last row of each table of results.
  Because 1 Geometric means provide better overall performance evaluation. 2 It is easy to calculate and there is no need to do any extra experiment.

This is part of openjournals/joss-reviews#1843. Please address the following points:

• The results should also be moved away from the git page and into the paper itself

Comparisons

• This section should be re-written and the results must be included in the paper itself.
• A graph would be better over time
• Resource usage should be clarified

The code and github resources are good, but the write up needs to be more coherent and self-contained.

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.