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

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

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

Super User

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

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

Super User

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

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);
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);
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;
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;
end;
end;
end;

want.output(dataset:'want');
end;
run;

```

Ksharp

Super User

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

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);
*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);
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;
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;
end;
end;
end;
*At this time, we get all the components ,then output it.;
want.output(dataset:'want');
end;
run;

```

Ksharp

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