Strongly connected component in oriented graph.Procedures(tools) on SAS?

[AmitKB]

Hi Ksharp,

                 Thanks for your help. I have a few questions:

1> Which algorithm did you use. Is it Tarjan?

2> The final result gives the components. Is that what your program does?

Is it possible for you to comment the program so i can follow each step.

Regards,

Amit

[Ksharp]

Actually my code is very raw. I need some more example to rectify it. Maybe I need some more GRAPH theory knowledge.

I used Broad First Search algorithm to find a LOOP path .

The dataset WANT contains all the LOOP path. You can use it to get the

strongly connected components of a directed graph .

The dataset X contains the these components maybe you need , but I need to process more.

The code explanation is wasting my time . I have no so much time to do it.

The fist part code of generating table WANT is the most important . once you can understand my BFS search

algorithm ,you will find the key opening a door.

Tarjan algorithm , I am not read it yet . Hope I have some spare time .

Good Luck.

Ksharp

[Ksharp]

Hahahahaha..........

Finnally I caught it . I will write a paper about this and post it to SGF.

I used K algorithm , but I used BFS not DFS .

Matt and Art.T, Hope you have already registed .

data have;
    input (_start _end) (:$1.) @@;
  cards;
  1 2  2 6  2 8  6 2  6 8  6 9
  3 3  4 4  5 7  8 2  8 6  9 6
  ;
  run;

data node(keep=node);
 set have;
 node=_start;output;
 node=_end;output;
run;
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;
declare hash ha(hashexp:20,dataset:'have',multidata:'Y');
ha.definekey('_start');
ha.definedata('_end');
ha.definedone();



declare hash _map(hashexp:20);
_map.definekey('map');
_map.definedone();

declare hash pa(ordered:'Y');
declare hiter hi_path('pa');
pa.definekey('count');
pa.definedata('path');
pa.definedone();

if 0 then set node;
declare hash _node(dataset:'node'); 
declare hiter hi_node('_node');
_node.definekey('node');
_node.definedata('node');
_node.definedone();

declare hash want(ordered:'Y');
declare hiter hi_want('want');
want.definekey('group');
want.definedata('group','component');
want.definedone();

end;

set have end=last;
count=1;
path=catx(' ',_start,_end);
pa.add();
do while(hi_path.next()=0);
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;
pa.clear();

if last then do;
               do while(hi_node.next()=0);
                n+1;
                if n=1 then do;
                              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);
                           map=catx(' ',scan(component,k),node);
                           if _map.check() ne 0 then no=1;

                           map=catx(' ',node,scan(component,k));
                           if _map.check() ne 0 then no=1; 
                          end;
                          if not no then do;
                                         component=catx(' ',component,node);
                                         want.replace(); 
                                         leave;
                                         end;
                         rc=hi_want.next();
                         end;
                       if no then do;
                                   group+1; component=node; want.add();
                                  end;
                      end;
                end;
 
 want.output(dataset:'want');
end;
run;

Ksharp

[Ksharp]

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