Поиск хроматического индекса графа. Точный алгоритм методом перебора возможных окрасок рёбер. Как оптимизировать?

Question

[VerNika]

Необходимо реализовать точный алгоритм поиска хроматического индекса графа (минимального числа красок, которыми можно окрасить рёбра графа, чтобы никакие смежные ребра не были окрашены в один и тот же цвет).

Пусть ρ - максимальная степень вершины в графе. Тогда граф можно окрасить иногда ρ или всегда ρ + 1 цветами. Неточный алгоритм всегда справляется с раскраской в ρ + 1 цветов и не всегда в ρ цветов, он реализован. Теперь необходимо реализовать точный алгоритм для поиска раскраски в ρ цветов, если такая возможна. Как мне подсказали здесь такой алгоритм реализуется только полным перебором. Сделала, для графа, который в том же вопросе, он выполняется около минуты.

Код:

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);

Как можно его хоть более-менее оптимизировать?

Comments

[VerNika]

Самая затратная часть - это проверка на правильность раскраски, без неё алгоритм выполняется практически мгновенно. Возможно мне надо заменить списки на массивы, не знаю, быстрее ли будет с ними работать.

[VerNika]

Оптимизировала пока так:

void MainWindow::BFS_lsAcc()
{
    bool f;
    int maxDegree = 0;
    QList<Edge> bufferVertex;
    for (int i = 0; i < edges.size(); i++)
        bufferVertex.append(edges.at(i));
    int *colors = new int[bufferVertex.size()];         //Массив для хранения возможных комбинаций цветов
    for (int i = 0; i < bufferVertex.size(); i++)
        colors[i] = 0;
    int *bufferArray = new int[n];
    for (int i = 0; i < n; i++)
        bufferArray[i] = 0;
    for (int i = 0; i < bufferVertex.size(); i++)
    {
        bufferArray[bufferVertex[i].getStart() - 1]++;
        bufferArray[bufferVertex[i].getEnd() - 1]++;
    }
    for (int i = 0; i < n; i++)
        if (bufferArray[i] > maxDegree)
            maxDegree = bufferArray[i];
    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++)
        {
            for (int j = 0; j < colorEdges[colors[i]].size(); j++)
                if ((colorEdges[colors[i]][j].getStart() == bufferVertex[i].getStart()) || (colorEdges[colors[i]][j].getStart() == bufferVertex[i].getEnd()) || (colorEdges[colors[i]][j].getEnd() == bufferVertex[i].getStart()) || (colorEdges[colors[i]][j].getEnd() == bufferVertex[i].getEnd()))
                {
                    f = true;
                    goto abc;
                }
            colorEdges[colors[i]].append(bufferVertex.at(i));
        }
        abc:
        /*for (int i = 0; i < colorEdges.size(); 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);
    ui->minVC->setText("-не используется-");
    ui->chrInd->setText(QString::number(colorEdges.size()));
    delete []colors;
    delete []bufferArray;
}

Время, в среднем, уменьшилось в 4,5 раза. Сейчас последую ответу AtomKrieg

[vampire444]

VerNika: учусь на этом же направлении, возникли вопросы как у тебя здесь и ещё вот тут: Внутренняя сортировка. Как лучше реализовать сортировку по нескольким полям?
Можешь дать какой-нибудь свой контакт, как с тобой связаться?

Answer 1

[AtomKrieg]

Конечно, доступ к элементу list линейно зависит от размера контейнера. И дополнительные проверки на f==true в тела циклов вставил.
Ну и по коду комментарии немного

//Список рёбер
// 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);