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

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: 10,784

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

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?

Posts: 5,539

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

# 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: 10,784

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

```
input from_label \$ to_label \$ weight;
datalines;
A B 3
A D 6
B D 1
;
run;
data have(drop=from_label to_label);
_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);
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);
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

 1 A B A B 3 1 A B B D 1 2 B A B A 3 2 B A A D 6 3 A D A D 6 3 A D D B 1 4 D A D A 6 4 D A A B 3 5 B D B D 1 5 B D D A 6 6 D B D B 1 6 D B B A 3

And is it based on directed or undirected

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

Super User
Posts: 10,784

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

Discussion stats
• 8 replies
• 802 views
• 0 likes
• 3 in conversation