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

#cpp #алгоритм #cpp11

Работаю с разреженными матрицами. Возникала необходимость перестановки строк и столбцов
с целью сократить "заполненность" матрицы после разложения Холецкого. Итак сам алгоритм:

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-я вершина или нет. Из-за этого поиск минимума идет по
всем вершинам, но учитываются только не удаленные. Можно ли поправить этот момент?
    

Ответы

Ответ 1

А вы сделайте наоборот, в 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 справа остался
                                           // старый диапазон, укоротим его
    }
}


Ответ 2

Алгоритм минимальной степени не верно описали : "Сама вершина удаляется вместе с
ребрами." но рёбра могут и добавляться. Если у нас было три вершины A B C а рёбра только
между AB и AC и мы удаляем вершину A с рёбрами AB и AC, до надо добавить ребро BC в граф.