Find circular routes using Hash Objects

Accepted Solution Solved
Reply
Occasional Contributor
Posts: 16
Accepted Solution

Find circular routes using Hash Objects

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


Accepted Solutions
Solution
‎01-19-2015 06:04 AM
Super User
Posts: 9,878

Re: Find 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

View solution in original post


All Replies
Super User
Posts: 9,878

Re: Find circular routes using Hash Objects

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

Occasional Contributor
Posts: 16

Re: Find circular routes using Hash Objects

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

Solution
‎01-19-2015 06:04 AM
Super User
Posts: 9,878

Re: Find 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

Occasional Contributor
Posts: 16

Re: Find circular routes using Hash Objects

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

Occasional Contributor
Posts: 16

Re: Find circular routes using Hash Objects

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!

Super User
Posts: 9,878

Re: Find circular routes using Hash Objects

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

Occasional Contributor
Posts: 16

Re: Find circular routes using Hash Objects

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

Super User
Posts: 9,878

Re: Find circular routes using Hash Objects

"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

Occasional Contributor
Posts: 16

Re: Find circular routes using Hash Objects

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


Super User
Posts: 9,878

Re: Find circular routes using Hash Objects

"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

Occasional Contributor
Posts: 16

Re: Find circular routes using Hash Objects

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

Super User
Posts: 9,878

Re: Find circular routes using Hash Objects

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

Occasional Contributor
Posts: 16

Re: Find circular routes using Hash Objects

You are simply rocking friend.

Thank you so much.

Deep

Occasional Contributor
Posts: 16

Re: Find circular routes using Hash Objects

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

🔒 This topic is solved and locked.

Need further help from the community? Please ask a new question.

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