8 views (last 30 days)

I would like to do this, but in Matlab with a graph (it is not a directed graph): https://stackoverflow.com/questions/18393842/k-th-order-neighbors-in-graph-python-networkx

I have a graph in which I want to efficiently find a list of all K-th order neighbors of a node (j). K-th order neighbors are defined as all nodes which can be reached from the node in question in exactly K hops.

For example,

s = [1 1 1 1 2 2 2 2 2 8 8 12 6];

t = [3 5 4 2 6 10 7 9 8 11 12 13 7];

G = graph(s,t);

plot(G)

If j=1, I want to get :

for k=1

[2 3 4 5]

for k=2

[6 7 8 9 10]

for k=3

[11 12]

k=4

[13]

k=5

empthy

Matt J
on 24 Jul 2020

Edited: Matt J
on 25 Jul 2020

function result=distk(G,i,k)

% G -graph

% i - start node

% k - number of steps

A=adjacency(G);

v=A(i,:);

prior=false(size(v)); prior(i)=true;

for n=1:k-1

prior=prior|v;

v=v*A;

end

result = find(v&~prior);

end

Bruno Luong
on 29 Jul 2020

"A drawback of Bruno's approach that I see is that its use of distances() will compute all distances, even those greater than the particular k of interest."

I just did some benchmark, and Matlab graph distances seems to be pretty fast and beat all even for small k and large n. Let alone the case where k is large.

If that is matter at all.

Bruno Luong
on 29 Jul 2020

Here is my benchmark code, feel free to play with it.

function BenchGNeighbor

start = 1; % starting node

% Graph corresponds to the 2D square grid of size 1000 x 1000

[X,Y] = ndgrid(1:1000);

n = numel(X);

I = sub2ind(size(X),X(1:end-1,:),Y(1:end-1,:));

J = I+1;

A = sparse(I,J,1,n,n);

I = sub2ind(size(X),X(:,1:end-1),Y(:,1:end-1));

J = I+size(X,1);

A = A + sparse(I,J,1,n,n);

A = A + A';

G = graph(A);

k = 100; %size(X,1);

% clean memory

clear X Y I J

k = min(k,size(A,1));

%% Matlab graph distances method

tic

d = distances(G, start);

rMatlab = find(d==k);

tMatlab = toc;

%% Bruno's algorithm

tic

n = size(A,1);

% initialize distance matrix

notdone = true(n,1);

i = start;

for q=1:k

notdone(i) = false;

[i,~] = find(A(:,i));

if isempty(i)

break

end

i = unique(i);

i = i(notdone(i));

end

rBruno = reshape(i,1,[]);

tBruno = toc;

%% Matt method

tic

i = start; % start node

v = A(i,:);

prior = false(size(v));

prior(i) = true;

for j=1:k-1

prior = prior|v;

v = v*A;

end

rMatt = find(v & ~prior);

tMatt = toc;

% Check matching results

if ~isequal(rBruno, rMatlab) || ~isequal(rMatt, rMatlab)

fprintf('Bug detected!!!\n');

end

fprintf('Timings for 2D-grid graph with number of nodes = %d, k=%d\n', n, k);

fprintf('\ttMatlab = %f [second]\n', tMatlab);

fprintf('\ttBruno = %f [second]\n', tBruno);

fprintf('\ttMatt = %f [second]\n', tMatt);

Bruno Luong
on 25 Jul 2020

Edited: Bruno Luong
on 28 Jul 2020

It sounds like you look at graph-distance and NOT what you described "K-th order neighbors are defined as all nodes which can be reached from the node in question in exactly K hops." The later problem is solved by my other answer.

If it is is the first case (graph distance) one can do by shortest path algorithms such as Bellman-Ford (BF) algorithm.

Graph example (yours):

s = [1 1 1 1 2 2 2 2 2 8 8 12 14 14 1 14];

t = [3 5 4 2 6 10 7 9 8 11 12 13 7 6 8 15];

G = graph(s,t);

plot(G)

