Skip to content
  • Guido Trotter's avatar
    Fix Dsatur and add Dcolor · 8b50de5c
    Guido Trotter authored
    
    
    Our Dsatur implementation was incorrect: while the paper defined the
    degree of saturation of a vertex as the number of different colors it is
    adjacent to, we were using the number of colors, without considering
    uniqueness. This effectively implemented a different algorithm, which is
    very similar to the previous one, and while it performs slightly worse
    on average it still beats Dsatur on some cases.
    
    So we refactor the implementation to effectively support both algorithms
    without code duplication, and then we export both the old algorithms as
    "Dcolor" and the new one as "Dsatur". Since these are all fast
    algorithms in hroller we will still be able to pick the best result.
    
    Note that the new Dsatur implementation uses an IntSet to calculate the
    uniqueness. Results with nub + length on a list were significantly
    slower.
    
    Signed-off-by: default avatarGuido Trotter <ultrotter@google.com>
    Reviewed-by: default avatarIustin Pop <iustin@google.com>
    8b50de5c