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