Skip to content

Instantly share code, notes, and snippets.

@fronx
Forked from moink/transclose.m
Created October 25, 2011 22:05
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save fronx/1314504 to your computer and use it in GitHub Desktop.
Save fronx/1314504 to your computer and use it in GitHub Desktop.
Transitive closure solution in Matlab
function A=transclose(A)
%returns the transitive closure matrix of the input matrix
%input: A(i,j) is 1 if the binary relation if (element i) R (element j) using the
%notation in the introduction of http://en.wikipedia.org/wiki/Transitive_closure
%
%Usage example: Implements the first example problem on https://www.4clojure.com/problem/84
%
%divideskey=[2 3 4 8 9 27];
%%I don't actually use that variable, but it keeps track of what my matrix means
%
%divides=zeros(6)
%
%divides(4,3)=1 %Add [8,4] to the relation
%divides(5,2)=1 %Add [9 3] to the relation
%divides(3,1)=1 %Add [4 2] to the relation
%divides(6,5)=1 %Add [27 9] to the relation
%
%divides=[
% 0 0 0 0 0 0
% 0 0 0 0 0 0
% 1 0 0 0 0 0
% 0 0 1 0 0 0
% 0 1 0 0 0 0
% 0 0 0 0 1 0];
%
%transdiv=transclose(divides);
%%this returns the matrix
% transdiv=[
% 0 0 0 0 0 0
% 0 0 0 0 0 0
% 1 0 0 0 0 0
% 1 0 1 0 0 0
% 0 1 0 0 0 0
% 0 1 0 0 1 0];
for i = 1:size(A,1)
for j = 1:size(A,2)
t=(A(i,j)==1 & A(j,:)==1);
A(i,t)=1;
end
end
@Saadallah
Copy link

when
A=[1 0 0 1;0 1 1 0;0 1 1 1;1 0 1 1] ;
A is symmetric, but the result is not.
we have A(1,4)=A(4,3)=A(3,2)=1 and transclose(A)(1,2)=0 !

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment