## Cycle detection in data set

Solved
Super Contributor
Posts: 355

# Cycle detection in data set

Hello!

I am searching a possibility to detect cycles in a data set. For example, it should tell me that Product A has itself as a component in the following data set:

Data Have;

Input @1 Product \$ @3 Component \$;

Datalines;

M N

N O

A B

B C

C D

D A

;

Run;

Thanks&kind regards

Accepted Solutions
Solution
‎09-02-2014 10:07 AM
Posts: 5,523

## Re: Cycle detection in data set

If you have access to SAS/OR, look into the CYCLE statement of PROC OPTNET.

PG

PG

All Replies
Super Contributor
Posts: 319

## Re: Cycle detection in data set

hello,

if i have understood correctly (you are looking for products that are also components) this may be one solution:

proc sql;

select a.product from have a, have b

where a.product=b.component;

quit;

Super Contributor
Posts: 355

## Re: Cycle detection in data set

Hi!

I am afraid this only tells me which "products" in the first column are componets of another product.

What the program should do is to check the structure: 1. M consists (in part) of N. N consits of O -> o.k. 2. A consists of B. B consists of C. C of D. D of A -> this is a contradiction.

Super User
Posts: 10,766

## Re: Cycle detection in data set

only one product correspond to one component ?

Or one product can project to multi-component ?

Super Contributor
Posts: 355

## Re: Cycle detection in data set

Sorry, bad example. Multiple Components are possible. This would be a better example:

Data Have;

Input @1 Product \$ @3 Component \$;

Datalines;

M N

N O

A B

B C

B F

B G

C D

D A

;

Run;

Solution
‎09-02-2014 10:07 AM
Posts: 5,523

## Re: Cycle detection in data set

If you have access to SAS/OR, look into the CYCLE statement of PROC OPTNET.

PG

PG
Super Contributor
Posts: 355

## Re: Cycle detection in data set

I do. will try.

Super Contributor
Posts: 355

## Re: Cycle detection in data set

Copy Paste of Example 2.2 Cycle Detection for Kidney Donor Exchange worked even for a relatively large data set. Many Thanks !!!!!!!!!!!!

Posts: 1,270

## Re: Cycle detection in data set

Data Have;
Input @1 Product \$ @3 Component \$;
Datalines;
M N
N O
A B
B C
B F
B G
C D
D A
;
Run;

data want;
set have;
if product<component then flag=0;
else flag=1;
run;

Super User
Posts: 10,766

## Re: Cycle detection in data set

It looks like I am late. But just post it here for other user who don't have SAS/OR .

Take a look at LOG to see which one is a circle component.

```data have;
input (_start _end) (:\$1.) @@;
cards;
M N
N O
A B
B C
B F
B G
C D
D A
;
run;

data _null_;
if _n_ eq 1 then do;
length path _path  \$ 200 ;

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

end;

set have;
*initial Hash Table PA, i.e. get the first branch;
count=1;
path=catx(' ',_start,_end);
*Now get start,using Broad Search First  to get all of from-to;
do while(hi_path.next()=0);
_path=path;     *_path is for rollback;
_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;
else putlog 'FOUND:' _end 'is a circle component.';
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();
run;

```

Xia Keshan

🔒 This topic is solved and locked.