To check out this repository please hg clone the following URL, or open the URL using EasyMercurial or your preferred Mercurial client.
root / _FullBNT / BNT / graph / reachability_graph.m @ 8:b5b38998ef3b
History | View | Annotate | Download (430 Bytes)
| 1 |
function C = reachability_graph(G) |
|---|---|
| 2 |
% REACHABILITY_GRAPH C(i,j) = 1 iff there is a path from i to j in DAG G |
| 3 |
% C = reachability_graph(G) |
| 4 |
|
| 5 |
if 1 |
| 6 |
% expm(G) = I + G + G^2 / 2! + G^3 / 3! + ... |
| 7 |
M = expm(double(full(G))) - eye(length(G)); |
| 8 |
C = (M>0); |
| 9 |
else |
| 10 |
% This computes C = G + G^2 + ... + G^{n-1}
|
| 11 |
n = length(G); |
| 12 |
A = G; |
| 13 |
C = zeros(n); |
| 14 |
for i=1:n-1 |
| 15 |
C = C + A; |
| 16 |
A = A * G; |
| 17 |
end |
| 18 |
C = (C > 0); |
| 19 |
end |