4

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

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

6
  • Как минимум первые четыре строки можно записать как std::vector<unsigned> tmp(n,1); :) И использовать для tmp vector<bool>.
    – Harry
    3 апр 2016 в 4:54
  • Это хорошо, но можно ли обойтись без tmp? 3 апр 2016 в 5:30
  • Что-то с утра ничего глобального в голову не лезет, а просто засунуть дополнительный флаг в используемую структуру данных глобально ничего не решает... Если я правильно понимаю, на каждой итерации удаляется по одному элементу из каждого вектора внутри вектора G. Т.е. все size() просто уменьшаются на единицу? И минимальным становится очередной? Нельзя ли их отсортировать заранее по size(), фактически сразу получив p[i], а потом с его помощью все удалять? правда, тут уползут значения index...
    – Harry
    3 апр 2016 в 5:37
  • Ну если отсортировать, но еще дополнительно хранить значение индекса, правда это еще порядка 30 тысяч элементов в моей ситуации. Ладно, подумаю в этом направлении 3 апр 2016 в 5:43
  • Для чего нужен p[]?
    – Cerbo
    3 апр 2016 в 10:06

2 ответа 2

1

А вы сделайте наоборот, в temp храните не признаки наличия вершины а, индексы существующих вершин. Кроме того следует хранить не сами индексы, а диапазоны индексов, то есть:

typedef std::pair<size_t, size_t> Range ;
typedef std::vector<Range>        Ranges;

std::vector<Range> 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 справа остался
                                           // старый диапазон, укоротим его
    }
}
4
  • Действительно, Ваш вариант работает. Только возникает вопрос о сложности функции erase для вектора. Насколько я понимаю, там каждый раз будет происходить сдвиг элементов? 4 апр 2016 в 3:50
  • @Евгений Да, чтобы снять все вопросы нужно профилировать.
    – Cerbo
    4 апр 2016 в 6:28
  • @Евгений Обновил ответ
    – Cerbo
    4 апр 2016 в 9:55
  • Спасибо за ответ, как будет время выложу результаты по времени выполнения 4 апр 2016 в 10:28
0

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.