Hybrid Algorithm is Broken #1
Labels
Comments
|
After writing a test that provides the hybrid algorithm with a K5 kuratowski subgraph (which can only be colored with 5 colors) the hybrid algorithm returned a coloring of 4 (which is impossible). This seems to occur because it leaves one of the nodes with a value of -1 (which is invalid). |
Merged
brrcrites
added a commit
that referenced
this issue
Oct 6, 2018
* Expands the build tests to include Mac and Linux builds * Integrates basic unit tests into Travis for validation of PRs * Temporarily removes Hybrid unit tests until #1 is closed
brrcrites
added a commit
that referenced
this issue
Oct 6, 2018
* Expands the build tests to include Mac and Linux builds * Integrates basic unit tests into Travis for validation of PRs * Temporarily removes Hybrid unit tests until #1 is closed
brrcrites
added a commit
that referenced
this issue
Oct 6, 2018
* Expands the build tests to include Mac and Linux builds * Integrates basic unit tests into Travis for validation of PRs * Temporarily removes Hybrid unit tests until #1 is closed
brrcrites
added a commit
that referenced
this issue
Oct 15, 2018
* Adds a post-processing step to Tabucol which both minimizes the colors used during the random coloring process and makes them contiguous. Closes #28 * Adds a check to Tabucol to guarantee that we choose a reasonable starting condition (the size of the grpah in this case, which will always be reasonable), it does not set a minimum size. * Updates the is_valid() base function with more robust checking * Updates all algorithms such that when they move to an invalid state they update the interal coloring map to be an empty map. This should likely be updated to be an uncolored version of the input map or to have the algorithms return a valid/invalid rather than the result. * Retab various files * Contains enough test cases to give a weak validation to the hybrid algorithms, and closes #1. It should be noted that these hybrid algorithms were actually incorrectly coded in the first place and will need to be majorly refactored through a refactor of Tabucol which allows for partial colorings to be used.
brrcrites
added a commit
that referenced
this issue
Oct 15, 2018
* Adds a post-processing step to Tabucol which both minimizes the colors used during the random coloring process and makes them contiguous. Closes #28 * Adds a check to Tabucol to guarantee that we choose a reasonable starting condition (the size of the grpah in this case, which will always be reasonable), it does not set a minimum size. * Updates the is_valid() base function with more robust checking * Updates all algorithms such that when they move to an invalid state they update the interal coloring map to be an empty map. This should likely be updated to be an uncolored version of the input map or to have the algorithms return a valid/invalid rather than the result. * Retab various files * Contains enough test cases to give a weak validation to the hybrid algorithms, and closes #1. It should be noted that these hybrid algorithms were actually incorrectly coded in the first place and will need to be majorly refactored through a refactor of Tabucol which allows for partial colorings to be used.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
When testing the algorithms, Hybrid had a single instance of a better coloring than previously known. This is likely an error, so the Hybrid algorithm needs to be hand verified with the paper.
The text was updated successfully, but these errors were encountered: