Cycle detection in data set

[user24feb]

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

[Loko]

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;

[user24feb]

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.

[Ksharp]

only one product correspond to one component ?

Or one product can project to multi-component ?

[user24feb]

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;

[PGStats · Accepted solution]

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

PG

[user24feb]

I do. will try.

[user24feb]

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

[stat_sas]

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;

flag=1 will be contradiction.

[Ksharp]

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);
pa.add();
*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);
                                      pa.add(); 
                                      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