Search a tree - using Broad Search First algorithm

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&colon;'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&colon;'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

PGStats · ‎10-08-2014

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

Ksharp · ‎10-09-2014

PG,

Thanks. I hope I could do it better .

Xia Keshan

From China

Ksharp · ‎07-06-2015

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