BookmarkSubscribeRSS Feed
🔒 This topic is solved and locked. Need further help from the community? Please sign in and ask a new question.
DeepH
Calcite | Level 5

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

1 ACCEPTED SOLUTION

Accepted Solutions
Ksharp
Super User

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

View solution in original post

28 REPLIES 28
Ksharp
Super User

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

DeepH
Calcite | Level 5

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

Ksharp
Super User

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

DeepH
Calcite | Level 5

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

DeepH
Calcite | Level 5

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!

Ksharp
Super User

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

DeepH
Calcite | Level 5

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

Ksharp
Super User

"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

DeepH
Calcite | Level 5

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


Ksharp
Super User

"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

DeepH
Calcite | Level 5

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

Ksharp
Super User

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

DeepH
Calcite | Level 5

You are simply rocking friend.

Thank you so much.

Deep

DeepH
Calcite | Level 5

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

sas-innovate-2024.png

Join us for SAS Innovate April 16-19 at the Aria in Las Vegas. Bring the team and save big with our group pricing for a limited time only.

Pre-conference courses and tutorials are filling up fast and are always a sellout. Register today to reserve your seat.

 

Register now!

How to Concatenate Values

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.

Click image to register for webinarClick image to register for webinar

Classroom Training Available!

Select SAS Training centers are offering in-person courses. View upcoming courses for:

View all other training opportunities.

Discussion stats
  • 28 replies
  • 1635 views
  • 3 likes
  • 3 in conversation