blob: 0f3c4f58550cf9eb3e89d9de02a9803f463435a7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
function C = reachability_graph(G)
% REACHABILITY_GRAPH C(i,j) = 1 iff there is a path from i to j in DAG G
% C = reachability_graph(G)
if 1
% expm(G) = I + G + G^2 / 2! + G^3 / 3! + ...
M = expm(double(full(G))) - eye(length(G));
C = (M>0);
else
% This computes C = G + G^2 + ... + G^{n-1}
n = length(G);
A = G;
C = zeros(n);
for i=1:n-1
C = C + A;
A = A * G;
end
C = (C > 0);
end
|
