source: proiecte/Parallel-DT/R8/Src/trees.c @ 72

Last change on this file since 72 was 72, checked in by (none), 14 years ago
File size: 13.0 KB
Line 
1/*************************************************************************/
2/*                                                                       */
3/*      Routines for displaying, building, saving and restoring trees    */
4/*      -------------------------------------------------------------    */
5/*                                                                       */
6/*************************************************************************/
7
8#include "defns.i"
9#include "types.i"
10#include "extern.i"
11
12#define Tab             "|   "
13#define TabSize         4
14#define Width           80      /* approx max width of printed trees */
15
16/*  If lines look like getting too long while a tree is being
17 printed, subtrees are broken off and printed separately after
18 the main tree is finished       */
19
20short Subtree; /* highest subtree to be printed */
21Tree Subdef[100]; /* pointers to subtrees */
22
23FILE *TRf = 0, *fopen(); /* file pointer for tree i/o */
24char Fn[500]; /* file name */
25
26/*************************************************************************/
27/*                                                                       */
28/*      Display entire decision tree T                                   */
29/*                                                                       */
30/*************************************************************************/
31
32PrintTree(T)
33        /*  ----------  */
34        Tree T; {
35        short s;
36
37        Subtree = 0;
38        printf("Decision Tree:\n");
39        Show(T, 0);
40        printf("\n");
41
42        ForEach(s, 1, Subtree) {
43                printf("\n\nSubtree [S%d]\n", s);
44                Show(Subdef[s], 0);
45                printf("\n");
46        }
47        printf("\n");
48}
49
50/*************************************************************************/
51/*                                                                       */
52/*      Display the tree T with offset Sh                                */
53/*                                                                       */
54/*************************************************************************/
55
56Show(T, Sh)
57        /*  ---- */
58        Tree T;short Sh; {
59        DiscrValue v, MaxV;
60        short MaxLine();
61
62        if (T->NodeType) {
63                /*  See whether separate subtree needed  */
64
65                if (T != Nil && Sh && Sh * TabSize + MaxLine(T) > Width) {
66                        if (Subtree < 99) {
67                                Subdef[++Subtree] = T;
68                                printf("[S%d]", Subtree);
69                        } else {
70                                printf("[S??]");
71                        }
72                } else {
73                        MaxV = T->Forks;
74
75                        /*  Print simple cases first */
76
77                        ForEach(v, 1, MaxV) {
78                                if (!T->Branch[v]->NodeType) {
79                                        ShowBranch(Sh, T, v);
80                                }
81                        }
82
83                        /*  Print subtrees  */
84
85                        ForEach(v, 1, MaxV) {
86                                if (T->Branch[v]->NodeType) {
87                                        ShowBranch(Sh, T, v);
88                                }
89                        }
90                }
91        } else {
92                printf(" %s (%.1f", ClassName[T->Leaf], T->Items);
93                if (T->Errors > 0)
94                        printf("/%.1f", T->Errors);
95                printf(")");
96        }
97}
98
99/*************************************************************************/
100/*                                                                       */
101/*      Print a node T with offset Sh, branch value v, and continue      */
102/*                                                                       */
103/*************************************************************************/
104
105ShowBranch(Sh, T, v)
106        /*  -----------  */
107        short Sh;Tree T;DiscrValue v; {
108        DiscrValue Pv, Last;
109        Attribute Att;
110        Boolean FirstValue;
111        short TextWidth, Skip, Values = 0, i;
112
113        Att = T->Tested;
114
115        switch (T->NodeType) {
116        case BrDiscr:
117
118                Indent(Sh, Tab);
119
120                printf("%s = %s:", AttName[Att], AttValName[Att][v]);
121                break;
122
123        case ThreshContin:
124
125                Indent(Sh, Tab);
126
127                printf("%s %s %g ", AttName[Att], (v == 1 ? "<=" : ">"), T->Cut);
128
129                if (T->Lower != T->Upper) {
130                        printf("[%g,%g]", T->Lower, T->Upper);
131                }
132
133                printf(":");
134                break;
135
136        case BrSubset:
137
138                /*  Count values at this branch  */
139
140                ForEach(Pv, 1, MaxAttVal[Att]) {
141                        if (In(Pv, T->Subset[v])) {
142                                Last = Pv;
143                                Values++;
144                        }
145                }
146                if (!Values)
147                        return;
148
149                Indent(Sh, Tab);
150
151                if (Values == 1) {
152                        printf("%s = %s:", AttName[Att], AttValName[Att][Last]);
153                        break;
154                }
155
156                printf("%s in {", AttName[Att]);
157                FirstValue = true;
158                Skip = TextWidth = strlen(AttName[Att]) + 5;
159
160                ForEach(Pv, 1, MaxAttVal[Att]) {
161                        if (In(Pv, T->Subset[v])) {
162                                if (!FirstValue && TextWidth + strlen(AttValName[Att][Pv]) + 11
163                                                > Width) {
164                                        Indent(Sh, Tab);
165                                        ForEach(i, 1, Skip)
166                                                putchar(' ');
167
168                                        TextWidth = Skip;
169                                        FirstValue = true;
170                                }
171
172                                printf("%s%c", AttValName[Att][Pv], Pv == Last ? '}' : ',');
173                                TextWidth += strlen(AttValName[Att][Pv]) + 1;
174                                FirstValue = false;
175                        }
176                }
177                putchar(':');
178        }
179
180        Show(T->Branch[v], Sh + 1);
181}
182
183/*************************************************************************/
184/*                                                                       */
185/*      Find the maximum single line size for non-leaf subtree St.       */
186/*      The line format is                                               */
187/*                      <attribute> <> X.xx:[ <class (<Items>)], or      */
188/*                      <attribute> = <DVal>:[ <class> (<Items>)]        */
189/*                                                                       */
190/*************************************************************************/
191
192short MaxLine(St)
193        /*    --------  */
194        Tree St; {
195        Attribute a;
196        DiscrValue v, MaxV, Next;
197        short Ll, MaxLl = 0;
198
199        a = St->Tested;
200
201        MaxV = St->Forks;
202        ForEach(v, 1, MaxV) {
203                Ll = (St->NodeType == 2 ? 4 : strlen(AttValName[a][v])) + 1;
204
205                /*  Find the appropriate branch  */
206
207                Next = v;
208
209                if (!St->Branch[Next]->NodeType) {
210                        Ll += strlen(ClassName[St->Branch[Next]->Leaf]) + 6;
211                }
212                MaxLl = Max(MaxLl, Ll);
213        }
214
215        return strlen(AttName[a]) + 4 + MaxLl;
216}
217
218/*************************************************************************/
219/*                                                                       */
220/*      Indent Sh columns                                                */
221/*                                                                       */
222/*************************************************************************/
223
224Indent(Sh, Mark)
225        /*  ------  */
226        short Sh;char *Mark; {
227        printf("\n");
228        while (Sh--)
229                printf("%s", Mark);
230}
231
232/*************************************************************************/
233/*                                                                       */
234/*      Save entire decision tree T in file with extension Extension     */
235/*                                                                       */
236/*************************************************************************/
237
238SaveTree(T, Extension)
239        /*  ---------  */
240        Tree T;String Extension; {
241        static char *LastExt = "";
242
243        if (strcmp(LastExt, Extension)) {
244                LastExt = Extension;
245
246                if (TRf)
247                        fclose(TRf);
248
249                strcpy(Fn, FileName);
250                strcat(Fn, Extension);
251                if (!(TRf = fopen(Fn, "w")))
252                        Error(0, Fn, " for writing");
253        }
254
255        putc('\n', TRf);
256        OutTree(T);
257
258        SaveDiscreteNames();
259}
260
261/*************************************************************************/
262/*                                                                       */
263/*      Save tree T as characters                                        */
264/*                                                                       */
265/*************************************************************************/
266
267OutTree(T)
268        /*  --------  */
269        Tree T; {
270        DiscrValue v;
271        int Bytes;
272
273        StreamOut((char *) &T->NodeType, sizeof(short));
274        StreamOut((char *) &T->Leaf, sizeof(ClassNo));
275        StreamOut((char *) &T->Items, sizeof(ItemCount));
276        StreamOut((char *) &T->Errors, sizeof(ItemCount));
277        StreamOut((char *) T->ClassDist, (MaxClass + 1) * sizeof(ItemCount));
278
279        if (T->NodeType) {
280                StreamOut((char *) &T->Tested, sizeof(Attribute));
281                StreamOut((char *) &T->Forks, sizeof(short));
282
283                switch (T->NodeType) {
284                case BrDiscr:
285                        break;
286
287                case ThreshContin:
288                        StreamOut((char *) &T->Cut, sizeof(float));
289                        StreamOut((char *) &T->Lower, sizeof(float));
290                        StreamOut((char *) &T->Upper, sizeof(float));
291                        break;
292
293                case BrSubset:
294                        Bytes = (MaxAttVal[T->Tested] >> 3) + 1;
295                        ForEach(v, 1, T->Forks) {
296                                StreamOut((char *) T->Subset[v], Bytes);
297                        }
298                        break;
299                }
300
301                ForEach(v, 1, T->Forks) {
302                        OutTree(T->Branch[v]);
303                }
304        }
305}
306
307/*************************************************************************/
308/*                                                                       */
309/*      Retrieve entire decision tree with extension Extension           */
310/*                                                                       */
311/*************************************************************************/
312
313Tree GetTree(Extension)
314        /*   --------  */
315        String Extension; {
316        Tree Hold, InTree();
317        static char *LastExt = "";
318
319        if (strcmp(LastExt, Extension)) {
320                LastExt = Extension;
321
322                if (TRf)
323                        fclose(TRf);
324
325                strcpy(Fn, FileName);
326                strcat(Fn, Extension);
327                if (!(TRf = fopen(Fn, "r")))
328                        Error(0, Fn, "");
329        }
330
331        if (!TRf || getc(TRf) == EOF)
332                return Nil;
333
334        Hold = InTree();
335
336        RecoverDiscreteNames();
337
338        return Hold;
339}
340
341/*************************************************************************/
342/*                                                                       */
343/*      Retrieve tree from saved characters                              */
344/*                                                                       */
345/*************************************************************************/
346
347Tree InTree()
348/*   -------  */
349{
350        Tree T;
351        DiscrValue v;
352        int Bytes;
353
354        T = (Tree) malloc(sizeof(TreeRec));
355
356        StreamIn((char *) &T->NodeType, sizeof(short));
357        StreamIn((char *) &T->Leaf, sizeof(ClassNo));
358        StreamIn((char *) &T->Items, sizeof(ItemCount));
359        StreamIn((char *) &T->Errors, sizeof(ItemCount));
360
361        T->ClassDist = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
362        StreamIn((char *) T->ClassDist, (MaxClass + 1) * sizeof(ItemCount));
363
364        if (T->NodeType) {
365                StreamIn((char *) &T->Tested, sizeof(Attribute));
366                StreamIn((char *) &T->Forks, sizeof(short));
367
368                switch (T->NodeType) {
369                case BrDiscr:
370                        break;
371
372                case ThreshContin:
373                        StreamIn((char *) &T->Cut, sizeof(float));
374                        StreamIn((char *) &T->Lower, sizeof(float));
375                        StreamIn((char *) &T->Upper, sizeof(float));
376                        break;
377
378                case BrSubset:
379                        T->Subset = (Set *) calloc(T->Forks + 1, sizeof(Set));
380
381                        Bytes = (MaxAttVal[T->Tested] >> 3) + 1;
382                        ForEach(v, 1, T->Forks) {
383                                T->Subset[v] = (Set) malloc(Bytes);
384                                StreamIn((char *) T->Subset[v], Bytes);
385                        }
386                }
387
388                T->Branch = (Tree *) calloc(T->Forks + 1, sizeof(Tree));
389                ForEach(v, 1, T->Forks) {
390                        T->Branch[v] = InTree();
391                }
392        }
393
394        return T;
395}
396
397/*************************************************************************/
398/*                                                                       */
399/*      Stream characters to/from file TRf from/to an address            */
400/*                                                                       */
401/*************************************************************************/
402
403StreamOut(s, n)
404        /*  ---------  */
405        String s;int n; {
406        while (n--)
407                putc(*s++, TRf);
408}
409
410StreamIn(s, n)
411        /*  ---------  */
412        String s;int n; {
413        while (n--)
414                *s++ = getc(TRf);
415}
416
417/*************************************************************************/
418/*                                                                       */
419/*      Free up space taken up by tree Node                              */
420/*                                                                       */
421/*************************************************************************/
422
423ReleaseTree(Node)
424        /*  -------  */
425        Tree Node; {
426        DiscrValue v;
427
428        if (Node->NodeType) {
429                ForEach(v, 1, Node->Forks) {
430                        ReleaseTree(Node->Branch[v]);
431                }
432
433                cfree(Node->Branch);
434
435                if (Node->NodeType == BrSubset) {
436                        cfree(Node->Subset);
437                }
438
439        }
440
441        cfree(Node->ClassDist);
442        cfree(Node);
443}
444
445/*************************************************************************/
446/*                                                                       */
447/*      Construct a leaf in a given node                                 */
448/*                                                                       */
449/*************************************************************************/
450
451Tree Leaf(ClassFreq, NodeClass, Cases, Errors)
452        /*   ----  */
453        ItemCount *ClassFreq;ClassNo NodeClass;ItemCount Cases, Errors; {
454        Tree Node;
455
456        Node = (Tree) calloc(1, sizeof(TreeRec));
457
458        Node->ClassDist = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
459        memcpy(Node->ClassDist, ClassFreq, (MaxClass + 1) * sizeof(ItemCount));
460
461        Node->NodeType = 0;
462        Node->Leaf = NodeClass;
463        Node->Items = Cases;
464        Node->Errors = Errors;
465
466        return Node;
467}
468
469/*************************************************************************/
470/*                                                                       */
471/*      Insert branches in a node                                        */
472/*                                                                       */
473/*************************************************************************/
474
475Sprout(Node, Branches)
476        /*  ------  */
477        Tree Node;DiscrValue Branches; {
478        Node->Forks = Branches;
479
480        Node->Branch = (Tree *) calloc(Branches + 1, sizeof(Tree));
481}
482
483/*************************************************************************/
484/*                                                                       */
485/*      Count the nodes in a tree                                        */
486/*                                                                       */
487/*************************************************************************/
488
489TreeSize(Node)
490        /*  --------  */
491        Tree Node; {
492        int Sum = 0;
493        DiscrValue v;
494
495        if (Node->NodeType) {
496                ForEach(v, 1, Node->Forks) {
497                        Sum += TreeSize(Node->Branch[v]);
498                }
499        }
500
501        return Sum + 1;
502}
503
504/*************************************************************************/
505/*                                                                       */
506/*      Return a copy of tree T                                          */
507/*                                                                       */
508/*************************************************************************/
509
510Tree CopyTree(T)
511        /*   ---------  */
512        Tree T; {
513        DiscrValue v;
514        Tree New;
515
516        New = (Tree) malloc(sizeof(TreeRec));
517        memcpy(New, T, sizeof(TreeRec));
518
519        New->ClassDist = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
520        memcpy(New->ClassDist, T->ClassDist, (MaxClass + 1) * sizeof(ItemCount));
521
522        if (T->NodeType) {
523                New->Branch = (Tree *) calloc(T->Forks + 1, sizeof(Tree));
524                ForEach(v, 1, T->Forks) {
525                        New->Branch[v] = CopyTree(T->Branch[v]);
526                }
527        }
528
529        return New;
530}
531
532/*************************************************************************/
533/*                                                                       */
534/*      Save attribute values read with "discrete N"                     */
535/*                                                                       */
536/*************************************************************************/
537
538SaveDiscreteNames()
539/*  -----------------  */
540{
541        Attribute Att;
542        DiscrValue v;
543        int Length;
544
545        ForEach(Att, 0, MaxAtt) {
546                if (SpecialStatus[Att] != DISCRETE)
547                        continue;
548
549                StreamOut((char *) &MaxAttVal[Att], sizeof(int));
550
551                ForEach(v, 1, MaxAttVal[Att]) {
552                        Length = strlen(AttValName[Att][v]) + 1;
553
554                        StreamOut((char *) &Length, sizeof(int));
555                        StreamOut((char *) AttValName[Att][v], Length);
556                }
557        }
558}
559
560/*************************************************************************/
561/*                                                                       */
562/*      Recover attribute values read with "discrete N"                  */
563/*                                                                       */
564/*************************************************************************/
565
566RecoverDiscreteNames()
567/*  --------------------  */
568{
569        Attribute Att;
570        DiscrValue v;
571        int Length;
572
573        ForEach(Att, 0, MaxAtt) {
574                if (SpecialStatus[Att] != DISCRETE)
575                        continue;
576
577                StreamIn(&MaxAttVal[Att], sizeof(int));
578
579                ForEach(v, 1, MaxAttVal[Att]) {
580                        StreamIn(&Length, sizeof(int));
581
582                        AttValName[Att][v] = (char *) malloc(Length);
583                        StreamIn(AttValName[Att][v], Length);
584                }
585        }
586}
Note: See TracBrowser for help on using the repository browser.