BookmarkSubscribeRSS Feed

Search a tree - using Broad Search First algorithm

Started ‎09-02-2014 by
Modified ‎10-05-2015 by
Views 1,635

The following code is to find circle components :

 

 

Code: Program

data have;
array x{0:3} $  _temporary_ ('A' 'B' 'C' 'D');
length _start _end $ 8;
call streaminit(1234);
do i=1 to 1000000;
  _start=cats(x{mod(i,4)},ceil(1000000*rand('uniform')));
  _end=cats(x{mod(i,4)},ceil(1000000*rand('uniform')));
  output;
end;
drop i;
run;

options compress=yes;
data _null_;
if _n_ eq 1 then do;
length path _path  $ 100 ;
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(where=(_start is not missing and _end is not missing));
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();
do while(rc=0);
  if not findw(path,strip(_end)) then do;
   if length(path)+length(_end)+1 gt lengthc(path) then do; put path= _end=;
   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 do;put path= _end=;putlog 'FOUND:' _end 'is a circle component.';end;
  rc=ha.find_next();
end;
end;
pa.clear();
run;

 

 


Log: Program

Notes (5)

1 OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;

 

53 

54 data have;

55 array x{0:3} $ _temporary_ ('A' 'B' 'C' 'D');

56 length _start _end $ 8;

57 call streaminit(1234);

58 do i=1 to 1000000;

59 _start=cats(x{mod(i,4)},ceil(1000000*rand('uniform')));

60 _end=cats(x{mod(i,4)},ceil(1000000*rand('uniform')));

61 output;

62 end;

63 drop i;

64 run;

NOTE: The data set WORK.HAVE has 1000000 observations and 2 variables.

NOTE: DATA statement used (Total process time):

  real time 0.66 seconds

  cpu time 0.56 seconds

  

65 

66 options compress=yes;

67 data _null_;

68 if _n_ eq 1 then do;

69 length path _path $ 100 ;

70 if 0 then set have;

71 declare hash ha(hashexp:20,dataset:'have(where=(_start is not missing and _end is not missing))',multidata:'y');

72 ha.definekey('_start');

73 ha.definedata('_end');

75 declare hash pa(ordered:'y');

76 declare hiter hi_path('pa');

77 pa.definekey('n');

78 pa.definedata('n','path');

79 pa.definedone();

80 end;

81 set have(where=(_start is not missing and _end is not missing));

82 count=1;n=1;_n=1;

83 path=catx(' ',_start,_end);

84 pa.add();

85 do while(hi_path.next()=0);

86 if n ne 1 then pa.remove(key:_n);_n=n;

87 _path=path;

88 _start=scan(path,-1,' ');

89 rc=ha.find();

90 do while(rc=0);

91 if not findw(path,strip(_end)) then do;

92 if length(path)+length(_end)+1 gt lengthc(path) then do; put path= _end=;

93 putlog 'ERROR: The length of path and _path are set too short';

95 end;

96 count+1;n=count;

97 path=catx(' ',path,_end);

98 pa.add();

99 path=_path;

100 end;

101 else do;put path= _end=;putlog 'FOUND:' _end 'is a circle component.';end;

102 rc=ha.find_next();

103 end;

104 end;

105 pa.clear();

106 run;

 

NOTE: There were 1000000 observations read from the data set WORK.HAVE.

 

  WHERE (_start is not null) and (_end is not null);

 

path=D712556 D646720 D378691 D365123 _end=D365123

 

FOUND:D365123 is a circle component.

path=D967236 D646720 D378691 D365123 _end=D365123

FOUND:D365123 is a circle component.

 

path=D365123 D365123 _end=D365123

 

FOUND:D365123 is a circle component.

path=D646720 D378691 D365123 _end=D365123

FOUND:D365123 is a circle component.

path=A459972 A459972 _end=A459972

FOUND:A459972 is a circle component.

 

path=D378691 D365123 _end=D365123

 

FOUND:D365123 is a circle component.

 

NOTE: DATA statement used (Total process time):

 

  real time 9.62 seconds

  cpu time 9.11 seconds

  

NOTE: There were 1000000 observations read from the data set WORK.HAVE.

  WHERE (_start is not null) and (_end is not null);

107 

108 

109 OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;

119 

 

 

 

 

The following code is to get all the path.

 

 

 

 

Code: Program

data have;
array x{0:3} $  _temporary_ ('A' 'B' 'C' 'D');
length _start _end $ 8;
call streaminit(1234);
do i=1 to 1000000;
  _start=cats(x{mod(i,4)},ceil(1000000*rand('uniform')));
  _end=cats(x{mod(i,4)},ceil(1000000*rand('uniform')));
  output;
end;
drop i;
run;


options compress=yes;
data want(keep=path);
if _n_ eq 1 then do;
length path _path  $ 100 ;

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(where=(_start is not missing and _end is not missing));
count=1;n=1;_n=1;
path=catx(' ',_start,_end);
pa.add();output;
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();
do while(rc=0);
  if not findw(path,strip(_end)) then do;

   if length(path)+length(_end)+1 gt lengthc(path) then do; put path= _end=;
   putlog 'ERROR: The length of path and _path are set too short';
   stop;
   end;
   count+1;n=count;
   path=catx(' ',path,_end);
   pa.add(); output;
   path=_path;
   end;
   else do;put path= _end=;putlog 'FOUND:' _end 'is a circle component.';end;
  rc=ha.find_next();
