Finding a chain in an adjacency matrix
9 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Josue Sandoval
le 25 Oct 2016
Commenté : Walter Roberson
le 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 commentaires
David Goodmanson
le 25 Oct 2016
Hello Josue, If A is an adjacency matrix, could you explain how it is not a square matrix?
Réponse acceptée
Walter Roberson
le 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 commentaires
Walter Roberson
le 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
Voir également
Catégories
En savoir plus sur Graph and Network Algorithms dans Help Center et File Exchange
Produits
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!