-
Notifications
You must be signed in to change notification settings - Fork 4
/
ucs_geodesic_tau.m
53 lines (40 loc) · 1.04 KB
/
ucs_geodesic_tau.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
function [nlist, dlist] = ucs_geodesic_tau(W,node,tau)
% Algorithm 1 (Uniform Cost Search) of the paper
% Calculate the information neighbourhood of information radius tau
% W: upper bound of the information distance matrix
% node: node index of the center of the information neighbourhood
% tau: information radius
if tau==0
nlist=node;
dlist=0;
return;
end
n = size(W,1);
openset = PriorityQueue(n);
nlist=NaN(1,1000);
dlist=NaN(1,1000);
push(openset, node, 10^-12);
m=1;
gcurrent=0;
while gcurrent<=tau && ~isEmpty(openset)
[u,gu] = pop(openset);
W(:,u)=0;
[~,neighor,nb_distance]=find(W(u,:));
push(openset, neighor, gu + nb_distance);
if size(nlist,2)<m
nlist=[nlist NaN(1,1000)];
dlist=[dlist NaN(1,1000)];
end
nlist(m)=u;
dlist(m)=gu;
gcurrent=gu;
m=m+1;
end
if gcurrent>tau
nlist=nlist(1,1:m-2);
dlist=dlist(1,1:m-2);
else
nlist=nlist(1,1:m-1);
dlist=dlist(1,1:m-1);
end
end