Mercurial > hg > camir-aes2014
annotate toolboxes/FullBNT-1.0.7/graph/mk_nbrs_of_dag.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 [Gs, op, nodes] = mk_nbrs_of_dag(G0) |
| wolffd@0 | 2 % MK_NBRS_OF_DAG Make all DAGs that differ from G0 by a single edge deletion, addition or reversal |
| wolffd@0 | 3 % [Gs, op, nodes] = mk_nbrs_of_dag(G0) |
| wolffd@0 | 4 % |
| wolffd@0 | 5 % Gs{i} is the i'th neighbor. |
| wolffd@0 | 6 % op{i} = 'add', 'del', or 'rev' is the operation used to create the i'th neighbor. |
| wolffd@0 | 7 % nodes(i,1:2) are the head and tail of the operated-on arc. |
| wolffd@0 | 8 |
| wolffd@0 | 9 Gs = {}; |
| wolffd@0 | 10 op = {}; |
| wolffd@0 | 11 nodes = []; |
| wolffd@0 | 12 |
| wolffd@0 | 13 [I,J] = find(G0); |
| wolffd@0 | 14 nnbrs = 1; |
| wolffd@0 | 15 % all single edge deletions |
| wolffd@0 | 16 for e=1:length(I) |
| wolffd@0 | 17 i = I(e); j = J(e); |
| wolffd@0 | 18 G = G0; |
| wolffd@0 | 19 G(i,j) = 0; |
| wolffd@0 | 20 Gs{nnbrs} = G; |
| wolffd@0 | 21 op{nnbrs} = 'del'; |
| wolffd@0 | 22 nodes(nnbrs, :) = [i j]; |
| wolffd@0 | 23 nnbrs = nnbrs + 1; |
| wolffd@0 | 24 end |
| wolffd@0 | 25 |
| wolffd@0 | 26 % all single edge reversals |
| wolffd@0 | 27 for e=1:length(I) |
| wolffd@0 | 28 i = I(e); j = J(e); |
| wolffd@0 | 29 G = G0; |
| wolffd@0 | 30 G(i,j) = 0; |
| wolffd@0 | 31 G(j,i) = 1; |
| wolffd@0 | 32 if acyclic(G) |
| wolffd@0 | 33 Gs{nnbrs} = G; |
| wolffd@0 | 34 op{nnbrs} = 'rev'; |
| wolffd@0 | 35 nodes(nnbrs, :) = [i j]; |
| wolffd@0 | 36 nnbrs = nnbrs + 1; |
| wolffd@0 | 37 end |
| wolffd@0 | 38 end |
| wolffd@0 | 39 |
| wolffd@0 | 40 [I,J] = find(~G0); |
| wolffd@0 | 41 % all single edge additions |
| wolffd@0 | 42 for e=1:length(I) |
| wolffd@0 | 43 i = I(e); j = J(e); |
| wolffd@0 | 44 if i ~= j % don't add self arcs |
| wolffd@0 | 45 G = G0; |
| wolffd@0 | 46 G(i,j) = 1; |
| wolffd@0 | 47 if G(j,i)==0 % don't add i->j if j->i exists already |
| wolffd@0 | 48 if acyclic(G) |
| wolffd@0 | 49 Gs{nnbrs} = G; |
| wolffd@0 | 50 op{nnbrs} = 'add'; |
| wolffd@0 | 51 nodes(nnbrs, :) = [i j]; |
| wolffd@0 | 52 nnbrs = nnbrs + 1; |
| wolffd@0 | 53 end |
| wolffd@0 | 54 end |
| wolffd@0 | 55 end |
| wolffd@0 | 56 end |
| wolffd@0 | 57 |
| wolffd@0 | 58 |
| wolffd@0 | 59 |
| wolffd@0 | 60 |
| wolffd@0 | 61 |
| wolffd@0 | 62 |
| wolffd@0 | 63 |
| wolffd@0 | 64 |