как переиндексировать разреженный ассоциативный массив

Пусть E[m+1][m+1] будет двумерной матрицей смежности, соответствующей edges, где диапазон точечных индексов равен [0..m].

Пусть f[n] будет отсортированным массивом n точек, посещенных в edges. Создавая массив f[n], мы создаем сопоставление между индексами несмежных точек в диапазоне [0..m] и индексами смежных точек из [0..n-1].

Создайте новую матрицу смежности G следующим образом:

for i = 0..(n-1)
    for j = 0..(n-1)    // or, j = (i+1)..(n-1) for upper triangular portion
        G[i][j] = E[f[i]][f[j]]
    end
end

Это займет всего O (n ^ 2), а не O (m ^ 2) времени.

Изменить: удален оператор if. Если и E, и G инициализированы всеми 0, это не нужно.

Поскольку ваша матрица разрежена, я предлагаю вам использовать структуру данных отсортированного списка для создания разреженной структуры из вашего списка ребер. Для каждой строки вам нужно создать динамический отсортированный список (в порядке возрастания), в который вы добавляете ребра. Например, для ребра (1,2) вы вставите столбец 2 в отсортированный список sorted_lists{1}. Для небольшого количества записей в строке (несколько сотен) лучше всего использовать линейный поиск в отсортированных списках с последующим перемещением более крупных элементов в конец списка. Для большего количества записей в строке вы можете использовать деление пополам, чтобы найти правильную позицию. Я обычно использую этот подход для разреженных матриц, возникающих в методе конечных элементов. По моему опыту, это самый быстрый подход, и его можно тривиально распараллелить! (разделить диапазоны строк между потоками)

Вот пример кода MATLAB, который реализует отсортированный список:

function list = sorted_list_insert(list, col)

% special case for empty list
if isempty(list)
    list = col;
    return;
end

% search for col position in the row
% can be done with bisection,
% but linear search is much faster for small number of entries per row
it = 1;
while it<length(list) && list(it)<col
    it = it+1;
end

% duplicate entry - do not add
if list(it)==col
    return;
end

% insert col in proper position, move other elements in the list
list = [list(1:it) col list(it+1:end)];
end

Сложность добавления всех записей подряд в этот отсортированный список составляет O(number of entries per row ^ 2).

Следующее, что вам нужно сделать, это пройтись по списку ребер и добавить столбцы, чтобы исправить списки, отсортированные по строкам (sorted_lists{row}). В приведенном ниже edges предполагается двумерный массив, где edges(1,i) — это столбец, а edges(2,i) — это строка:

% find maximum row id
max_row = number of rows in the matrix

% initialize sorted list structures for all rows - max_row empty lists
sorted_lists = cell(max_row, 1);

% create sorted rows
nedges = total number of edges
for it=1:nedges
    row = edges(2,it);
    col = edges(1,it);
    sorted_lists{row} = sorted_list_insert(sorted_lists{row}, col);
end

Сложность вышеуказанного шага O(number of rows * number of entries per row ^ 2).

Последнее, что нужно сделать, это убрать пробелы. В отсортированных списках это легко сделать, найдя позицию col в отсортированных списках. Вы также должны добавить смещение. Судя по вашим данным, вы имеете дело с верхнетреугольной частью матрицы (вы сказали, что порядок узлов на краях не имеет значения). Таким образом, смещение — это просто номер строки (-1 в MATLAB, поскольку он имеет нумерацию, основанную на 1)

% the positions of col in every row (plus offset)
% are the new col id with removed gaps
for it=1:nedges
    offset = edges(2,it)-1;
    edges(1,it) = offset + find(sorted_lists{edges(2,it)}==edges(1,it));
end

Вот как выглядит edges после обработки приведенным выше кодом:

edges =

Columns 1 through 13

 1     2     3     4     2     3     3     4     5     4     5     6     5
 1     1     1     1     2     2     3     3     3     4     4     4     5

Columns 14 through 20

 6     7     8     9    10    11    12
 5     5     5     5     5     5     5

Процедура отлично работает для отсортированных и несортированных ребер. Это только предполагает, что col >= row. Которого вы можете легко достичь. Вы также можете легко добавить удаление диагональных (i,i) ребер.