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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
function rte = pred2path(P,s,t)
%PRED2PATH Convert predecessor indices to shortest paths from node 's' to 't'.
% rte = pred2path(P,s,t)
% P = |s| x n matrix of predecessor indices (from DIJK)
% s = FROM node indices
% = [] (default), paths from all nodes
% t = TO node indices
% = [] (default), paths to all nodes
% rte = |s| x |t| cell array of paths (or routes) from 's' to 't', where
% rte{i,j} = path from s(i) to t(j)
% = [], if no path exists from s(i) to t(j)
%
% (Used with output of DIJK)
% Copyright (c) 1998-2001 by Michael G. Kay
% Matlog Version 5 22-Aug-2001
% Input Error Checking ******************************************************
error(nargchk(1,3,nargin));
[rP,n] = size(P);
if nargin < 2 | isempty(s), s = (1:n)'; else s = s(:); end
if nargin < 3 | isempty(t), t = (1:n)'; else t = t(:); end
if any(P < 0 | P > n)
error(['Elements of P must be integers between 1 and ',num2str(n)]);
elseif any(s < 1 | s > n)
error(['''s'' must be an integer between 1 and ',num2str(n)]);
elseif any(t < 1 | t > n)
error(['''t'' must be an integer between 1 and ',num2str(n)]);
end
% End (Input Error Checking) ************************************************
rte = cell(length(s),length(t));
for i = 1:length(s)
if rP == 1
si = 1;
else
si = s(i);
if si < 1 | si > rP
error('Invalid P matrix.')
end
end
for j = 1:length(t)
tj = t(j);
if tj == s(i)
r = tj;
elseif P(si,tj) == 0
r = [];
else
r = tj;
while tj ~= s(i)
if tj < 1 | tj > n
error('Invalid element of P matrix found.')
end
r = [P(si,tj) r];
tj = P(si,tj);
end
end
rte{i,j} = r;
end
end
if length(s) == 1 & length(t) == 1
rte = rte{:};
end
%rte = t;
while 0%t ~= s
if t < 1 | t > n | round(t) ~= t
error('Invalid ''pred'' element found prior to reaching ''s''');
end
rte = [P(t) rte];
t = P(t);
end
|
