topic Re: Find circular routes using Hash Objects in SAS Programming

Find circular routes using Hash Objects

DeepH — Mon, 19 Jan 2015 08:41:26 GMT

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

Re: Find circular routes using Hash Objects

Ksharp — Mon, 19 Jan 2015 09:21:49 GMT

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

Re: Find circular routes using Hash Objects

DeepH — Mon, 19 Jan 2015 10:24:25 GMT

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

Re: Find circular routes using Hash Objects

KachiM — Mon, 19 Jan 2015 10:43:49 GMT

DeepH,

I have heard about recursive lookups (chained relationship) but not circular routes.

For id = 2, can you explain how you get i->j->i.

Re: Find circular routes using Hash Objects

DeepH — Mon, 19 Jan 2015 10:57:11 GMT

Hi datasp,

Actually I have made a minor change in my input data, which now looks as:

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

;

So now for ID = 2 you can see i -> j -> i.

Circular route is what I want to accomplish, and recursive lookup might be a way to achieve it.

Can you pls share further details about it?

Re: Find circular routes using Hash Objects

Ksharp — Mon, 19 Jan 2015 11:04:39 GMT

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

Re: Find circular routes using Hash Objects

KachiM — Mon, 19 Jan 2015 11:14:42 GMT

Hi DeepH,

For ID = 2, the recursive lookup works the way you want but not for ID = 1.

In the former, you take From_City as KEY Part and get To_City as Data Part. Again take To_City(i) as KEY Part and get J as Data Part. And finally take J as Key Part and get I as the Data Part.

In the latter, you will get a->b->c->e->f

Re: Find circular routes using Hash Objects

DeepH — Mon, 19 Jan 2015 12:05:33 GMT

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

Re: Find circular routes using Hash Objects

DeepH — Tue, 20 Jan 2015 06:12:18 GMT

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!

Re: Find circular routes using Hash Objects

Ksharp — Tue, 20 Jan 2015 06:43:21 GMT

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

Re: Find circular routes using Hash Objects

DeepH — Fri, 23 Jan 2015 06:14:35 GMT

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

Re: Find circular routes using Hash Objects

Ksharp — Fri, 23 Jan 2015 06:38:09 GMT

"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

Re: Find circular routes using Hash Objects

Ksharp — Fri, 23 Jan 2015 06:39:41 GMT

If your table was huge, I really suggest you to split them into lots of small tables according to ID , That would be a better choice .

Re: Find circular routes using Hash Objects

DeepH — Fri, 23 Jan 2015 07:41:56 GMT

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

Re: Find circular routes using Hash Objects

Ksharp — Fri, 23 Jan 2015 08:14:32 GMT

"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

Re: Find circular routes using Hash Objects

DeepH — Fri, 23 Jan 2015 08:23:30 GMT

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

Re: Find circular routes using Hash Objects

Ksharp — Fri, 23 Jan 2015 08:25:14 GMT

"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."

No, You can't. how you make sure there is no circular , if only searching the first 8 nodes .

Re: Find circular routes using Hash Objects

DeepH — Fri, 23 Jan 2015 08:33:20 GMT

Yes, agree that there is no surity regarding circular route, by only searching first 8 nodes.

But I have to have some control on the output.

Just to give you an example is said 8, else one should be able to define upto how many nodes he want to check for the circular route.

If one defines it 20, the code should be able to check it for 20 nodes.

Deep

Re: Find circular routes using Hash Objects

Ksharp — Fri, 23 Jan 2015 08:36:46 GMT

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

Re: Find circular routes using Hash Objects

DeepH — Fri, 23 Jan 2015 08:47:56 GMT

You are simply rocking friend.

Thank you so much.

Deep