|
wolffd@0
|
1 function rte = pred2path(P,s,t)
|
|
wolffd@0
|
2 %PRED2PATH Convert predecessor indices to shortest paths from node 's' to 't'.
|
|
wolffd@0
|
3 % rte = pred2path(P,s,t)
|
|
wolffd@0
|
4 % P = |s| x n matrix of predecessor indices (from DIJK)
|
|
wolffd@0
|
5 % s = FROM node indices
|
|
wolffd@0
|
6 % = [] (default), paths from all nodes
|
|
wolffd@0
|
7 % t = TO node indices
|
|
wolffd@0
|
8 % = [] (default), paths to all nodes
|
|
wolffd@0
|
9 % rte = |s| x |t| cell array of paths (or routes) from 's' to 't', where
|
|
wolffd@0
|
10 % rte{i,j} = path from s(i) to t(j)
|
|
wolffd@0
|
11 % = [], if no path exists from s(i) to t(j)
|
|
wolffd@0
|
12 %
|
|
wolffd@0
|
13 % (Used with output of DIJK)
|
|
wolffd@0
|
14
|
|
wolffd@0
|
15 % Copyright (c) 1998-2001 by Michael G. Kay
|
|
wolffd@0
|
16 % Matlog Version 5 22-Aug-2001
|
|
wolffd@0
|
17
|
|
wolffd@0
|
18 % Input Error Checking ******************************************************
|
|
wolffd@0
|
19 error(nargchk(1,3,nargin));
|
|
wolffd@0
|
20
|
|
wolffd@0
|
21 [rP,n] = size(P);
|
|
wolffd@0
|
22
|
|
wolffd@0
|
23 if nargin < 2 | isempty(s), s = (1:n)'; else s = s(:); end
|
|
wolffd@0
|
24 if nargin < 3 | isempty(t), t = (1:n)'; else t = t(:); end
|
|
wolffd@0
|
25
|
|
wolffd@0
|
26 if any(P < 0 | P > n)
|
|
wolffd@0
|
27 error(['Elements of P must be integers between 1 and ',num2str(n)]);
|
|
wolffd@0
|
28 elseif any(s < 1 | s > n)
|
|
wolffd@0
|
29 error(['''s'' must be an integer between 1 and ',num2str(n)]);
|
|
wolffd@0
|
30 elseif any(t < 1 | t > n)
|
|
wolffd@0
|
31 error(['''t'' must be an integer between 1 and ',num2str(n)]);
|
|
wolffd@0
|
32 end
|
|
wolffd@0
|
33 % End (Input Error Checking) ************************************************
|
|
wolffd@0
|
34
|
|
wolffd@0
|
35 rte = cell(length(s),length(t));
|
|
wolffd@0
|
36
|
|
wolffd@0
|
37 for i = 1:length(s)
|
|
wolffd@0
|
38 if rP == 1
|
|
wolffd@0
|
39 si = 1;
|
|
wolffd@0
|
40 else
|
|
wolffd@0
|
41 si = s(i);
|
|
wolffd@0
|
42 if si < 1 | si > rP
|
|
wolffd@0
|
43 error('Invalid P matrix.')
|
|
wolffd@0
|
44 end
|
|
wolffd@0
|
45 end
|
|
wolffd@0
|
46 for j = 1:length(t)
|
|
wolffd@0
|
47 tj = t(j);
|
|
wolffd@0
|
48 if tj == s(i)
|
|
wolffd@0
|
49 r = tj;
|
|
wolffd@0
|
50 elseif P(si,tj) == 0
|
|
wolffd@0
|
51 r = [];
|
|
wolffd@0
|
52 else
|
|
wolffd@0
|
53 r = tj;
|
|
wolffd@0
|
54 while tj ~= s(i)
|
|
wolffd@0
|
55 if tj < 1 | tj > n
|
|
wolffd@0
|
56 error('Invalid element of P matrix found.')
|
|
wolffd@0
|
57 end
|
|
wolffd@0
|
58 r = [P(si,tj) r];
|
|
wolffd@0
|
59 tj = P(si,tj);
|
|
wolffd@0
|
60 end
|
|
wolffd@0
|
61 end
|
|
wolffd@0
|
62 rte{i,j} = r;
|
|
wolffd@0
|
63 end
|
|
wolffd@0
|
64 end
|
|
wolffd@0
|
65
|
|
wolffd@0
|
66 if length(s) == 1 & length(t) == 1
|
|
wolffd@0
|
67 rte = rte{:};
|
|
wolffd@0
|
68 end
|
|
wolffd@0
|
69
|
|
wolffd@0
|
70 %rte = t;
|
|
wolffd@0
|
71 while 0%t ~= s
|
|
wolffd@0
|
72 if t < 1 | t > n | round(t) ~= t
|
|
wolffd@0
|
73 error('Invalid ''pred'' element found prior to reaching ''s''');
|
|
wolffd@0
|
74 end
|
|
wolffd@0
|
75 rte = [P(t) rte];
|
|
wolffd@0
|
76 t = P(t);
|
|
wolffd@0
|
77 end
|
|
wolffd@0
|
78
|
