Mercurial > hg > camir-aes2014
annotate toolboxes/FullBNT-1.0.7/graph/reachability_graph.m @ 0:e9a9cd732c1e tip
first hg version after svn
| author | wolffd |
|---|---|
| date | Tue, 10 Feb 2015 15:05:51 +0000 |
| parents | |
| children |
| rev | line source |
|---|---|
| wolffd@0 | 1 function C = reachability_graph(G) |
| wolffd@0 | 2 % REACHABILITY_GRAPH C(i,j) = 1 iff there is a path from i to j in DAG G |
| wolffd@0 | 3 % C = reachability_graph(G) |
| wolffd@0 | 4 |
| wolffd@0 | 5 if 1 |
| wolffd@0 | 6 % expm(G) = I + G + G^2 / 2! + G^3 / 3! + ... |
| wolffd@0 | 7 M = expm(double(full(G))) - eye(length(G)); |
| wolffd@0 | 8 C = (M>0); |
| wolffd@0 | 9 else |
| wolffd@0 | 10 % This computes C = G + G^2 + ... + G^{n-1} |
| wolffd@0 | 11 n = length(G); |
| wolffd@0 | 12 A = G; |
| wolffd@0 | 13 C = zeros(n); |
| wolffd@0 | 14 for i=1:n-1 |
| wolffd@0 | 15 C = C + A; |
| wolffd@0 | 16 A = A * G; |
| wolffd@0 | 17 end |
| wolffd@0 | 18 C = (C > 0); |
| wolffd@0 | 19 end |