Search a tree - using Broad Search First algorithm
- Article History
- RSS Feed
- Mark as New
- Mark as Read
- Bookmark
- Subscribe
- Printer Friendly Page
- Report Inappropriate Content
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)
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;
WHERE (_start is not null) and (_end is not null);
FOUND:D365123 is a circle component.
path=D967236 D646720 D378691 D365123 _end=D365123
FOUND:D365123 is a circle component.
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.
FOUND:D365123 is a circle component.
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)
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
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);
FOUND:D365123 is a circle component.
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.
FOUND:D365123 is a circle component.
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
- Mark as Read
- Mark as New
- Bookmark
- Permalink
- Report Inappropriate Content
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
- Mark as Read
- Mark as New
- Bookmark
- Permalink
- Report Inappropriate Content
PG,
Thanks. I hope I could do it better .
Xia Keshan
From China
- Mark as Read
- Mark as New
- Bookmark
- Permalink
- Report Inappropriate Content
Sorry. I should use FINDW() ,not FIND(), which could generate ERROR result .Fix it .