Работаю с разреженными матрицами. Возникала необходимость перестановки строк и столбцов с целью сократить "заполненность" матрицы после разложения Холецкого. Итак сам алгоритм:
1) Для матрицы построить граф, вершины которого - номера строк, если в i
-той строке есть не нулевой элемент, то это отображается ребром в графе между i
-й вершиной и вершиной, значением которой является номер ненулевого элемента в i
-й строке. (Матрица симметричная, диагональные элементы все не нулевые, дуги для диагональных элементов не строятся.) Получается граф "смежности", если так его можно назвать.
2)В графе находим вершину с минимальной степенью, ее значение записывается в вектор перестановки. (Минимальная степень - вершина соединена с минимальным количеством других вершин. Если таких вершин несколько, берется первая.) Сама вершина удаляется вместе с ребрами.
3) Алгоритм повторяется пока в графе остаются вершины.
Граф храню через списки смежности: std::vector< std::set<unsigned> > G;
Реализация:
std::vector<unsigned> 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
-я вершина или нет. Из-за этого поиск минимума идет по всем вершинам, но учитываются только не удаленные. Можно ли поправить этот момент?
std::vector<unsigned> tmp(n,1);
:) И использовать дляtmp
vector<bool>
.size()
, фактически сразу получивp[i]
, а потом с его помощью все удалять? правда, тут уползут значенияindex
...p[]
?