Finding a chain in an adjacency matrix

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

[David Goodmanson]

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

[Josue Sandoval]

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]

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

[Josue Sandoval]

Sorry but I just don't get it.

[Walter Roberson]

This uses the Adjacency matrix A . A mathematical way to find out which places you can reach from where you are is to multiply by the adjacency matrix. Keep doing that up to k times; when you get a non-zero entry for the location combining the source and destination indices then you know that you were able to reach the destination after that many steps.

[Josue Sandoval]

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]

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

Answer 2

[Thorsten]

You can use the power of the adjacency matrix as detailed in

http://math.stackexchange.com/questions/222429/graph-theory-shortest-path-problem-via-matrix-operations-in-matlab