Graph-Vertex Coloring benchmarking

This site aims to support in the continued research into Graph-Vertex Coloring Algorithms

View the Project on GitHub DenatYeti/GVC-validator

To see an example output from an execution of an Instance Space Analysis you can follow this link: Example To see the best known results: best

Initial information regarding the algorithms used

All Algorithms have currently been run for a maximum of 10 minutes. Therefore for a fair comparison with new algorithms they are expected to have had a similar limit on their allowed running time. For the homer.col instance there is a current issue and as such this instance should be skipped.

Posting your own algorithms

To allow for analysis using user algorithms, the page allows for users to add algorithms to the test suite that can be used. This process is done by,

  1. Running your algorithm using the instances present in the Resources folder for the repository.
  2. Gathering the resulting .sol files in a directory called the name that the algorithm should be recognized as, ensuring no overlap with pre existing algorithms in the repository.

This triggers a simple coloring-verifier that ensure that only valid solutions are present on the repository, in the case that an algorithm shows a better performance than previously denoted in the best_solutions.md file, said file is updated to reflect this.

Running your own Instance Space Analysis

To perform an Instance Space Analysis (ISA),

  1. Modify the config.yaml file found in the main repository, adjusting the list of algorithms to match the algorithms that one wants to use (The names should match the directory names that contain solution files generated by said algorithm). Ensure that the dir parameter does not overlap with an already existing docs subdirectory, and that the parameters are as desired in regards to the ISA.

  2. Push these changes onto the GitHub repository.

  3. Go to the page corresponding to the performed ISA /dir/page.html replacing dir with the user defined name in the config.yaml

  4. Inspect and analyze the plots using the two for easier comparisons.

Adding additional Instances to better fill out the instance space.

To add more instance to the analysis,

  1. Push additional instance into the instance folder found in the Resources subdirectory.
  2. Run the solvers for the new instances.
  3. Follow the Posting your own algorithms guide to add the new .sol files.
  4. Rerun the ISA, by modifying the dir to a new name this allows for differences between the two spaces to also be viewed and analyzed.