MATLAB — эффективный способ вычисления расстояний между точками на графике/сети с использованием матрицы смежности и координат.

У меня есть представление сети в двумерном координатном пространстве. У меня есть матрица смежности Adj (разреженная) и матрица coordinate со значениями x, y всех точек/узлов/вершин на графике, которые нарисованы.

Я хотел бы максимально эффективно вычислить расстояние между этими точками. Я хотел бы избежать циклического перебора записей в матрице и вычисления попарных расстояний один за другим.


matlab matrix sparse-matrix matrix-multiplication euclidean-distance
person Vass    schedule 18.03.2013    source источник

Ответы (2)


arrow_upward
2
arrow_downward 

[n, d] = size(coordinate);
assert(d == 2);
resi = sparse(Adj * diag(1:n));
resj = sparse(diag(1:n) * Adj);
res = sparse(zeros(n));
f = find(Adj)
res(f) = sqrt((coordinate(resi(f), 1) - coordinate(resj(f), 1)) .^ 2 + (coordinate(resi(f), 2) - coordinate(resj(f), 2)) .^ 2);

РЕДАКТИРОВАТЬ: Ой, исправил ошибку

Уточнение: я предполагаю, что под матрицей координат вы имеете в виду http://www.passagesoftware.net/webhelp/Coordinate_Matrix.htm

РЕДАКТИРОВАТЬ 2: я на самом деле не уверен, является ли Adj матрицей логики (или может ли у вас быть разреженная матрица логики). Я исправил это, чтобы обойти эту потенциальную ловушку

person dspyz    schedule 18.03.2013
comment
Мои матрицы увеличились в размерах и Out of memory. Type HELP MEMORY for your options. Error in ==> modularize_graphs_Alex_hugeMats at 50 res(i,j) = sqrt((coordinate(resi(i,j), 1) - coordinate(resj(i,j), 1)) .^ 2 +... есть ли способ сэкономить место? Я также изменил f=find(Adj) на [i,j]=find(Adj). - person Vass; 03.04.2013
comment
Мои матрицы увеличились в размерах и ??? Error using ==> find Matrix is too large to return linear indices. Use [i,j] = find(S) for sparse matrix. Error in ==> modularize_graphs_Alex_hugeMats at 49 [f] = find(graph_temp); а потом я сделал изменение и Out of memory. Type HELP MEMORY for your options. Error in ==> modularize_graphs_Alex_hugeMats at 50 res(f) = sqrt((coordinate(resi(f), 1) - coordinate(resj(f), 1)) .^ 2 +... есть ли способ сэкономить место? - person Vass; 03.04.2013
comment
Боюсь, я не смогу вам помочь, если у вас заканчивается память. Я знаю, что в Octave есть так называемые oct-файлы для хранения действительно больших разреженных матриц, но я никогда ими не пользовался и не знаю, что есть в Matlab. - person dspyz; 07.04.2013

arrow_upward
1
arrow_downward

Если ваш график разреженный, вам следует вместо этого использовать списки смежности.

Итерация по спискам смежности позволит вам получить все пары связанных точек во времени, линейные по количеству пар, в отличие от итерации по пустым записям в матрице смежности.

person Andrew Mao    schedule 18.03.2013
comment
Проблема может быть решена вообще без итерации, как я показал в своем решении. - person dspyz; 19.03.2013
comment
Конечно, это итерация, она просто делает это на собственном уровне, а не на уровне интерпретации MATLAB. С нативным кодом все работает быстрее, но асимптотическая эффективность все равно плохая. - person Andrew Mao; 19.03.2013
comment
Это то, что я имел в виду, и даже на нативном уровне мое решение перебирает только пары в матрице смежности. - person dspyz; 19.03.2013
comment
Вы все еще перебираете всю матрицу с помощью find. - person Andrew Mao; 19.03.2013
comment
Нет, потому что Adj — разреженная матрица. Это означает, что внутри он хранится в виде списка всех ненулевых элементов. Я считаю, что find оптимизирован для разреженных матриц, чтобы просто вернуть этот список. - person dspyz; 19.03.2013