Finding all simple paths between two nodes (source and sink) using PROC OPTGRAPH

Reply
Super Contributor
Posts: 490

Finding all simple paths between two nodes (source and sink) using PROC OPTGRAPH

The Proc OPTGRAPH could be used to find the shortest or longest paths in a graph data set. Is there any way to let the OPTGRAPH gave me all the paths between the sink and source not just the shortest path? And if not, is there any way around in sas to find all the possible paths in a graph between two node.

Super User
Posts: 9,875

Re: Finding all paths between two nodes (source and sink) using PROC OPTGRAP

Post your sample data and the desired output .

Super Contributor
Posts: 490

Re: Finding all paths between two nodes (source and sink) using PROC OPTGRAP

data LinkSetIn;

input from_label $ to_label $ weight;

datalines;

A B 3

A D 6

B D 1

;

What i get with the shortest path in OPTGRAPH

(order source sink from to weight)

1 A B A B 3

1 A D A B 3

2 A D B D 1

1 B A B A 3

1 B D B D 1

1 D A D B 1

2 D A B A 3

1 D B D B 1

What i need is:

(path order source sink from to weight)

1 1 A B A B 3

2 1 A B A D 6

2 2 A B D B 1

1 1 A D A B 3

1 2 A D B D 1

2 1 A D A D 6

1 1 B A B A 3

2 1 B A B D 1

2 2 B A D A 6

1 1 B D B D 1

2 1 B D B A 3

2 2 B D A D 6

...

the data is more complicated, but this for example.

What i need is all the simple paths? and i always know my source and sink?

Respected Advisor
Posts: 4,820

Re: Finding all paths between two nodes (source and sink) using PROC OPTGRAP

Can't find any documentation about OPTGRAPH. Did you mean OPTNET?

PG

PG
Super Contributor
Posts: 490

Re: Finding all paths between two nodes (source and sink) using PROC OPTGRAP

SAS® OPTGRAPH Procedure

http://support.sas.com/documentation/solutions/optgraph/index.html

SAS OPTNET Procedure

http://support.sas.com/documentation/cdl/en/ornoaug/65289/HTML/default/viewer.htm#ornoaug_optnet_syn...

It may be the same implementation in the two Proc (OPTGRAPH & OPTNET)

If you checked the documentation, you will find they have common algorithms, with same examples, description and syntax.

But i have the OPTGRAPH

What i need is all the simple paths not only the shortest one

Super Contributor
Posts: 490

Re: Finding all paths between two nodes (source and sink) using PROC OPTGRAP

Could you find all the simple paths between two nodes using OPTNET?

Super User
Posts: 9,875

Re: Finding all simple paths between two nodes (source and sink) using PROC OPTGRAPH

What about  if you don't have to use PROC OPTGRAPH ?

Note : this code only can handle 100 node , expand "  length path _path  $ 200 ; "  to handle more nodes.


data LinkSetIn;
input from_label $ to_label $ weight;
datalines;
A B 3
A D 6
B D 1
;
run;
data have(drop=from_label to_label);
 set  LinkSetIn ;
 _start=from_label;  _end=to_label; output;
 _start=to_label;  _end=from_label; output;
run;



data want(keep=group s e _s _e _w);
if _n_ eq 1 then do;
length path _path  $ 200 ;

if 0 then set have;
declare hash ha(hashexp:20,dataset:'have',multidata:'Y');
ha.definekey('_start');
ha.definedata('_end','weight');
ha.definedone();

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

set have;
count=1;
path=catx(' ',_start,_end);
pa.add(); group+1; s=_start;e=_end;  _s=_start;_e=_end;_w=weight; output;
do while(hi_path.next()=0);
_path=path;     
_start=scan(path,-1,' '); 
rc=ha.find();
 do while(rc=0);
  if not find(path,strip(_end)) then do;
                                      count+1;  _s=_start;_e=_end;_w=weight;output;
                                      path=catx(' ',path,_end); 
                                      pa.add(); 
                                      path=_path;
                                        end;
  rc=ha.find_next();
 end;
end;
pa.clear();
run;













Xia Keshan

Super Contributor
Posts: 490

Re: Finding all simple paths between two nodes (source and sink) using PROC OPTGRAPH

How do you interpret the output

1ABAB3
1ABBD1
2BABA3
2BAAD6
3ADAD6
3ADDB1
4DADA6
4DAAB3
5BDBD1
5BDDA6
6DBDB1
6DBBA3

And is it based on directed or undirected

And if the node is > 1M, does it will work?

Super User
Posts: 9,875

Re: Finding all simple paths between two nodes (source and sink) using PROC OPTGRAPH

It based on undirected.

1   A   B   A   B   3

1   A   B   B   D   1

2   B   A   B   A   3

2   B   A   A   D   6

every group stand for a branch . since from your output , I infer to you need bi-direct graph, therefore every obs in your table means there are two branch , one is for itself ,another is for reverse .  So you can take group value as a number of obs in my HAVE table.

second and third column stand for the current obs of HAVE ,in other words ,it is an branch.  forth and fifth column stand for all of sub-branch to the current branch( obs ).

"And if the node is > 1M, does it will work?"

You mean a million ? No. my code would not work for that scenario .


Xia Keshan

Ask a Question
Discussion stats
  • 8 replies
  • 680 views
  • 0 likes
  • 3 in conversation