|
wolffd@0
|
1 function [Gs, op, nodes] = mk_nbrs_of_digraph(G0)
|
|
wolffd@0
|
2 % MK_NBRS_OF_DIGRAPH Make all digraphs that differ from G0 by a single edge deletion, addition or reversal
|
|
wolffd@0
|
3 % [Gs, op, nodes] = mk_nbrs_of_digraph(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 debug = 0; % the vectorized version is about 3 to 10 times faster
|
|
wolffd@0
|
10
|
|
wolffd@0
|
11 n = length(G0);
|
|
wolffd@0
|
12 [I,J] = find(G0); % I(k), J(k) is the k'th edge
|
|
wolffd@0
|
13 E = length(I); % num edges present in G0
|
|
wolffd@0
|
14
|
|
wolffd@0
|
15 % SINGLE EDGE DELETIONS
|
|
wolffd@0
|
16
|
|
wolffd@0
|
17 Grep = repmat(G0(:), 1, E); % each column is a copy of G0
|
|
wolffd@0
|
18 % edge_ndx(k) is the scalar location of the k'th edge
|
|
wolffd@0
|
19 edge_ndx = find(G0);
|
|
wolffd@0
|
20 % edge_ndx = subv2ind([n n], [I J]); % equivalent
|
|
wolffd@0
|
21 % We set (ndx(k), k) to 0 for k=1:E in Grep
|
|
wolffd@0
|
22 ndx = subv2ind(size(Grep), [edge_ndx(:) (1:E)']);
|
|
wolffd@0
|
23 G1 = Grep;
|
|
wolffd@0
|
24 G1(ndx) = 0;
|
|
wolffd@0
|
25 Gdel = reshape(G1, [n n E]);
|
|
wolffd@0
|
26
|
|
wolffd@0
|
27
|
|
wolffd@0
|
28 % if debug
|
|
wolffd@0
|
29 % % Non-vectorized version
|
|
wolffd@0
|
30 % ctr = 1;
|
|
wolffd@0
|
31 % for e=1:E
|
|
wolffd@0
|
32 % i = I(e); j = J(e);
|
|
wolffd@0
|
33 % Gdel2(:,:,ctr) = G0;
|
|
wolffd@0
|
34 % Gdel2(i,j,ctr) = 0;
|
|
wolffd@0
|
35 % ctr = ctr + 1;
|
|
wolffd@0
|
36 % end
|
|
wolffd@0
|
37 % assert(isequal(Gdel, Gdel2));
|
|
wolffd@0
|
38 % end
|
|
wolffd@0
|
39
|
|
wolffd@0
|
40
|
|
wolffd@0
|
41 % SINGLE EDGE REVERSALS
|
|
wolffd@0
|
42
|
|
wolffd@0
|
43 % rev_edge_ndx(k) is the scalar location of the k'th reversed edge
|
|
wolffd@0
|
44 %rev_edge_ndx = find(G0'); % different order to edge_ndx, which is bad
|
|
wolffd@0
|
45 rev_edge_ndx = subv2ind([n n], [J I]);
|
|
wolffd@0
|
46 % We set (rev_edge_ndx(k), k) to 1 for k=1:E in G1
|
|
wolffd@0
|
47 % We have already deleted i->j in the previous step
|
|
wolffd@0
|
48 ndx = subv2ind(size(Grep), [rev_edge_ndx(:) (1:E)']);
|
|
wolffd@0
|
49 G1(ndx) = 1;
|
|
wolffd@0
|
50 Grev = reshape(G1, [n n E]);
|
|
wolffd@0
|
51
|
|
wolffd@0
|
52 % if debug
|
|
wolffd@0
|
53 % % Non-vectorized version
|
|
wolffd@0
|
54 % ctr = 1;
|
|
wolffd@0
|
55 % for e=1:E
|
|
wolffd@0
|
56 % i = I(e); j = J(e);
|
|
wolffd@0
|
57 % Grev2(:,:,ctr) = G0;
|
|
wolffd@0
|
58 % Grev2(i,j,ctr) = 0;
|
|
wolffd@0
|
59 % Grev2(j,i,ctr) = 1;
|
|
wolffd@0
|
60 % ctr = ctr + 1;
|
|
wolffd@0
|
61 % end
|
|
wolffd@0
|
62 % assert(isequal(Grev, Grev2));
|
|
wolffd@0
|
63 % end
|
|
wolffd@0
|
64
|
|
wolffd@0
|
65
|
|
wolffd@0
|
66 % SINGLE EDGE ADDITIONS
|
|
wolffd@0
|
67
|
|
wolffd@0
|
68 Gbar = ~G0; % Gbar(i,j)=1 iff there is no i->j edge in G0
|
|
wolffd@0
|
69 Gbar = setdiag(Gbar, 0); % turn off self loops
|
|
wolffd@0
|
70 [Ibar,Jbar] = find(Gbar);
|
|
wolffd@0
|
71
|
|
wolffd@0
|
72 bar_edge_ndx = find(Gbar);
|
|
wolffd@0
|
73 Ebar = length(Ibar); % num edges present in Gbar
|
|
wolffd@0
|
74 Grep = repmat(G0(:), 1, Ebar); % each column is a copy of G0
|
|
wolffd@0
|
75 ndx = subv2ind(size(Grep), [bar_edge_ndx(:) (1:Ebar)']);
|
|
wolffd@0
|
76 Grep(ndx) = 1;
|
|
wolffd@0
|
77 Gadd = reshape(Grep, [n n Ebar]);
|
|
wolffd@0
|
78
|
|
wolffd@0
|
79 % if debug
|
|
wolffd@0
|
80 % % Non-vectorized version
|
|
wolffd@0
|
81 % ctr = 1;
|
|
wolffd@0
|
82 % for e=1:length(Ibar)
|
|
wolffd@0
|
83 % i = Ibar(e); j = Jbar(e);
|
|
wolffd@0
|
84 % Gadd2(:,:,ctr) = G0;
|
|
wolffd@0
|
85 % Gadd2(i,j,ctr) = 1;
|
|
wolffd@0
|
86 % ctr = ctr + 1;
|
|
wolffd@0
|
87 % end
|
|
wolffd@0
|
88 % assert(isequal(Gadd, Gadd2));
|
|
wolffd@0
|
89 % end
|
|
wolffd@0
|
90
|
|
wolffd@0
|
91
|
|
wolffd@0
|
92 Gs = cat(3, Gdel, Grev, Gadd);
|
|
wolffd@0
|
93
|
|
wolffd@0
|
94 nodes = [I J;
|
|
wolffd@0
|
95 I J;
|
|
wolffd@0
|
96 Ibar Jbar];
|
|
wolffd@0
|
97
|
|
wolffd@0
|
98 op = cell(1, E+E+Ebar);
|
|
wolffd@0
|
99 op(1:E) = {'del'};
|
|
wolffd@0
|
100 op(E+1:2*E) = {'rev'};
|
|
wolffd@0
|
101 op(2*E+1:end) = {'add'};
|
|
wolffd@0
|
102
|
|
wolffd@0
|
103
|
|
wolffd@0
|
104 % numeric output:
|
|
wolffd@0
|
105 % op(i) = 1, 2, or 3, if the i'th neighbor was created by adding, deleting or reversing an arc.
|
|
wolffd@0
|
106
|
|
wolffd@0
|
107 ADD = 1;
|
|
wolffd@0
|
108 DEL = 2;
|
|
wolffd@0
|
109 REV = 3;
|
|
wolffd@0
|
110
|
|
wolffd@0
|
111 %op = [repmat(DEL, 1, E) repmat(REV, 1, E) repmat(ADD, 1, Ebar)];
|
