We’re smarter together. Learn from this collection of community knowledge and add your expertise.

Search a tree - using Broad Search First algorithm

by Super User on ‎09-02-2014 10:50 AM - edited on ‎10-05-2015 03:42 PM by Community Manager (706 Views)

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
by Respected Advisor
on ‎10-08-2014 10:48 AM

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

by Super User
on ‎10-09-2014 07:55 AM

PG,

Thanks. I hope I could do it better .

Xia Keshan

From China

by Super User
on ‎07-06-2015 11:15 PM

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

Your turn
Sign In!

Want to write an article? Sign in with your profile.