Finding a chain in an adjacency matrix

4 次查看（过去 30 天）
Josue Sandoval
Josue Sandoval 2016-10-25
评论： Walter Roberson 2016-10-30
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 个评论
David Goodmanson
David Goodmanson 2016-10-25
Hello Josue, If A is an adjacency matrix, could you explain how it is not a square matrix?
Josue Sandoval
Josue Sandoval 2016-10-30
I meant the size is (m*n) for each the number of rows and the number of columns. Sorry about that.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Walter Roberson
Walter Roberson 2016-10-25
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 个评论
显示 2更早的评论
Josue Sandoval
Josue Sandoval 2016-10-30
I understood what you meant after reading Seidel's shortest path algorithm (not the code but the idea). I implemented something completely brute force but that seems to work. I put the code below in case you want to see it. I think it should work.
A different question is simpler: I need to make a new figure, so I just type "figure". However, I want that the new figure keeps every plot in the old figure. I put hold on's everywhere but I guess they don't do the work. Any ideas?
%number=percentage of the society married;
%avgdistance=average distance between marriages;
%race
n=4;m=2;p=1;q=0.2;
rng(10,'twister');
x=rand(m,n); y=rand(m,n);
%sex=round(rand(m,n));
k=round(.4*n);kk=round(.4*n);
temp = [ones(m,kk), zeros(m,k), round(rand(m,n-k-kk))]
[~, idx] = sort( rand(m,n), 2)
sex = temp(sub2ind(size(temp), ndgrid(1:m,1:n), idx))
women=find(sex');men=find(~sex');
x1=reshape(x',1,n*m); y1=reshape(y',1,n*m); sex1=reshape(sex',1,n*m);
%Part 1: edges
colorstring = 'kbmcgy';hold on
for i = 1:m
for k=1:n
if sex(i,k)==1;
plot(x(i,k),y(i,k),'P', 'Color', colorstring(i),'MarkerFaceColor', colorstring(i),'MarkerSize',12)
else
plot(x(i,k),y(i,k),'O', 'Color', colorstring(i),'MarkerFaceColor', colorstring(i),'MarkerSize',10)
end
end
end
%Part 2: interracial edges
adj=zeros(m*n); boxes=(((m-1)*m)/2)*n^2;inter_edges=randsample(boxes,floor(boxes*q));
rr=1;
for i=1:(m*n)
for j=n+floor((i-1)/n)*n+1:(m*n)
if i~=j
if any(rr==inter_edges)
adj(i,j)=1;
end
rr=rr+1;
end
end
end
for i=1:n*m
for j=1:n*m
if adj(i,j)==1
plot([x1(1,i) x1(1,j)],[y1(1,i) y1(1,j)],':')
end
end
end
%Part 3: intraracial edges
intra_edges=rand(n*m);rr=0;
for i=1:n*m
rr=floor((i-1)/n);
for j=i+1:(rr*n)+n
if intra_edges(i,j)<p %
adj(i,j)=1;
end
end
end
adj=triu(adj,-1)+triu(adj)'
for k=1:m
for i=1:n
for j=i+1:n
if adj(j,i)==1
plot([x(k,i) x(k,j)],[y(k,i) y(k,j)],'Color', colorstring(k))
end
end
end
end
adj2=adj*adj;
adj3=zeros(m*n);
for i=1:m*n
for j=i+1:m*n
if adj2(i,j)+adj(i,j)>0
adj3(i,j)=1
end
end
end
adj3=triu(adj3,-1)+triu(adj3)'
%Part 4: distances
distance=zeros(n*m,m*n);
for i=1:m*n
for j=i:m*n
if i==j
distance(i,j)=NaN;
else
if adj3(i,j)==0
distance(i,j)=NaN;
else
if sex1(i)==sex1(j)
distance(i,j)=NaN;
else
distance(i,j)=sqrt((x1(i) - x1(j))^2 + (y1(i) - y1(j))^2);
end
end
end
end
end
distance=triu(distance,-1)+triu(distance)'
%Part 5: marriages
marr=zeros(1,m*n);
marriage=zeros(1,m*n);
for i=1:n*m
[~, marr(1,i)]=min(distance(i,:));
end
c=1;
while c <= min(nnz(sex),numel(sex)-nnz(sex))
for i=1:n*m
if i==marr(marr(i));
marriage(i)=marr(i);
end
end
for i=find(marriage==0)
if marriage(marr(i))~=0;
distance(i, marr(i))=NaN;
%distance(MARR(i),i)=NaN;
end
end
for i=1:n*m
[~, marr(1,i)]=min(distance(i,:));
end
c=c+1;
end
for i=1:m*n
if marriage(i)==i
marriage(i)=0;
end
end
hold on
figure
hold on
for i=1:n*m
if marriage(i)~=0
plot([x1(1,i) x1(1,marriage(1,i))],[y1(1,i) y1(marriage(1,i))],'red','LineWidth',3)
end
end
%Part 6: welfare measures
number=size(find(marriage),2)/2;
avgdist=0;
for i=find(marriage>0)
avgdist=avgdist+distance(i,marriage(i));
end
avgdist=avgdist/(2*size(find(marriage>0),2));
race=0;
for i=1:m*n
if marriage(i)>0
if marriage(i)<=(1+floor((i-1)/n))*n && marriage(i)>floor((i-1)/n)*n
race=race+1;
end
end
end
race=race/2;race=number-race;
formatSpec = '#marriages %.0f (%.0f), avgdist %.4f, p=%.2f, q=%.2f';
str = sprintf(formatSpec,number,race,avgdist,p,q)
title(str);
race=race/number
number=(number*2)/(n*m)
adj3
Walter Roberson
Walter Roberson 2016-10-30
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

请先登录，再进行评论。

更多回答（1 个）

Thorsten
Thorsten 2016-10-25
编辑：Thorsten 2016-10-25

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by