topic Re: Trace all the paths from source id in SAS Data Management

Trace all the paths from source id

JoshuaHarris — Thu, 21 Mar 2019 19:57:01 GMT

I have a dataset which contains pid, cid. I want to get the list of all the possible paths of each pid.
Example data as below
Pid cid
1 2
2 3
2 5
3 6
4 8
8 9
9 4
My expected result is
1 2 3 6
1 2 5
2 3 6
2 5
3 6
4 8 9 .
8 9
9 4
If the path is about to loop then i want to blank out the value and stop it to avoid any infinite loopings.

Re: Trace all the paths from source id

JoshuaHarris — Thu, 21 Mar 2019 20:02:22 GMT

My expected result is
1 2 3 6
1 2 5
2 3 6
2 5
3 6
4 8 9 .
8 9 4
9 4

Re: Trace all the paths from source id

TomKari — Thu, 21 Mar 2019 20:09:46 GMT

The option I'm aware of is PROC OPTNET, which takes the heavy lifting out of the recursion. I'll be interested to see what other options people post.

Tom

Re: Trace all the paths from source id

JoshuaHarris — Fri, 22 Mar 2019 00:58:22 GMT

Thanks Tom!
But i don't have the SAS/OR. Hence this proc optnet is not available for
me. Would like to do this with other logics

Re: Trace all the paths from source id

PGStats — Fri, 22 Mar 2019 03:44:16 GMT

I would trust @Ksharp to come up with an excellent hash-based solution for this.

Re: Trace all the paths from source id

Ksharp — Fri, 22 Mar 2019 11:50:02 GMT

Here is. Thanks @PGStats

data have;
input _start $ _end $;
cards;
1 2
2 3
2 5
3 6
4 8
8 9
9 4
;
run;
 

data want(keep=path);
if _n_ eq 1 then do;
length path _path  $ 400 ;
if 0 then set have;
declare hash ha(hashexp:20,dataset:'have(where=(_start is not missing and _end is not missing))',multidata:'y');
ha.definekey('_start');
ha.definedata('_end');
ha.definedone();

declare hash pa(ordered:'y');
declare hiter hi_path('pa');
pa.definekey('n');
pa.definedata('n','path');
pa.definedone();

end;


set have;
count=1;n=1;_n=1;
path=catx('|',_start,_end);
   
pa.add();
do while(hi_path.next()=0);
 if n ne 1 then pa.remove(key:_n);_n=n;
 _path=path;  
 _start=scan(path,-1,'|');
 rc=ha.find();
 if rc ne 0 then output; /*It is the longest path*/
 do while(rc=0);
  if not findw(path,strip(_end),'|') then do;
   if length(path)+length(_end)+1 gt lengthc(path) then do;
    putlog 'ERROR: The length of path and _path are set too short';
    stop;
   end;
   
   count+1;n=count;
   path=catx('|',path,_end);
   pa.add();
   path=_path;
 end;
  else output; /*It is a circle*/
  rc=ha.find_next();
end;
end;
pa.clear();
run;


proc print;run;

Re: Trace all the paths from source id

JoshuaHarris — Fri, 22 Mar 2019 15:19:07 GMT

Awesome!!! Thanks @PGStats
Works like a charm.. Still am learning your code 🙂

Re: Trace all the paths from source id

PeterClemmensen — Fri, 22 Mar 2019 21:27:14 GMT

@Ksharp, very cool! 🙂

Re: Trace all the paths from source id

JoshuaHarris — Sat, 23 Mar 2019 03:03:39 GMT

@Ksharp awesome job.. Thanks.. It works cool 🙂