This is a quick study of which graph coloring heuristic of NetworkX performs best. It is meant as an example for AlgBench and the general structure of a good study.
Graph coloring is an NP-hard problem that appears as subproblem in many contexts. You can find more information on it on Wikipedia.
The documentation of NetworkX greedy heuristics for it can be found here.
- _utils provides utils used during the study. In this case just a database for the graph instances.
- 00_generate_instances.py generates us a set of instances. In this case, I already ran the script. It generated the next file.
01_instances.zipcontains the graph instances generated by the previous script.- 02_run_benchmark.py runs a set of different
algorithms on these instances.
- 02_run_benchmark_with_slurminade.py just showing how to do the same distributed with slurminade.
03_benchmark_datathe data generated by the previous script.- 04_check_results.ipynb a simple notebook to check that the data looks fine.
- 05_process_results.py converting the data into a simple pandas table which is easier and faster to work with. In some cases, the raw data can also be too much for a Git, so you can only share the reduced file.
06_simplified_results.json.zipthe simplified pandas table generated by the previous script.- 07_analyze_mean.ipynb a quick analyzis of the results. For real studies, you would have multiple such files following as there are often multiple aspects of the benchmark to evaluate.
- 08_analyze_runtime.ipynb thus, we analyze the runtime in more detail here
- 09_analyze_quality.ipynb and the solution quality here