[ALGO] Welsh-Powell Algorithm

[bobluppes]

Welsh-Powell Algorithm

The Welsh-Powell algorithm is a greedy graph coloring algorithm. It works by sorting the vertices by their degrees in descending order and then assigning colors in a manner that no two adjacent vertices share the same color. This algorithm is particularly efficient for coloring sparse graphs and is generally simpler to implement than other coloring algorithms.

Since it is a variant of the greedy coloring algorithm (which is already implemented under algorithm/coloring/greedy_graph_coloring.h), it would be nice if we could reuse that implementation.

More details on this variant of greedy coloring can be found in the wikipedia entry.

Syntax

The algorithm should have the following syntax:

/**
  * @brief Applies the Welsh-Powell greedy graph coloring algorithm to the given graph.
  * 
 * The function sorts the vertices by their degree in descending order, then attempts
 * to color the graph in a way that no two adjacent vertices share the same color.
 *
 * @tparam GRAPH The graph type.
 * @param graph The input graph to color.
 * @return std::unordered_map<vertex_id_t, int> An map from vertex ID to color if the graph could be colored, or an empty map otherwise.
 */
template <typename GRAPH>
std::unordered_map<vertex_id_t, int> welsh_powell_coloring(const GRAPH& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/coloring/welsh_powell.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/coloring/welsh_powell_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[toadkarter]

Hi there, I would be happy to take this on. Would it be possible to have this issue assigned to me?

[GouraV-Chatterjee]

I generated a PR on this issue..Since I am a beginner please do look into my PR and share your valuable feedback...Thank you!!

[bobluppes]

Hi there, I would be happy to take this on. Would it be possible to have this issue assigned to me?

Hi, seeing as you are already assigned on #115 I will go ahead and assign this to @GouraV-Chatterjee

Welcome both to Graaf!

[GouraV-Chatterjee]

@bobluppes I have generated a PR regarding this issue....Please have a look!!!!Thanks:)