Finding a chain in an adjacency matrix
9 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Josue Sandoval
el 25 de Oct. de 2016
Comentada: Walter Roberson
el 30 de Oct. de 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 comentarios
David Goodmanson
el 25 de Oct. de 2016
Hello Josue, If A is an adjacency matrix, could you explain how it is not a square matrix?
Respuesta aceptada
Walter Roberson
el 25 de Oct. de 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 comentarios
Walter Roberson
el 30 de Oct. de 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
Ver también
Categorías
Más información sobre Graph and Network Algorithms en Help Center y File Exchange.
Productos
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!