BF algo (note: the bellow is not optimal implemented, since using full matrix with Inf).

start = 1; % starting node

B = adjacency(G);

B = full(B);

B(B==0) = Inf;

n = size(B,1);

d = inf(n,1);

d(start) = 0;

while any(isinf(d)) % careful graph must be connected, otherwise loop forever

d = min(d,min(d+B,[],1).');

end

Or simply using MATLAB stock function

d = distances(G,start);

% neighhbor for any specific k, e.g. k=2; neightbors i are

% i = find(d==k)

Display result

n = size(G.Nodes,1);

nodes = setdiff(1:n,start)';

d = d(:);

dcell = accumarray(d(nodes), nodes, [], @(x) {x.'});

K = (1:length(dcell))';

for k=1:length(dcell)

i = dcell{k};

fprintf('k = %d: i = %s\n', k, mat2str(i));

end

Result

k = 1: i = [2 3 4 5 8]

k = 2: i = [6 7 9 10 11 12]

k = 3: i = [13 14]

k = 4: i = 15

Bruno Luong
on 28 Jul 2020

In the above I code Bellman-Ford algorithm like this single-line while loop for illustration purpose:

% ...

% Initialization of d and B

while any(isinf(d)) % careful graph must be connected, otherwise loop forever

d = min(d,min(d+B,[],1).');

end

A better implementation of Bellman-Ford algorithm that exploits the sparsity of ajadcent matrix to compute the shortest distance is

start = 1; % starting node

A = adjacency(G); % eventually with non-unit and non-negative weight

n = size(A,1);

% initialize distance matrix

d = inf(n,1);

du = 0;

i = start;

while true

d(i) = du;

[i,j,dij] = find(A(:,i));

if isempty(i)

break

end

[du, p] = sort(du(j)+dij);

[i, p] = sort(i(p)); % here we requires stable sorting, which is the case with MATLAB

b = [true; diff(i,1,1)>0];

i = i(b);

du = du(p(b));

b = du < d(i);

i = i(b);

du = du(b);

end

% Exit the while-loop d contains distance vector from start-node to all nodes

Bruno Luong
on 24 Jul 2020

Edited: Bruno Luong
on 24 Jul 2020

Assuming A is the transposed of the adjacent matrix (n x n).

j in (1:n) is the source node number.

This method should be faster than computing A^k proposed by Matt

x = zeros(n,1);

x(j) = 1;

for i=1:k

x = A*x;

end

i = find(x)';

fprintf('%d-neighbor of %d is %s\n', k, j, mat2str(i))

If sparse form of the adjadcent matrix is readily available, it could be preferable to use it.

Bruno Luong
on 24 Jul 2020

When you allow to go from s to t, and forbid to go in the opposite direction from t to s, it's called digraph

s = [1 1 1 1 2 2 2 2 2 8 8 12];

t = [3 5 4 2 6 10 7 9 8 11 12 13];

G = digraph(s,t);

plot(G)

A = adjacency(G).';

n = size(A,1);

x = zeros(n,1);

x(1) = 1;

for k=1:5

x = A*x;

i = find(x)';

fprintf('k = %d: i = %s\n', k, mat2str(i));

end

Output match your expectation

k = 1: i = [2 3 4 5]

k = 2: i = [6 7 8 9 10]

k = 3: i = [11 12]

k = 4: i = 13

k = 5: i = zeros(1,0)

Bruno Luong
on 31 Jul 2020

Edited: Bruno Luong
on 31 Jul 2020

Given A an (n x n) symmetric ajadcent matrix (undirected graph), and k the order (integer scalar), I propose this algorithm to find index of all k-neigbor of node #start

n = size(A,1);

k = min(k,n);

notdone = true(n,1);

i = start;

for q=1:k

notdone(i) = false;

[i,~] = find(A(:,i));

if isempty(i)

break

end

i = unique(i);

i = i(notdone(i));

end

neighbouridx = i; % column vector

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
## 0 Comments

Sign in to comment.