Finding the chromatic index of a graph. Exact algorithm by enumeration of possible colorings of edges. How to optimize?

Question

Programming

It is necessary to implement an exact algorithm for finding the chromatic index of a graph (the minimum number of colors that can be used to color the edges of the graph so that no adjacent edges are painted in the same color).
Let ρ be the maximum degree of a vertex in the graph. Then the graph can be colored sometimes with ρ or always with ρ + 1 colors. The imprecise algorithm always copes with coloring in ρ + 1 colors and not always in ρ colors, it is implemented. Now it is necessary to implement an exact algorithm for finding a coloring in ρ colors, if such is possible. As I was told heresuch an algorithm is implemented only by exhaustive search. I did, for the graph that is in the same question, it runs for about a minute.
The code:

QList< QList<Edge> > colorEdges; //Окрашенные рёбра, colorEdges[i] - цвет, colorEdges[i][j] - ребро
QList<Edge> bufferVertex; //Список рёбер
/**/
maxDegree = 4; //Потом максимальной степени вершины
bool f;
int *colors = new int[bufferVertex.size()]; //Массив для хранения возможных комбинаций цветов
for (int i = 0; i < bufferVertex.size(); i++)
    colors[i] = 0;
do
{
    f = false;
    for (int i = 0; i < bufferVertex.size(); i++) //Перебор возможный комбинаций цветов
        if ((colors[i] + 1) != maxDegree)
        {
            colors[i]++;
            for (int j = i - 1; j > -1; j--)
                colors[j] = 0;
            break;
        }

    colorEdges.clear();
    for (int i = 0; i < maxDegree; i++) //Окраска в текущую комбинация цветов
        colorEdges.append(QList<Edge>());
    for (int i = 0; i < bufferVertex.size(); i++)
        colorEdges[colors[i]].append(bufferVertex.at(i));
        for (int j = 0; j < colorEdges[i].size(); j++)
            for (int k = j + 1; k < colorEdges[i].size(); k++)
                if ((colorEdges[i][j].getStart() == colorEdges[i][k].getStart()) ||
                   (colorEdges[i][j].getStart() == colorEdges[i][k].getEnd()) ||
                   (colorEdges[i][j].getEnd() == colorEdges[i][k].getStart()) ||
                   (colorEdges[i][j].getEnd() == colorEdges[i][k].getEnd()))
                    f = true;

    if (f) //Если окрасился неправильно, проверяем не закончился ли счётчик
    {
        f = false;
        for (int i = 0; i < bufferVertex.size(); i++)
            if (colors[i] != (maxDegree - 1))
            {
                f = true;
                break;
            }
    }
} while (f);

How can it be at least more or less optimized?

Answer 1

Of course, access to the list element depends linearly on the size of the container. And I inserted additional checks for f==true into the bodies of the cycles.
Well, a few comments on the code

//Список рёбер
// QList<Edge> bufferVertex; 
std::vector<Edge> bufferVertex;

//Потом максимальной степени вершины
maxDegree = 4; 
//нужно 2 булевы переменные
bool f;

//Окрашенные рёбра, colorEdges[i] - цвет, colorEdges[i][j] - ребро
// QList< QList<Edge> > colorEdges;
std::vector<std::vector<Edge>> colorEdges(maxDegree);
for (int i = 0; i < colorEdges.size(); i++){
  colorEdges[i].reserve(bufferVertex.size());
}

//Потом максимальной степени вершины
// int *colors = new int[bufferVertex.size()];
// for (int i = 0; i < bufferVertex.size(); i++)
//     colors[i] = 0;

std::vector<int> colors(bufferVertex.size(), 0);

do
{
  f = false;
  //Перебор возможный комбинаций цветов
  for (int i = 0; i < colors.size(); i++) 
    if (colors[i] != maxDegree-1)
    {
      colors[i]++;
      for (int j = i - 1; j > -1; j--)
        colors[j] = 0;
      break;
    }

  //Окраска в текущую комбинация цветов
  // colorEdges.clear();

  //удалять объекты внутри не надо, а просто их чистим 
  for (int i = 0; i < colorEdges; i++){
    colorEdges[i].clear();
  } 
  
  for (int i = 0; i < bufferVertex.size(); i++){

    colorEdges[colors[i]].push_back(bufferVertex[i]);
    
    //нужен ли этот 2ой цикл снизу, может достаточно проверять только последнее вставленное значени?
    //for (int j = 0; j < colorEdges[i].size()-1 && !f; j++){
    // 		auto start_j = colorEdges[i][j].getStart();
    // 		auto end_j = colorEdges[i][j].getEnd();
    // 		auto start_k = colorEdges[i].back().getStart();
    // 		auto end_k = colorEdges[i].back().getEnd();
    // 		f = start_j==start_k || start_j == end_k || end_j == start_k || end_j==end_k;
    // }		
      for (int j = 0; j < colorEdges[i].size() && !f; j++)
        for (int k = j + 1; k < colorEdges[i].size() && !f; k++)
        {
          // if ((colorEdges[i][j].getStart() == colorEdges[i][k].getStart()) ||
          //    (colorEdges[i][j].getStart() == colorEdges[i][k].getEnd()) ||
          //    (colorEdges[i][j].getEnd() == colorEdges[i][k].getStart()) ||
          //    (colorEdges[i][j].getEnd() == colorEdges[i][k].getEnd()))
          // 	f = true;
          auto start_j = colorEdges[i][j].getStart();
          auto end_j = colorEdges[i][j].getEnd();
          auto start_k = colorEdges[i][k].getStart();
          auto end_k = colorEdges[i][k].getEnd();
          f = start_j==start_k || start_j == end_k || end_j == start_k || end_j==end_k;
        }
  }

  if (f) //Если окрасился неправильно, проверяем не закончился ли счётчик
  {
    f = false;
    for (int i = 0; i < bufferVertex.size() && !f; i++)
      f =  colors[i] != (maxDegree - 1);
  }
} while (f);