MATLAB - efficient way of computing distances between points in a graph/network using the adjacency matrix and coordinates

StackOverflow https://stackoverflow.com/questions/15482539

Frage

I have the network representation in a 2D coordinate space. I have an adjacency matrix Adj(which is sparse) and a coordinate matrix with the x,y values of all the points/nodes/vertices in the graph which are drawn.

I would like to compute as efficiently as possible the distance between these points. I would like to avoid cycling through the entries in the matrix and computing the pairwise distances one by one.

War es hilfreich?

Lösung

[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);

EDIT: Oops, fixed a bug

Clarification: I'm assuming by coordinate matrix you mean like http://www.passagesoftware.net/webhelp/Coordinate_Matrix.htm

EDIT 2: I'm actually not sure whether Adj is a matrix of logicals (or whether you can have a sparse matrix of logicals). I fixed it to sidestep that potential pitfall

Andere Tipps

If your graph is sparse, then you should consider using adjacency lists instead.

Iterating through the adjacency lists will allow you to get all pairs of connected points in time linear in the number of pairs, as opposed iterating through empty entries in the adjacency matrix.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top