Now I write some comment to help you understand my code. And use the example this. http://en.wikipedia.org/wiki/Strongly_connected_component you posted .
data have;
input (_start _end) (:$1.) @@;
cards;
a b
b e b f b c
c d c g
d c d h
e a e f
f g
g f
h g h d
;
run;
data node(keep=node);
set have;
node=_start;output;
node=_end;output;
run;
*find all of unique node;
proc sort data=node nodupkey;by node;run;
data _null_;
if _n_ eq 1 then do;
length path _path component $ 100 map $ 8;
if 0 then set have;
*This Hash Table contains the from-to information;
declare hash ha(hashexp:20,dataset:'have',multidata:'Y');
ha.definekey('_start');
ha.definedata('_end');
ha.definedone();
*This Hash Table contains all of the from-to we can searched in a tree;
*i.e. a->b a->d b->a d->a ......... map'value like: 'a b' 'a d' ;
declare hash _map(hashexp:20);
_map.definekey('map');
_map.definedone();
*This Hash Table contains all of branches in a tree,it is very important;
*which we can find all of the from-to ;
declare hash pa(ordered:'Y');
declare hiter hi_path('pa');
pa.definekey('count');
pa.definedata('path');
pa.definedone();
*This Hash Table contains all of unique node ;
if 0 then set node;
declare hash _node(dataset:'node');
declare hiter hi_node('_node');
_node.definekey('node');
_node.definedata('node');
_node.definedone();
*This Hash Table contans final result we need;
*i.e. strongly connected components ;
declare hash want(ordered:'Y');
declare hiter hi_want('want');
want.definekey('group');
want.definedata('group','component');
want.definedone();
end;
set have end=last;
*initial Hash Table PA, i.e. get the first branch;
count=1;
path=catx(' ',_start,_end);
pa.add();
*Now get start,using BSF to get all of from-to;
do while(hi_path.next()=0);
*find a from-to and push it into Hash Table MAP;
map=catx(' ',scan(path,1,' '),scan(path,-1,' '));
_map.replace();
_path=path;
_start=scan(path,-1,' ');
rc=ha.find();
do while(rc=0);
if not find(path,strip(_end)) then do;
count+1;
path=catx(' ',path,_end);
pa.add();
path=_path;
end;
rc=ha.find_next();
end;
end;
*Now a branch has searched completely,we need to clear it to ;
*prepare for next branch (an observation is a branch);
pa.clear();
*Now At this time, we have gotten all of the from-to we can searched ;
*Starting to find strongly connected components ;
if last then do;
do while(hi_node.next()=0);
n+1;
if n=1 then do; *initial Hash Table WANT;
group+1; component=node; want.add();
end;
else do;
rc=hi_want.first();
do while(rc=0);
no=0;
do k=1 to countw(component);
*check whether there is a path from a to b;
map=catx(' ',scan(component,k),node);
if _map.check() ne 0 then no=1;
*check whether there is a path from b to a;
map=catx(' ',node,scan(component,k));
if _map.check() ne 0 then no=1;
end;
*if this node is belonged to this component, ;
*then merge it into the component;
if not no then do;
component=catx(' ',component,node);
want.replace();
leave;
end;
rc=hi_want.next();
end;
*if this node is not belonged to all of components;
*then this node is a independent component;
*we add it at the bottom of Hash Table WANT;
if no then do;
group+1; component=node; want.add();
end;
end;
end;
*At this time, we get all the components ,then output it.;
want.output(dataset:'want');
end;
run;
Ksharp
... View more
