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;
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
I would trust @Ksharp to come up with an excellent hash-based solution for this.
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;
@Ksharp, very cool! 🙂
Build your skills. Make connections. Enjoy creative freedom. Maybe change the world. Registration is now open through August 30th. Visit the SAS Hackathon homepage.
Register today!Need to connect to databases in SAS Viya? SAS’ David Ghan shows you two methods – via SAS/ACCESS LIBNAME and SAS Data Connector SASLIBS – in this video.
Find more tutorials on the SAS Users YouTube channel.