Generate a list of macro variable .

[Saurabh13]

I have a simple problem . My dataset has 3 column Child , Parent, Flag 

I need to search the child into the parent column and check the flag if flag is N ( New node) or Z  we need to again check the child of that parent and continue till we don't get the parent of the child and flag='Y'. 

child	parent	flag
1	.	I
2	1	Z
3	1	Z
4	2	N
5	4	Z
6	4	Z
7	4	Z
8	3	N
9	8	Z
10	8	Z
11	10	N
12	11	Z
13	11	Z
14	13	N
15	14	Z
16	14	Z
17	12	N
18	17	Z
19	17	Z
20	18	N
21	20	Z
22	20	Z
23	19	N
24	23	Z
25	23	Z
36	5	Y
37	6	Y
38	7	Y
39	9	Y
40	21	Y
41	22	Y
42	24	Y
43	25	Y
44	15	Y
45	16	Y

My macro variable list should be generated as :

Tree_List = 1, 2, 4, 5, 36, 6, 37, 7, 38, 3, 8, 9, 39, 10, 11, 12, 17, 18, 20, 21, 40, 22, 41, 19, 23, 24, 42, 25, 43, 13, 14, 15, 44, 16, 45 

Am not able to get the idea how to start coding . Any help would be great help for me. Thanks.

[Ksharp]

What is the FLAG for ?
I also notice the order of Tree_list is based on Deep First Algorithm .
Does the order of it matter ? What if use hierarchy first algorithm ?

[Saurabh13]

Hi,

Flag is there for stop criteria. I need to stop where child has no same parent and FLAG ='Y' . 

Yes, Its a deep first algo. 

[Ksharp]

I think that FLAG is useless, since there are no children for the last person.
So you prefer Deep First Algorithm ?
Once get WANT table, use PROC SQL to get that macro variable you are talking abont,
it is easy for you I think.



data have(rename=(parent=from child=to) drop=flag);
infile cards expandtabs truncover;
input child	parent	flag $;
cards;
1	 .	I
2	1	Z
3	1	Z
4	2	N
5	4	Z
6	4	Z
7	4	Z
8	3	N
9	8	Z
10	8	Z
11	10	N
12	11	Z
13	11	Z
14	13	N
15	14	Z
16	14	Z
17	12	N
18	17	Z
19	17	Z
20	18	N
21	20	Z
22	20	Z
23	19	N
24	23	Z
25	23	Z
36	5	Y
37	6	Y
38	7	Y
39	9	Y
40	21	Y
41	22	Y
42	24	Y
43	25	Y
44	15	Y
45	16	Y
;
run;
data _null_;
 if 0 then set have;
 declare hash from_to(dataset:'have(where=(from is not missing and to is not missing))',hashexp:20,multidata:'y');
 from_to.definekey('from');
 from_to.definedata('to');
 from_to.definedone();

 if 0 then set have(keep=from rename=(from=node));
 declare hash h();
 h.definekey('node');
 h.definedone(); 
 
 declare hash che();
 che.definekey('node');
 che.definedone();
 
 declare hash all(ordered:'a');
 all.definekey('n');
 all.definedata('node');
 all.definedone(); 
 
do while(from_to.num_items ne 0);
 node=1;h.add();
 if che.check() ne 0 then do;che.add();n+1;all.add();end;
 from=node;
 rc=from_to.find();
 do while(rc=0);
  if h.check(key:to)=0 then leave;
   else do; 
          node=to;h.add();
          if che.check() ne 0 then do;che.add();n+1;all.add();end;
         end;
  if from_to.check(key:to)=0 then do; from=to;rc=from_to.find();end;
   else leave;
 end;
 from_to.find();
 from_to.removedup();
 h.clear();
end; 
all.output(dataset:'want');
stop;
run;

[Saurabh13]

Thanks a lot for the reply and solution.

I have never used hashing in SAS so could you please explain a little about the soultion.

1. In second hash you have kept only key so that we can search from this key.

2. could you please explain about 3rd and 4th hash ? Why are they created ? 

3. all.definekey('n'); what is n here ?

4. please explain about do while loop which i think is most important piece in the solution?

I also want to learn so could you please explain a bit that would be great for me and my learning .

[Ksharp]

Hash Table is a big topic to talk. I have no time to go through these. 
Check documentation to get some basic concept.
My basic idea is removing a last person at every iterative .
E.X. you have
1 2
1 3
2 4
Firstly I search 1->2->4 and output 1->2->4 ,remove 2->4(the last person) 
 now it look like 
1 2
1 3
Secondly I search 1->2  and output 1->2(if node are not in Hash Table CHE) ,remove 1->2
.....
until the hash table which contains this dataset is empty
in my code: 
do while(from_to.num_items ne 0);



1. In second hash you have kept only key so that we can search from this key.
the second hash hold the search path at every time like: 1->2->4 or 1->2

2. could you please explain about 3rd and 4th hash ? Why are they created ? 
The third CHE is holding node which has been searched in all the time.

3. all.definekey('n'); what is n here ?
the forth ALL is the result I want. if node is not in CHE then put it into ALL.
The reason I made N is for ordering node, if you don't the node in ALL will be messed up.
Keep the order is important for your question.


4. please explain about do while loop which i think is most important piece in the solution?
do while loop is removing a single person at every loop, just as I said at the beginning.

 if h.check(key:to)=0 then leave; /*<--If we find a dead loop then leave and remove it (4 1)*/
E.X.
1 2
1 3  
2 4
4 1

   else do;  /*else Node is not searched ,put it into H,CHE,ALL*/
          node=to;h.add();
          if che.check() ne 0 then do;che.add();n+1;all.add();end;
         end;

/*if it is last person,then leave and remove it , else find next child*/
  if from_to.check(key:to)=0 then do; from=to;rc=from_to.find();end;
   else leave; /*it is last person*/
 end;
 from_to.find(); /*make point pointed where we want delete*/
 from_to.removedup(); /*remove it e.x. 2->4*/
 h.clear();

[Saurabh13]

Thanks for the explanation . I have also read some documents about the hash.