MATLAB Answers

John Doe

Finding the indices of all edges within k steps from a chosen line in an adjacency matrix

Asked by John Doe
on 3 May 2013

I have a function where I can find all nodes k number of steps from any initial set of nodes in a sparse adjacency matrix. Normally this intial set is the to-from node for a single branch. I want a list of the branches "used" to reach these nodes.

The function I use to find the connected nodes is as follows:

% nb = number of buses in the system
% branch_list = [from to] = the from/to nodes of each branch
adj_mat = sparse(from,to,1,nb,nb);
node_vec0 = sparse([from0 to0],1,1,nb,1);  % from0 and to0 are the "initial nodes"
A = adj_mat + speye(nb);  % Add 1's on the diagonal of the adjacency matrix
node_vec = A * node_vec0; % Vector containing all nodes connected to node_vec0

I can repeat the last line k times, and find all nodes k steps from the initial nodes.

What I want to do, is to find the row (in the branch list) of each branch used to reach these nodes.

Is there a good way of doing this without extensive use of loops? Note that I want to get a list of both the nodes, and the branches, as efficient as possible.

Thank you!


Log in to comment.

0 Answers

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Win prizes and improve your MATLAB skills

Play today