Finding a chain in an adjacency matrix

Question

Josue Sandoval 2016-10-25

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/308976-finding-a-chain-in-an-adjacency-matrix

评论： 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 2016-10-25

Hello Josue, If A is an adjacency matrix, could you explain how it is not a square matrix?

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.

请先登录，再进行评论。

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

Answer 1

Walter Roberson 2016-10-25

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/308976-finding-a-chain-in-an-adjacency-matrix#answer_240619

在 MATLAB Online 中打开

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更早的评论隐藏 2更早的评论

Josue Sandoval 2016-10-30

在 MATLAB Online 中打开

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 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

请先登录，再进行评论。