## Search a tree - using Broad Search First algorithm

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

# 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);

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);

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);

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);

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

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 .

Version history
Last update:
‎10-05-2015 03:42 PM
Updated by:
Contributors
Article Labels
Article Tags