/*
The ALLPATHS macro finds all paths between two nodes in a directed network. The
network is described by a list of arcs (from-to node pairs). Nodes can be identified
by numeric or character values. Node pairs for which paths are requested are listed
in a dataset (start-end node pairs).
The macro creates a dataset describing all possible paths for each node pair requested.
Syntax
%macro allPaths(Network, Pairs, Paths, maxPathLength=100);
Input/Output datasets (variables) are:
Input Network (from, to)
Input Pairs (start, end)
Output Paths (start, end, pathNo, nodeOrder, from, to)
The ALLPATHS macro has one optional parameter:
maxPathLength gives the maximum path length (number of arcs) to search for.
Default=100.
IMPORTANT : Prior to calling the macro, Network dataset must be sorted and indexed
by from nodes. For example :
proc sort data=myNetwork out=myNetwork(index=(from));
where from ne to;
by from to;
run;
IMPORTANT : Node variables from, to, start, and end should be of the same
type and length.
PG
*/
%macro allPaths(network, pairs, paths, maxPathLength=100);
%let nodeIDlength=8;
%let which=whichn;
data _null_;
set &network;
if vtype(from) = "C" then do;
call symputx("nodeIDlength", cats("$",vlength(from)));
call symputx("which", "whichc");
end;
stop;
run;
data &paths(keep=start end pathNo nodeOrder from to);
set &pairs;
array arc[&maxPathLength];
array node[0:&maxPathLength] &nodeIDlength;
pathNo = 0;
len = 0;
node[len] = start;
do k = 1 to 10000; /* Catch infinite loop, just in case */
if missing(node[len]) then do; /* Move to sibling or back off*/
if len = 0 then leave;
p = arc[len] + 1;
if p > maxp then do; /* Last arc: no sibling. Back off */
len + (-1);
call missing(node[len]);
end;
else do;
set &network point=p nobs=maxp;
if from = node[len-1] then do; /* Sibling found */
node[len] = to;
arc[len] = p;
end;
else do; /* No more sibling. Back off */
len + (-1);
call missing(node[len]);
end;
end;
end;
else do; /* Go further down the path */
if node[len] = end then do; /* Simple path found */
pathNo + 1;
do j = 1 to len;
from = node[j-1]; to = node; nodeOrder=j; output;
end;
call missing(node[len]);
end;
else if &which(node[len], of node
- ) < len+1 then do; /* Cycle detected in path */
call missing(node[len]);
end;
else do; /* Move ahead in path */
from = node[len];
set &network key=from/unique curobs=p;
if p and len < dim(arc) then do; /* To node found, add it to path, if possible */
len + 1;
node[len] = to;
arc[len] = p;
end;
else do; /* No arc found or no room left on path. Dead end */
_error_ = 0;
call missing(node[len]);
end;
end;
end;
end;
if pathNo = 0 then do; /* No path found. Output missing values */
call missing(from, to, nodeOrder); output; end;
run;
%mend allPaths;
/*
* Example of use ;
* List the edges of a directed network. Must include variables FROM and TO
(see attached picture) ;
data network;
length from to $4;
input from to @@;
datalines;
a b b c c d d e e f f a
a c c e e a
f d d b b f
;
* IMPORTANT : Sort and index the network by FROM node ;
proc sort data=network out=network(index=(from)); where from ne to; by from to; run;
* List of node pairs for which we want to enumerate the paths.
Variables START and END must match the type of network variables FROM and TO ;
data requests;
length start end $4;
input start end;
label start="Starting Node" end="Ending Node";
datalines;
a a
a x
x a
a b
b f
f b
f .
. .
;
* Call the allPaths macro ;
%allPaths(network, requests, paths);
* Print the paths in a tabular format ;
data printNet;
length Path $200;
do until(last.pathNo);
set paths; by start end pathNo notsorted;
if first.pathNo then path = cats(from);
path = catx(" - ", path, to);
end;
if pathNo = 0 then path = "No path";
keep start end pathNo path;
label pathNo="Path No";
run;
title "List of all paths";
proc print data=printNet noobs label;
by start end notsorted; id start end; run;
*/
/*
* Example of use (with numeric nodes) ;
* List the edges of a directed network. Must include variables FROM and TO ;
data network;
length from to 8;
input from to @@;
datalines;
1 2 2 3 3 4 4 5 5 6 6 1
1 3 3 5 5 1
6 4 4 2 2 6
;
* IMPORTANT : Sort and index the network by FROM node ;
proc sort data=network out=network(index=(from)); by from to; run;
* List of node pairs for which we want to enumerate the paths.
Variables START and END must match the type of network variables FROM and TO ;
data requests;
length start end 8;
input start end;
label start="Starting Node" end="Ending Node";
datalines;
1 1
1 9
9 1
1 2
2 6
6 2
6 .
. .
;
* Call the allPaths macro ;
%allPaths(network, requests, paths);
* Print the paths in a tabular format ;
data printNet;
length Path $200;
do until(last.pathNo);
set paths; by start end pathNo notsorted;
if first.pathNo then path = cats(from);
path = catx(" - ", path, to);
end;
keep start end pathNo path;
label pathNo="Path No";
run;
title "List of all paths";
proc print data=printNet noobs label;
by start end notsorted; id start end; run;
*/
PG
