Метод минимальной степени. Оптимизировать реализацию

Работаю с разреженными матрицами. Возникала необходимость перестановки строк и столбцов с целью сократить "заполненность" матрицы после разложения Холецкого. Итак сам алгоритм:
1) Для матрицы построить граф, вершины которого - номера строк, если в i-той строке есть не нулевой элемент, то это отображается ребром в графе между i-й вершиной и вершиной, значением которой является номер ненулевого элемента в i-й строке. (Матрица симметричная, диагональные элементы все не нулевые, дуги для диагональных элементов не строятся.) Получается граф "смежности", если так его можно назвать.
2)В графе находим вершину с минимальной степенью, ее значение записывается в вектор перестановки. (Минимальная степень - вершина соединена с минимальным количеством других вершин. Если таких вершин несколько, берется первая.) Сама вершина удаляется вместе с ребрами.
3) Алгоритм повторяется пока в графе остаются вершины.
Граф храню через списки смежности: std::vector< std::set > G;
Реализация:
std::vector tmp; tmp.resize(n); for (auto &t : tmp) t = 1; unsigned index; int min; // ПОЛУЧЕНИЕ ПЕРЕСТАНОВКИ for (unsigned i = 0; i < n; i++) { // поиск мин min = n + 1; for (unsigned k = 0; k < n; k++) { if (tmp[k]) { if (G[k].size() < min) { min = G[k].size(); index = k; } } } for (auto &Node : G[index]) if (tmp[Node]) G[Node].erase(index); p[i] = index; tmp[index] = 0; }
Не нравится тот момент, что приходится использовать дополнительный массив, который показывает была ли удалена i-я вершина или нет. Из-за этого поиск минимума идет по всем вершинам, но учитываются только не удаленные. Можно ли поправить этот момент?

Ответ

А вы сделайте наоборот, в temp храните не признаки наличия вершины а, индексы существующих вершин. Кроме того следует хранить не сами индексы, а диапазоны индексов, то есть:
typedef std::pair Range ; typedef std::vector Ranges;
std::vector ranges; ranges.reserve(n \ 2); // в худшем случае будет n\2 диапазонов // если узлы станут удалятся через один ranges.push_back(Range(0, n));
Ranges::iterator min_range; size_t min_index; size_t min;
// ПОЛУЧЕНИЕ ПЕРЕСТАНОВКИ for (size_t i = 0; i < n; ++i) { // поиск мин min = n + 1; for(auto r = ranges.begin(); r != ranges.end(); ++r) { for(auto k = r->first; k < r->second; ++k) { if (G[k].size() < min) { min = G[k].size(); min_index = k; min_range = r; } } }
for(auto & node : G[min_index]) { // здесь не проверяется удалена ли вершина node // так как это избыточно, node всегда "живая" // если G построен корректно G[node].erase(min_index); } p[i] = min_index;
// удаляем найденный индекс if(min_index == min_range->first) { if(min_range->first + 1 == min_range->second) { ranges.erase(min_range); } else { min_range->first++; } } else if(min_index + 1 == min_range->second) { min_range->second--; } else // min_index где-то в середине диапазона { auto left = ranges.insert ( min_range , Range(min_range->first, min_index) ); (left + 1)->first = min_index + 1; // после insert справа остался // старый диапазон, укоротим его } }