Introduce Welsh Powell Algorithm

[ZigRazor]

Please introduce Welsh Powell Coloring Algorithm

[badumbatish]

Hi there, I'm working on this problem on my branch https://github.com/badumbatish/CXXGraph/tree/welsh_powell_coloring and hit an obstacle.

The algorithm returns an unordered_map of shared_ptrs of nodes where the value is the color order of each node.

template <typename T>
std::unordered_map<std::shared_ptr<const Node<T>>, int>Graph<T>::welshPowellColoring() const {
  auto adjMatrix = *getAdjMatrix();
  std::unordered_map<std::shared_ptr<const Node<T>>, int> degreeOfVertexMap = {};

  // Find degree of each vertex and put them in a map
  for (auto &[nodeFrom, nodeToEdgeVec] : adjMatrix) {
    degreeOfVertexMap[nodeFrom] = nodeToEdgeVec.size();
  }

  // Transform the map to the vector to sort
  std::vector<std::pair<std::shared_ptr<const Node<T>>, int>> degreeOfVertexVector(degreeOfVertexMap.begin(), degreeOfVertexMap.end());

  // Sort them based on the vertex degree
  std::sort(degreeOfVertexVector.begin(), degreeOfVertexVector.end(), [](const auto& left, const auto& right) {
    return left.second > right.second;
  });

  // Create a new map of coloring, where the keys are the "color", and the value is a vector of node that belongs to that color.
  std::unordered_map<std::shared_ptr<const Node<T>>, int> mapOfColoring = {};

  for (auto &[nodeFrom, _] : adjMatrix) {
    mapOfColoring[nodeFrom] = 0;
  }
  // Going down the list of vertex based on degrees
  for (int i = 0; i < degreeOfVertexVector.size(); i++) {

    // Current vertex being considered for coloring
    auto node = degreeOfVertexVector[i].first;


    // Find the smallest unused color for the current vertex
    std::vector<int> usedColors(degreeOfVertexVector.size() + 1, 0);

    for (const auto &[neighbor, _] : adjMatrix[node]) {
      usedColors[mapOfColoring[neighbor]] = 1;
    }
    // Assign the smallest unused color to the current vertex

    for (int c = 1; c < usedColors.size(); c++) {
      if (usedColors[c] == 0) {
        mapOfColoring[node] = c;
        break;
      }
    }
  }

  return mapOfColoring;
}

When coloring, for each vertex, I'm trying to access its neighbor's color value in mapOfColoring with mapOfColoring[neighbor] to calculate the minimum color order needed for each vertex but the problem is that mapOfColoring is populated with source vertices, where neighbors are destination vertices. So none of the neighbor is actually in mapOfColoring.

I'm wondering if there is a way to approach this problem?

[badumbatish]

Hi there, I went back to the repository and took some inspiration from the breadth_first_search algorithm where it returns a vector of raw nodes.

I finally implemented the correct changes and created a pull request #391 , can you help me take a look @ZigRazor ?

[badumbatish]

Hi there, please don't close this issue yet, I noticed that there is some improvement to be made for my code to be more elegant.

[ZigRazor]

Ok, @badumbatish