Hi,
I have the data as following;
ID From_City To_City
1 a b
1 b c
1 c e
1 b a
1 e f
2 h i
2 i j
2 j k
So for ID = 1 there is a circular route from a -> b -> a and for ID = 2 there is also a circular route from i -> j -> i
How can I identify such circular routes using Hash Objects!!
So you want the first one is exactly the same with the last one ?
data have; input (id From_City To_City) ($) @@; cards; 1 a b 1 b c 1 c e 1 b a 1 e f 2 h i 2 i j 2 j i ; run; data _null_; if _n_ eq 1 then do; length path _path $ 400 ; if 0 then set have; declare hash ha(hashexp:20,dataset:'have(where=(From_City is not missing and To_City is not missing))',multidata:'Y'); ha.definekey('id','From_City'); ha.definedata('To_City'); ha.definedone(); declare hash pa(ordered:'Y'); declare hiter hi_path('pa'); pa.definekey('count'); pa.definedata('path'); pa.definedone(); end; set have; count=1; path=catx(' ',From_City,To_City); pa.add(); do while(hi_path.next()=0); _path=path; From_City=scan(path,-1,' '); rc=ha.find(); do while(rc=0); if not find(path,strip(To_City)) then do; count+1; path=catx(' ',path,To_City); pa.add(); path=_path; end; else if scan(path,1,' ')=To_City then putlog 'FOUND:' path To_City 'is a circle component.'; rc=ha.find_next(); end; end; pa.clear(); run;
Xia Keshan
Hi, check the code I wrote about it before .
https://communities.sas.com/docs/DOC-7756
data have; input (id From_City To_City) ($) @@; cards; 1 a b 1 b c 1 c e 1 b a 1 e f 2 h i 2 i j 2 j k ; run; data _null_; if _n_ eq 1 then do; length path _path $ 400 ; if 0 then set have; declare hash ha(hashexp:20,dataset:'have(where=(From_City is not missing and To_City is not missing))',multidata:'Y'); ha.definekey('id','From_City'); ha.definedata('To_City'); ha.definedone(); declare hash pa(ordered:'Y'); declare hiter hi_path('pa'); pa.definekey('count'); pa.definedata('path'); pa.definedone(); end; set have; count=1; path=catx(' ',From_City,To_City); pa.add(); do while(hi_path.next()=0); _path=path; From_City=scan(path,-1,' '); rc=ha.find(); do while(rc=0); if not find(path,strip(To_City)) then do; count+1; path=catx(' ',path,To_City); pa.add(); path=_path; end; else putlog 'FOUND:' path To_City 'is a circle component.'; rc=ha.find_next(); end; end; pa.clear(); run;
Xia Keshan
Message was edited by: xia keshan
Hi Xia,
Many thanks for the help.
This is what exactly I wanted.
Now, just a small tweek need to be fixed.
When running the code for:
data have;
input (id From_City To_City) ($) @@;
cards;
1 a b
1 b c
1 c e
1 b a
1 e f
2 h i
2 i j
2 j i
;
I am getting "FOUND: h i j i is a circle component", which is not correct in fact.
How can we fix that??
So you want the first one is exactly the same with the last one ?
data have; input (id From_City To_City) ($) @@; cards; 1 a b 1 b c 1 c e 1 b a 1 e f 2 h i 2 i j 2 j i ; run; data _null_; if _n_ eq 1 then do; length path _path $ 400 ; if 0 then set have; declare hash ha(hashexp:20,dataset:'have(where=(From_City is not missing and To_City is not missing))',multidata:'Y'); ha.definekey('id','From_City'); ha.definedata('To_City'); ha.definedone(); declare hash pa(ordered:'Y'); declare hiter hi_path('pa'); pa.definekey('count'); pa.definedata('path'); pa.definedone(); end; set have; count=1; path=catx(' ',From_City,To_City); pa.add(); do while(hi_path.next()=0); _path=path; From_City=scan(path,-1,' '); rc=ha.find(); do while(rc=0); if not find(path,strip(To_City)) then do; count+1; path=catx(' ',path,To_City); pa.add(); path=_path; end; else if scan(path,1,' ')=To_City then putlog 'FOUND:' path To_City 'is a circle component.'; rc=ha.find_next(); end; end; pa.clear(); run;
Xia Keshan
Hi Xia,
Yes, the first one should exactly be same as the last one.
This is awesome. I got exactly what I want.
Thanks a lot.
Deep
Hi Xia,
Now if I want to save the final circular paths in a output dataset, what is the most probable way to do it!
OK. Open the dataset WANT.
data have; input (id From_City To_City) ($) @@; cards; 1 a b 1 b c 1 c e 1 b a 1 e f 2 h i 2 i j 2 j i ; run; data want(keep=loop); if _n_ eq 1 then do; length path _path loop $ 400 ; if 0 then set have; declare hash ha(hashexp:20,dataset:'have(where=(From_City is not missing and To_City is not missing))',multidata:'Y'); ha.definekey('id','From_City'); ha.definedata('To_City'); ha.definedone(); declare hash pa(ordered:'Y'); declare hiter hi_path('pa'); pa.definekey('count'); pa.definedata('path'); pa.definedone(); end; set have; count=1; path=catx(' ',From_City,To_City); pa.add(); do while(hi_path.next()=0); _path=path; From_City=scan(path,-1,' '); rc=ha.find(); do while(rc=0); if not find(path,strip(To_City)) then do; count+1; path=catx(' ',path,To_City); pa.add(); path=_path; end; else if scan(path,1,' ')=To_City then do;loop=catx(' ',path,To_City);output;end; rc=ha.find_next(); end; end; pa.clear(); run;
Xia Keshan
Hi Xia,
The input dataset that I am using is quiet huge.
Is there a way where I can restrict the number of iterations!
Lets say after 'X' number of iterations if no circular route is found, then the code moves to next observation and checks for the circular route.
If the circular route is found within less than 'X' iterations then it gives output, else it goes and scans the next observation.
Thanks,
Deep
"Lets say after 'X' number of iterations if no circular route is found, then the code moves to next observation and checks for the circular route."
'X' number of iterations . You mean the number of levels of deep ?
E.X. There is a branch which have four levels of deep.
A -> B -> C -> D
But you only want the first two levels , the next two levels will drop ?
Only need A->B ?
Xia Keshan
Hi Xia,
Lets say there is a circular route from A->B->C->D->E->F->G->H->I->J->K->A for a single ID.
Now out of total 12 nodes shown, there are 10 nodes in between start node and the end node.
But I want to restrict that, if there is no circular route found till 8 nodes i.e. A->B->C->D->E->F->G->H, then it should move to next observation and check for the circular route.
So my output data sets would be having only those circular routes which has less than or equal to 8 nodes.
Hope I made myself clear!
Thanks,
Deep
"But I want to restrict that, if there is no circular route found till 8 nodes i.e. A->B->C->D->E->F->G->H, then it should move to next observation and check for the circular route."
So what you say is what I say. if there is A->B->C->D->E->F->G->H ->A ,you will drop it ,even A is appeared at ninth position ?
BTW, Change length path _path loop $ 400 ; to be small value to save resource.
Xia Keshan
Yes,
If the circular route is found till the maximum of 8 nodes, then it will give in output else we will drop it.
Deep
OK. Got you.
data have; input (id From_City To_City) ($) @@; cards; 1 a b 1 b c 1 c d 1 d e 1 b a 1 e f 1 f g 1 g a 2 h i 2 i j 2 j i ; run; data want(keep=loop); if _n_ eq 1 then do; length path _path loop $ 400 ; if 0 then set have; declare hash ha(hashexp:20,dataset:'have(where=(From_City is not missing and To_City is not missing))',multidata:'Y'); ha.definekey('id','From_City'); ha.definedata('To_City'); ha.definedone(); declare hash pa(ordered:'Y'); declare hiter hi_path('pa'); pa.definekey('count'); pa.definedata('path'); pa.definedone(); end; set have; count=1; path=catx(' ',From_City,To_City); pa.add(); do while(hi_path.next()=0); _path=path; From_City=scan(path,-1,' '); rc=ha.find(); do while(rc=0); if not find(path,strip(To_City)) then do; count+1; path=catx(' ',path,To_City); if countw(path) lt 8 then pa.add(); path=_path; end; else if scan(path,1,' ')=To_City then do;loop=catx(' ',path,To_City);output;end; rc=ha.find_next(); end; end; pa.clear(); run;
Xia Keshan
You are simply rocking friend.
Thank you so much.
Deep
Hi Xia,
Is it possible to store the individual nodes of circular route found in to seperate columns!
E.G.
ID C1 C2 C3 C4 C5 C5 C7
--------------------------------------
1 A B C D E F A
Thanks,
Deep
Are you ready for the spotlight? We're accepting content ideas for SAS Innovate 2025 to be held May 6-9 in Orlando, FL. The call is open until September 25. Read more here about why you should contribute and what is in it for you!
Learn how use the CAT functions in SAS to join values from multiple variables into a single value.
Find more tutorials on the SAS Users YouTube channel.