BookmarkSubscribeRSS Feed
🔒 This topic is solved and locked. Need further help from the community? Please sign in and ask a new question.
AmitKB
Fluorite | Level 6

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
Super User

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
Super User

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 . Smiley Happy

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
Super User

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

sas-innovate-2024.png

Don't miss out on SAS Innovate - Register now for the FREE Livestream!

Can't make it to Vegas? No problem! Watch our general sessions LIVE or on-demand starting April 17th. Hear from SAS execs, best-selling author Adam Grant, Hot Ones host Sean Evans, top tech journalist Kara Swisher, AI expert Cassie Kozyrkov, and the mind-blowing dance crew iLuminate! Plus, get access to over 20 breakout sessions.

 

Register now!

How to Concatenate Values

Learn how use the CAT functions in SAS to join values from multiple variables into a single value.

Find more tutorials on the SAS Users YouTube channel.

Click image to register for webinarClick image to register for webinar

Classroom Training Available!

Select SAS Training centers are offering in-person courses. View upcoming courses for:

View all other training opportunities.

Discussion stats
  • 18 replies
  • 2895 views
  • 3 likes
  • 6 in conversation