[ALGO] Graph Coloring (Greedy)

[bobluppes]

Greedy Graph Coloring

The Greedy Graph Coloring algorithm is a heuristic approach to assigning colors to the vertices of a graph in such a way that no adjacent vertices share the same color. It is a fundamental algorithm with applications in scheduling, map coloring, and various optimization problems. The goal is to implement this algorithm to add to the library's suite of graph algorithms.

See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Greedy Graph Coloring Algorithm
 *
 * This function performs greedy graph coloring on a given graph. It assigns
 * colors to vertices in such a way that no two adjacent vertices share the
 * same color. The algorithm is heuristic and does not guarantee an optimal
 * coloring.
 *
 * @tparam GRAPH The type of the graph
 * @param graph The graph object
 * @return An unordered_map where keys are vertex identifiers and values are their respective colors.
 */
template <typename GRAPH>
std::unordered_map<vertex_id_t, int> greedy_graph_coloring(const GRAPH& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/coloring/greedy_graph_coloring.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/greedy_graph_coloring_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category. The category should follow the file path of the new algorithm.
  • In case the category does not exist yet, please add one
  • 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

[ndcroos]

Hi, I'd like to do this. Can you assign it to me?

[bobluppes]

Hi, I'd like to do this. Can you assign it to me?

Hi, of course, would be happy to :)