end;
end;
pa.clear();
run;

 

 


Log: Program

Notes (8)

1 OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;

 

53 

54 data have;

55 array x{0:3} $ _temporary_ ('A' 'B' 'C' 'D');

56 length _start _end $ 8;

57 call streaminit(1234);

58 do i=1 to 1000000;

59 _start=cats(x{mod(i,4)},ceil(1000000*rand('uniform')));

60 _end=cats(x{mod(i,4)},ceil(1000000*rand('uniform')));

61 output;

62 end;

63 drop i;

64 run;

NOTE: Compression was disabled for data set WORK.HAVE because compression overhead would increase the size of the data set.

NOTE: The data set WORK.HAVE has 1000000 observations and 2 variables.

NOTE: DATA statement used (Total process time):

  real time 1.06 seconds

 

  cpu time 0.64 seconds

 

  

65 

66 

67 options compress=yes;

68 data want(keep=path);

69 if _n_ eq 1 then do;

70 length path _path $ 100 ;

71 

72 if 0 then set have;

73 declare hash ha(hashexp:20,dataset:'have(where=(_start is not missing and _end is not missing))',multidata:'y');

74 ha.definekey('_start');

75 ha.definedata('_end');

76 ha.definedone();

77 

78 declare hash pa(ordered:'y');

79 declare hiter hi_path('pa');

80 pa.definekey('n');

81 pa.definedata('n','path');

82 pa.definedone();

83 

84 end;

85 

86 set have(where=(_start is not missing and _end is not missing));

87 count=1;n=1;_n=1;

88 path=catx(' ',_start,_end);

89 pa.add();output;

90 do while(hi_path.next()=0);

91 

92 if n ne 1 then pa.remove(key:_n);_n=n;

93 

94 _path=path;

95 _start=scan(path,-1,' ');

96 rc=ha.find();

97 do while(rc=0);

98 if not findw(path,strip(_end)) then do;

99 

100 if length(path)+length(_end)+1 gt lengthc(path) then do; put path= _end=;

101 putlog 'ERROR: The length of path and _path are set too short';

102 stop;

103 end;

104 count+1;n=count;

105 path=catx(' ',path,_end);

106 pa.add(); output;

107 path=_path;

108 end;

109 else do;put path= _end=;putlog 'FOUND:' _end 'is a circle component.';end;

110 rc=ha.find_next();

111 end;

112 end;

113 pa.clear();

114 run;

NOTE: There were 1000000 observations read from the data set WORK.HAVE.

  WHERE (_start is not null) and (_end is not null);

 

path=D712556 D646720 D378691 D365123 _end=D365123

 

FOUND:D365123 is a circle component.

 

path=D967236 D646720 D378691 D365123 _end=D365123

 

FOUND:D365123 is a circle component.

path=D365123 D365123 _end=D365123

FOUND:D365123 is a circle component.

path=D646720 D378691 D365123 _end=D365123

FOUND:D365123 is a circle component.

path=A459972 A459972 _end=A459972

FOUND:A459972 is a circle component.

 

path=D378691 D365123 _end=D365123

 

FOUND:D365123 is a circle component.

 

NOTE: DATA statement used (Total process time):

 

  real time 7.74 seconds

  cpu time 7.57 seconds

  

NOTE: There were 1000000 observations read from the data set WORK.HAVE.

  WHERE (_start is not null) and (_end is not null);

NOTE: The data set WORK.WANT has 1330711 observations and 1 variables.

NOTE: Compressing data set WORK.WANT decreased size by 55.63 percent.

  Compressed is 903 pages; un-compressed would require 2035 pages.

115 

116 OPTIONS NONOTES NOSTIMER NOSOURCE NOSYNTAXCHECK;

126 

 

 

Xia Keshan

Comments

Thanks for a great alternative for those who don't have access to PROC OPTNET (CYCLE statement) or PROC OPTMODEL (SOLVE WITH NETWORK / CYCLE statement), both available under the SAS/OR licence. - PG

PG,

Thanks. I hope I could do it better .

Xia Keshan

From China

Sorry. I should use FINDW() ,not FIND(), which could generate ERROR result .Fix it .Smiley Sad

Version history
Last update:
‎10-05-2015 03:42 PM
Updated by:

SAS INNOVATE 2024

Innovate_SAS_Blue.png

Registration is open! SAS is returning to Vegas for an AI and analytics experience like no other! Whether you're an executive, manager, end user or SAS partner, SAS Innovate is designed for everyone on your team. Register for just $495 by 12/31/2023.

If you are interested in speaking, there is still time to submit a session idea. More details are posted on the website. 

Register now!

Free course: Data Literacy Essentials

Data Literacy is for all, even absolute beginners. Jump on board with this free e-learning  and boost your career prospects.

Get Started

Article Labels
Article Tags