comparison toolboxes/FullBNT-1.0.7/graph/pred2path.m @ 0:e9a9cd732c1e tip

first hg version after svn

+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
+