search

KeRNeLith / QuikGraph

Generic Graph Data Structures and Algorithms for .NET
https://kernelith.github.io/QuikGraph/
Microsoft Public License
453 stars 65 forks source link

Rename VertexColoringAlgorithm to GreedyVertexColoringAlgorithm #66

Closed Kemsekov closed 1 year ago

Kemsekov commented 1 year ago

VertexColoringAlgorithm in it's implementation uses greedy approach to color verticies so it cannot theoretically color graph with minimum count of colors in 100% of times, so I renamed it and changed it's documentation to make it clear.

KeRNeLith commented 1 year ago

Hello,

Do you have any example showcasing the fact that algorithm may not produce the minimum count of colors?

Kemsekov commented 1 year ago

Okey. This implementation uses Greedy approach to color nodes, but there is RLF, DSatur which gives better results with less colors used. Also there is tabu search and AB-RLF - which is best algorithm I know so far. There is just a lot of them so it makes sense to specify which one is used.

Kemsekov commented 1 year ago

Oh, my bad. I had to pull into develop