Finding a chain in an adjacency matrix
9 views (last 30 days)
Show older comments
Josue Sandoval
on 25 Oct 2016
Commented: Walter Roberson
on 30 Oct 2016
Hi everyone,
I have a binary matrix A representing edges in a graph, of size n x m. It is easy to know if elements i and j are connected by an edge: I simply look up if A(i,j)==1. However, I want to know if there is a chain of size k (or smaller) that connects i and j. For example, A(i,k)==1 and A(k,j)==1. Any ideas or maybe a pre-existing function that I have not found?
I have no interest whatsoever in finding the shortest path, I just care if there is any. Thanks
2 Comments
David Goodmanson
on 25 Oct 2016
Hello Josue, If A is an adjacency matrix, could you explain how it is not a square matrix?
Accepted Answer
Walter Roberson
on 25 Oct 2016
T = eye(size(A)) ;
found = false;
for n = 0 : k - 1
if T(i, j)
found = true;
break;
end
T = T * A;
end
chain_exists = found | T(i, j);
4 Comments
Walter Roberson
on 30 Oct 2016
If you want a new figure (that is, a completely new graphics window) and you want it to start out with what is in another figure, then you need to copyobj() appropriate children of the old figure into the new figure.
If what you want is a new subplot (that is, a section of an window that can be independently drawn in) and you want it to start out with what is in another subplot, then you need to copyobj() appropriate children of the old axes into the new axes.
Doing a proper copyobj of children of a figure is trickier than doing a proper copyobj of children of an axes. Some of the tricks are shown at http://www.mathworks.com/matlabcentral/answers/262265-duplicating-an-imshow-image-into-a-new-figure-without-using-imshow#comment_332459
See Also
Categories
Find more on Graph and Network Algorithms in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!