[BUG] Graph coloring unstable for directed graphs

[joweich]

Issue

While investigating the failing tests of #118, I noticed a more fundamental issue that breaks both this PRs tests as well as the greedy graph coloring introduced in #94: For directed graphs, the tests only succeed if the vertices are added in a certain order, i.e. the reversed order they are subsequently iterated over.

Steps to reproduce

In the BasicGraphColoring test in greedy_graph_coloring_test.cpp, reverse the order in which the nodes are added:

  const auto vertex_3{graph.add_vertex(30)};
  const auto vertex_2{graph.add_vertex(20)};
  const auto vertex_1{graph.add_vertex(10)};

This will fail the test.

Root Cause

Both the greedy graph coloring and the Welsh-Powell iterate over the neighbors and increment the color if the neighbor is already colored in the same color:

  // Iterate through each vertex
  for (const auto& [current_vertex_id, _] : vertices) {
    // Iterate through neighboring vertices
    // Find the smallest available color for the current vertex
    int available_color{0};
    for (const auto neighbor_id : graph.get_neighbors(current_vertex_id)) {
      if (coloring.contains(neighbor_id)) {
        const auto neighbor_color{coloring.at(neighbor_id)};
        if (neighbor_color >= available_color) {
          available_color = neighbor_color + 1;
        }
      }
    }

However, for directed graphs, get_neighbors will only return the succeeding vertices. For the following directed graph, the coloring will be successful if the nodes are visited in the order C-B-A, and fails otherwise. The order of the iteration depends on the order the vertices are added to the graph, thus the algorithm is unstable.

flowchart LR
    A --> B
    B --> C

Fix Ideas

get_neighbors accesses adjacency_list_ that does not have predecessor vertices for directed graphs. We could think of extending it by this and provide something like get_predecessors for directed graphs. Well-knowing this will have impact on memory consumption of directed graphs, there might be more elegant solutions. Curious what you guys think @bobluppes @ndcroos :thinking:

[github-actions[bot]]

Hi there! Thank you for creating your first issue on the Graaf library, we will look into it shortly. In the mean time, please make sure the issue has the correct labels set.

[github-actions[bot]]

Stale issue message