1 /*****************************************************************************
2 FILE : $Source: /projects/higgs1/SNNS/CVS/SNNS/kernel/sources/cc_glob.c,v $
3 SHORTNAME : cc_glob
4 SNNS VERSION : 4.2
5
6 PURPOSE : Common functions for all CC algorithms
7 NOTES : This file was put together from the earlier files cc_rcc
8 and cc_rcc_topo
9
10 AUTHOR : Michael Schmalzl
11 DATE : 5.2.93
12
13 CHANGED BY : Guenter Mamier
14 RCS VERSION : $Revision: 2.7 $
15 LAST CHANGE : $Date: 1998/03/13 16:23:51 $
16
17 Copyright (c) 1990-1995 SNNS Group, IPVR, Univ. Stuttgart, FRG
18 Copyright (c) 1996-1998 SNNS Group, WSI, Univ. Tuebingen, FRG
19
20 ******************************************************************************/
21 #include <config.h>
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <math.h>
26 #include <time.h>
27 #include <memory.h>
28 #ifdef HAVE_VALUES_H
29 #include <values.h>
30 #endif
31 #ifdef HAVE_FCNTL_H
32 #include <fcntl.h>
33 #endif
34
35 #include "kr_typ.h"
36 #include "kr_const.h"
37 #include "kr_def.h"
38 #include "random.h"
39 #include "kr_mac.h"
40 #include "kernel.h"
41 #include "kr_ui.h"
42 #include "kr_newpattern.h"
43 #include "cc_mac.h"
44 #include "cc_type.h"
45 #include "cc_modify.h"
46 #include "cc_display.h"
47
48 #include "cc_glob.ph"
49
50 extern FlintType ACT_Custom_Python(struct Unit * unit_ptr);
51 extern FlintType ACT_DERIV_Custom_Python(struct Unit * unit_ptr);
52 extern FlintType ACT_2_DERIV_Custom_Python(struct Unit * unit_ptr);
53
54
55 /*****************************************************************************
56 FUNCTION : cc_printHeadline
57 PURPOSE : prints Headline iff cc_printOnOff is ON
58 NOTES :
59
60 UPDATE : 30.3.96 <Juergen Gatter>
61 ******************************************************************************/
cc_printHeadline(char * s,int Length)62 void cc_printHeadline(char* s,int Length)
63 {
64 int LengthText,Length1,Length2;
65 int i;
66
67 LengthText=strlen(s)+2;
68 if ((LengthText>Length)||(!cc_printOnOff))
69 return;
70 Length2 = ((Length-LengthText) / 2);
71 Length1 = Length-Length2-LengthText;
72 printf("\n");
73 for (i=0;i<Length1;i++)
74 printf("-");
75 printf(" %s ",s);
76 for (i=0;i<Length2;i++)
77 printf("-");
78 printf("\n\n");
79 }
80
81
82
83 /*****************************************************************************
84 FUNCTION : cc_getErr
85 PURPOSE : get sum of squared errors (sse) = (o_actual - y_desired)^2
86 NOTES :
87
88 UPDATE : 19.01.96
89 ******************************************************************************/
cc_getErr(int StartPattern,int EndPattern)90 float cc_getErr (int StartPattern, int EndPattern)
91 {
92 int p=0, sub, start, end, n, pat, dummy;
93 float sse=0, devit,error;
94 register Patterns out_pat;
95 register struct Unit *OutputUnitPtr;
96 int Correct;
97 int WhichWin,CorrWin;
98 float MaxAct;
99
100 KernelErrorCode = kr_initSubPatternOrder(StartPattern,EndPattern);
101 ERROR_CHECK;
102 cc_getPatternParameter(StartPattern,EndPattern,&start,&end,&n);
103 ERROR_CHECK;
104 SumSqError = 0.0;
105
106 for(p=start; p<=end;p++){
107 Correct=TRUE;
108 MaxAct=0.0;
109 cc_getActivationsForActualPattern(p,start,&pat,&sub);
110 PROPAGATE_THROUGH_OUTPUT_LAYER(OutputUnitPtr,dummy,p);
111
112 out_pat = kr_getSubPatData(pat,sub,OUTPUT,NULL);
113
114 FOR_ALL_OUTPUT_UNITS(OutputUnitPtr,dummy){
115 if (*out_pat > 0.5) CorrWin = dummy;
116 devit = OutputUnitPtr->Out.output - *(out_pat++);
117 if (OutputUnitPtr->Out.output > MaxAct)
118 {
119 MaxAct=OutputUnitPtr->Out.output;
120 WhichWin=dummy;
121 }
122 if (abs(devit) > 0.2) Correct=FALSE;
123 sse += devit*devit;
124 error = devit *
125 (((OutputUnitPtr->act_deriv_func == ACT_DERIV_Custom_Python) ?
126 kr_PythonActFunction(OutputUnitPtr->python_act_deriv_func,
127 OutputUnitPtr) :
128 (OutputUnitPtr->act_deriv_func) (OutputUnitPtr)) + cc_fse);
129 SumSqError += error*error;
130 }
131 }
132 cc_actualNetSaved=TRUE;
133 return sse;
134 }
135
136 /*****************************************************************************
137 FUNCTION : cc_LayerCorrectnessTest
138
139 PURPOSE : Tests if the layer data is valid
140
141 NOTES :
142
143 UPDATE : 30.03.96 <Juergen Gatter>
144 ******************************************************************************/
cc_LayerCorrectnessTest(float * ParameterInArray,int StartPattern,int EndPattern)145 void cc_LayerCorrectnessTest(float* ParameterInArray,
146 int StartPattern, int EndPattern)
147 {
148 int LayerDataCorrect=TRUE;
149 struct Unit *UnitPtr,*UnitPtr2;
150 struct Link *LinkPtr;
151
152 FOR_ALL_UNITS(UnitPtr){
153 if ((CC_LAYER_NO(UnitPtr)==0)&&(IS_OUTPUT_UNIT(UnitPtr)))
154 LayerDataCorrect=FALSE;
155 }
156
157 if (!LayerDataCorrect) {
158 cc_calculateNetParameters();
159 FOR_ALL_UNITS(UnitPtr){
160 CC_SET_LAYER_NO(UnitPtr,0);
161 }
162
163 NoOfLayers=0;
164 /*cc_lastFirstOutputRow=100000;*/
165
166 FOR_ALL_UNITS(UnitPtr){
167 FOR_ALL_LINKS(UnitPtr,LinkPtr){
168 UnitPtr2=LinkPtr->to;
169 if ((CC_LAYER_NO(UnitPtr2)+1) > CC_LAYER_NO(UnitPtr))
170 CC_SET_LAYER_NO(UnitPtr,CC_LAYER_NO(UnitPtr2)+1);
171 }
172 if(CC_LAYER_NO(UnitPtr)>NoOfLayers)
173 NoOfLayers=CC_LAYER_NO(UnitPtr);
174 /*if ((IS_OUTPUT_UNIT(unitPtr))&&
175 (GET_UNIT_XPOS(unitPtr) < cc_lastFirstOutputRow))
176 cc_lastFirstOutputRow = GET_UNIT_XPOS(unitPtr);*/
177 } /* This algorithm works correct, iff u2 is in a layer greater than u1
178 --> NO(U2) > NO(U1) (except output units)*/
179
180 }
181
182 if (NoOfHiddenUnits<=0) {
183 NoOfLayers=0;
184 LastInsertedHiddenUnit=0;
185 }
186
187 SumSqError=0.0; /* Recalc SumSqEror later */
188 }
189
190 /*****************************************************************************
191 FUNCTION : cc_freeStorage
192
193 PURPOSE : Frees all the storage allocated by CC.
194 NOTES :
195
196 UPDATE : 5.2.93
197 ******************************************************************************/
cc_freeStorage(int StartPattern,int EndPattern,int flag)198 krui_err cc_freeStorage(int StartPattern,int EndPattern, int flag)
199 {
200 struct Unit *unitPtr;
201 struct Link *linkPtr;
202 int start, end, n;
203
204 cc_getPatternParameter(StartPattern,EndPattern,&start,&end,&n);
205 ERROR_CHECK;
206
207 cc_storageFree = 1;
208
209 if(flag==1){
210 (void) cc_deleteAllSpecialAndAllHiddenUnits();
211 cc_end = 0;
212 FOR_ALL_UNITS(unitPtr){
213 if(UNIT_IN_USE(unitPtr) && IS_OUTPUT_UNIT(unitPtr)){
214 unitPtr->value_a = unitPtr->value_b = unitPtr->value_c = 0;
215 FOR_ALL_LINKS(unitPtr,linkPtr){
216 linkPtr->value_a = linkPtr->value_b = linkPtr->value_c = 0;
217 }
218 }
219 }
220 return(KRERR_NO_ERROR);
221 }else{
222 FREE_2DIMENSIONAL_ARRAY_WITH_PRINT(OutputUnitError,n,p);
223 FREE_2DIMENSIONAL_ARRAY(CorBetweenSpecialActAndOutError,
224 cc_MaxSpecialUnitNo,s);
225 FREE_2DIMENSIONAL_ARRAY(SpecialUnitAct,n,p);
226 FREE_2DIMENSIONAL_ARRAY(ActOfUnit,n,p);
227 FREE_IF_USED(MeanOutputUnitError);
228 FREE_IF_USED(SpecialUnitSumAct);
229
230 cc_actualNetSaved=FALSE;
231
232 cc_deallocateMemory(); /* deallocate Memory needed by modifications */
233
234 return(KRERR_NO_ERROR);
235 }
236
237 }
238
239 /*****************************************************************************
240 FUNCTION : cc_allocateStorage
241
242 PURPOSE : Allocates all the storage needed by CC
243 NOTES :
244
245 UPDATE : 19.01.96
246 ******************************************************************************/
cc_allocateStorage(int StartPattern,int EndPattern,int NoOfSpecialUnits)247 krui_err cc_allocateStorage(int StartPattern, int EndPattern,
248 int NoOfSpecialUnits)
249 {
250 int p;
251 int start, end, n;
252
253 OldNoOfSpecialUnitStorage = NoOfSpecialUnits;
254 cc_storageFree = 0;
255
256 cc_getPatternParameter(StartPattern,EndPattern,&start,&end,&n);
257 ERROR_CHECK;
258
259 CALLOC_ERRORCHECK(MeanOutputUnitError,NoOfOutputUnits,float);
260 CALLOC_ERRORCHECK(SpecialUnitSumAct,NoOfSpecialUnits,float);
261 CALLOC_2DIMENSIONAL_ARRAY(OutputUnitError,n,NoOfOutputUnits,float,p);
262 CALLOC_2DIMENSIONAL_ARRAY(SpecialUnitAct,n,cc_MaxSpecialUnitNo,float,p);
263 CALLOC_2DIMENSIONAL_ARRAY(CorBetweenSpecialActAndOutError,NoOfSpecialUnits,
264 NoOfOutputUnits,float,p);
265 if(cc_fastmode){
266 CALLOC_2DIMENSIONAL_ARRAY(ActOfUnit,n,
267 (NoOfInputUnits+NoOfHiddenUnits+NO_OF_GROUPS),
268 float,p);
269 /* no of groups is set to a value bigger than 1, iff CCS-modification
270 is set */
271 }
272
273 return(cc_allocateMemoryForModifications());
274 }
275
276
277 /*****************************************************************************
278 FUNCTION : cc_deleteAllSpecialAndAllHiddenUnits
279
280 PURPOSE : Deletes all special units and all hidden units.
281 NOTES :
282
283 UPDATE : 19.01.96
284 ******************************************************************************/
cc_deleteAllSpecialAndAllHiddenUnits(void)285 krui_err cc_deleteAllSpecialAndAllHiddenUnits(void)
286 {
287 struct Unit *UnitPtr;
288
289 if(NoOfUnits != 0) {
290 FOR_ALL_UNITS(UnitPtr){
291 if((IS_HIDDEN_UNIT(UnitPtr) || IS_SPECIAL_UNIT(UnitPtr)) &&
292 UNIT_IN_USE(UnitPtr)) {
293 KernelErrorCode = kr_removeUnit(UnitPtr);
294 ERROR_CHECK;
295 }
296 }
297 kr_forceUnitGC();
298 NoOfHiddenUnits = 0;
299 NetModified = 1;
300 }
301 return(KRERR_NO_ERROR);
302 }
303
304
305
306 /*****************************************************************************
307 FUNCTION : cc_initActivationArrays
308
309 PURPOSE :
310 NOTES :
311
312 UPDATE : 19.01.96
313 ******************************************************************************/
cc_initActivationArrays(void)314 void cc_initActivationArrays(void)
315 {
316 int s,o;
317 struct Unit *outputUnitPtr,*specialUnitPtr;
318
319 FOR_ALL_SPECIAL_UNITS(specialUnitPtr,s) {
320 SpecialUnitSumAct[s] = 0.0;
321 }
322
323 FOR_ALL_SPECIAL_UNITS(specialUnitPtr,s) {
324 FOR_ALL_OUTPUT_UNITS(outputUnitPtr,o) {
325 CorBetweenSpecialActAndOutError[s][o] = 0.0;
326 }
327 }
328 }
329
330
331 /*****************************************************************************
332 FUNCTION : cc_generateRandomNo
333
334 PURPOSE : Generates a random number in the interval [-maxValue,+maxValue]
335 NOTES :
336
337 UPDATE : 19.01.96
338 ******************************************************************************/
cc_generateRandomNo(float maxValue)339 FlintType cc_generateRandomNo(float maxValue)
340 {
341 return (FlintType)(drand48()*2.0*maxValue-maxValue);
342 }
343
344
345
346 /*****************************************************************************
347 FUNCTION : cc_initOutputUnits
348
349 PURPOSE : Initializes the links of the output units.
350 NOTES :
351
352 UPDATE : 19.01.96
353 ******************************************************************************/
cc_initOutputUnits(void)354 void cc_initOutputUnits(void)
355 {
356 struct Unit *outputUnitPtr;
357 struct Link *linkPtr;
358 int o;
359
360 FOR_ALL_OUTPUT_UNITS(outputUnitPtr,o){
361 outputUnitPtr->value_a =
362 outputUnitPtr->value_b = outputUnitPtr->value_c = 0;
363 FOR_ALL_LINKS(outputUnitPtr,linkPtr){
364 linkPtr->value_a = linkPtr->value_b = linkPtr->value_c = 0;
365 }
366 }
367 }
368
369
370 /*****************************************************************************
371 FUNCTION : cc_getPatternParameter
372
373 PURPOSE : Get the Pattern-Parameters needed
374 NOTES :
375
376 UPDATE : 30.11.95 <Juergen Gatter>
377 ******************************************************************************/
cc_getPatternParameter(int StartPattern,int EndPattern,int * start,int * end,int * n)378 krui_err cc_getPatternParameter(int StartPattern,int EndPattern,
379 int* start, int* end,int* n)
380 {
381 KernelErrorCode = kr_initSubPatternOrder(StartPattern,EndPattern);
382 ERROR_CHECK;
383 *start = kr_AbsPosOfFirstSubPat(StartPattern);
384 *end = kr_AbsPosOfFirstSubPat(EndPattern);
385 *end += kr_NoOfSubPatPairs(EndPattern) - 1;
386 *n = *end - *start + 1;
387 return (KernelErrorCode);
388 }
389
390
391 /*****************************************************************************
392 FUNCTION : cc_getActivationsForActualPattern
393
394 PURPOSE : Gets or calculates the activations for the input and
395 hidden units.
396 NOTES :
397
398 UPDATE : 19.01.96
399 ******************************************************************************/
cc_getActivationsForActualPattern(int SubPatternNo,int First,int * pat,int * sub)400 void cc_getActivationsForActualPattern(int SubPatternNo,int First,int* pat,
401 int* sub)
402 {
403 struct Unit *UnitPtr;
404 Patterns in_pat;
405 int dummy,relPatternNo;
406 int Index1,Index2;
407
408 relPatternNo=SubPatternNo-First;
409
410 kr_getSubPatternByNo(pat,sub,SubPatternNo);
411 in_pat = kr_getSubPatData(*pat,*sub,INPUT,NULL);
412 if((cc_fastmode)&&(cc_actualNetSaved)){
413 FOR_ALL_INPUT_UNITS(UnitPtr,Index1){
414 UnitPtr->Out.output = ActOfUnit[relPatternNo][Index1];
415 }
416 FOR_ALL_HIDDEN_UNITS(UnitPtr,Index2){
417 UnitPtr->Out.output = UnitPtr->act =
418 ActOfUnit[relPatternNo][Index1+Index2];
419 }
420 }else{
421 PROPAGATE_THROUGH_INPUT_LAYER(UnitPtr,dummy,in_pat);
422 PROPAGATE_THROUGH_HIDDEN_LAYER(UnitPtr,dummy,SubPatternNo);
423 if(cc_fastmode){ /* then save activations */
424 FOR_ALL_INPUT_UNITS(UnitPtr,Index1){
425 ActOfUnit[relPatternNo][Index1] = UnitPtr->Out.output;
426 }
427 FOR_ALL_HIDDEN_UNITS(UnitPtr,Index2){
428 ActOfUnit[relPatternNo][Index1+Index2] = UnitPtr->Out.output;
429 }
430 }
431 }
432 }
433
434
435 /*****************************************************************************
436 FUNCTION : cc_setPointers
437
438 PURPOSE : Calculates the beginning of the input, hidden, output and special
439 units in the topo_ptr_array.
440 NOTES :
441
442 UPDATE : 19.01.96
443 ******************************************************************************/
cc_setPointers(void)444 krui_err cc_setPointers(void)
445 {
446 FirstInputUnitPtr = (struct Unit **)(&topo_ptr_array[1]);
447 if(*(FirstInputUnitPtr-1)!=NULL) CC_ERROR(KRERR_CC_ERROR1);
448 FirstHiddenUnitPtr = FirstInputUnitPtr + NoOfInputUnits + 1;
449 if(*(FirstHiddenUnitPtr-1)!=NULL) CC_ERROR(KRERR_CC_ERROR1);
450 FirstOutputUnitPtr = FirstHiddenUnitPtr + NoOfHiddenUnits + 1;
451 if(*(FirstOutputUnitPtr-1)!=NULL) CC_ERROR(KRERR_CC_ERROR1);
452 FirstSpecialUnitPtr = FirstOutputUnitPtr + NoOfOutputUnits + 1;
453 if(*(FirstSpecialUnitPtr-1)!=NULL) CC_ERROR(KRERR_CC_ERROR1);
454 return(KRERR_NO_ERROR);
455 }
456
457 /*****************************************************************************
458 FUNCTION : cc_initSpecialUnitLinks
459
460 PURPOSE : Sets all the links of the special units to zero.
461 NOTES :
462
463 UPDATE : 19.01.96
464 ******************************************************************************/
cc_initSpecialUnitLinks(void)465 krui_err cc_initSpecialUnitLinks(void)
466 {
467 int s;
468 struct Unit *SpecialUnitPtr;
469 struct Link *LinkPtr;
470
471 FOR_ALL_SPECIAL_UNITS(SpecialUnitPtr,s) {
472 SpecialUnitPtr->bias = 0.0;
473 BIAS_CURRENT_SLOPE(SpecialUnitPtr) = 0.0;
474 BIAS_PREVIOUS_SLOPE(SpecialUnitPtr) = 0.0;
475 BIAS_LAST_WEIGHT_CHANGE(SpecialUnitPtr) = 0.0;
476 FOR_ALL_LINKS(SpecialUnitPtr,LinkPtr) {
477 LinkPtr->weight = cc_generateRandomNo(CC_MAX_VALUE);
478 LN_CURRENT_SLOPE(LinkPtr) = 0.0;
479 LN_PREVIOUS_SLOPE(LinkPtr) = 0.0;
480 LN_LAST_WEIGHT_CHANGE(LinkPtr) = 0.0;
481 }
482 }
483 return(KRERR_NO_ERROR);
484 }
485
486
487 /*****************************************************************************
488 FUNCTION : cc_deleteAllSpecialUnits
489
490 PURPOSE : Deletes all special units.
491 NOTES :
492
493 UPDATE : 19.01.96
494 ******************************************************************************/
cc_deleteAllSpecialUnits(void)495 krui_err cc_deleteAllSpecialUnits(void)
496 {
497 struct Unit *UnitPtr;
498
499 if(NoOfUnits != 0) {
500 FOR_ALL_UNITS(UnitPtr){
501 if(IS_SPECIAL_UNIT(UnitPtr) && UNIT_IN_USE(UnitPtr)){
502 KernelErrorCode = kr_removeUnit(UnitPtr);
503 ERROR_CHECK;
504 }
505 }
506 kr_forceUnitGC();
507 NetModified = 1;
508 }
509 return(KRERR_NO_ERROR);
510 }
511
512
513 /*****************************************************************************
514 FUNCTION : QuickPropOfflinePart
515
516 PURPOSE : Update the weights ( or bias ) in QuickProp-Style
517 NOTES :
518
519 UPDATE : extracted 19.1.96 Juergen Gatter
520 ******************************************************************************/
QuickPropOfflinePart(float oldValue,float * previousSlope,float * currentSlope,float * LastChange,float epsilon,float mu,float decay)521 float QuickPropOfflinePart(float oldValue, float* previousSlope,
522 float* currentSlope, float* LastChange,
523 float epsilon, float mu, float decay)
524 {
525 float current,change;
526
527 current = *currentSlope + decay * oldValue;
528 if(*previousSlope == 0.0){
529 change = -epsilon*current;
530 }else{
531 if(current*(SGN(*previousSlope)) >= (mu/(mu+1))*fabs(*previousSlope)){
532 change = mu * (*LastChange);
533 }else{
534 change = *LastChange * current / (*previousSlope-current);
535 }
536 if (SGN(*previousSlope)==SGN(current)){
537 change -= epsilon * current;
538 }
539 }
540 *previousSlope = current;
541 *currentSlope = 0.0;
542 return (*LastChange = change);
543 }
544
545
546 /*****************************************************************************
547 FUNCTION : RPropOfflinePart
548
549 PURPOSE : Update the weights ( or bias ) in QuickProp-Style
550 NOTES :
551
552 UPDATE : extracted 19.1.96 Juergen Gatter
553 ******************************************************************************/
RPropOfflinePart(float oldValue,float * previousSlope,float * currentSlope,float * LastChange,float epsilonMinus,float epsilonPlus,float dummy)554 float RPropOfflinePart(float oldValue,float* previousSlope, float* currentSlope,
555 float* LastChange, float epsilonMinus,
556 float epsilonPlus,float dummy)
557 {
558 float change,lastChange;
559
560 change = 0;
561 lastChange = (*LastChange == 0.0) ? 1.0 : *LastChange;
562 if (*currentSlope != 0.0){
563 if (*previousSlope == 0.0){
564 change = fabs(lastChange) * SIGN(*currentSlope);
565 }else if (*previousSlope > 0.0){
566 change =
567 ((*currentSlope>0.0)? epsilonPlus : -epsilonMinus) * lastChange;
568 }else{
569 change =
570 ((*currentSlope<0.0)? epsilonPlus : -epsilonMinus) * lastChange;
571 }
572 if (fabs(change) < 0.00001) change = 0.00001 * SIGN(change);
573 if (fabs(change) > 10.0 ) change = 10.0 * SIGN(change);
574 }
575 *previousSlope = *currentSlope;
576 *currentSlope = 0.0;
577 *LastChange = change;
578 return (-change);
579 }
580
581 /*****************************************************************************
582 FUNCTION : BackPropOfflinePart
583
584 PURPOSE : Update the weights ( or bias ) in BackProp
585 NOTES : This one is used by rcc.
586
587 UPDATE : extracted 19.1.96 Juergen Gatter
588 ******************************************************************************/
BackPropOfflinePart(float oldValue,float * previousSlope,float * currentSlope,float * LastChange,float eta,float mu,float dummy)589 float BackPropOfflinePart(float oldValue, float* previousSlope,
590 float* currentSlope, float* LastChange,
591 float eta, float mu, float dummy)
592 {
593 float change;
594
595 *LastChange = change = -(*currentSlope * eta + *LastChange * mu);
596
597 *previousSlope = *currentSlope;
598 *currentSlope = 0.0;
599 return(change);
600
601 }
602
603 /*****************************************************************************
604 FUNCTION : OnlineBackPropPropOfflinePart
605
606 PURPOSE : Update the weights ( or bias ) in BackProp (online)
607 NOTES :
608
609 UPDATE : extracted 19.1.96 Juergen Gatter
610 ******************************************************************************/
OnlineBackPropOfflinePart(float oldValue,float * previousSlope,float * currentSlope,float * LastChange,float eta,float mu,float dummy)611 float OnlineBackPropOfflinePart(float oldValue, float* previousSlope,
612 float* currentSlope, float* LastChange,
613 float eta, float mu, float dummy)
614 {
615 return(0.0);
616 }
617
618
619
620 /*****************************************************************************
621 FUNCTION : cc_setCycletestFlag(struct Unit* UnitPtr)
622
623 PURPOSE : Sets CycletestFlag to 1
624 NOTES :
625
626 UPDATE : 22.11.95 (Juergen Gatter)
627 ******************************************************************************/
cc_setCycletestFlag(struct Unit * UnitPtr)628 void cc_setCycletestFlag(struct Unit* UnitPtr)
629 {
630 if (UnitPtr->lln >= 0)
631 UnitPtr->lln = (-1)-UnitPtr->lln;
632 }
633
634 /*****************************************************************************
635 FUNCTION : cc_testCycletestFlag(struct Unit* UnitPtr)
636
637 PURPOSE : test whether CycletestFlag is 1
638 NOTES :
639
640 UPDATE : 22.11.95 (Juergen Gatter)
641 ******************************************************************************/
cc_testCycletestFlag(struct Unit * UnitPtr)642 static bool cc_testCycletestFlag(struct Unit* UnitPtr)
643 {
644 return (UnitPtr->lln >= 0);
645 }
646
647 /*****************************************************************************
648 FUNCTION : cc_clearAllCycletestFlags(void)
649
650 PURPOSE : resets the CycletestFlag to 0.
651 NOTES :
652
653 UPDATE : 22.11.95 (Juergen Gatter)
654 ******************************************************************************/
cc_clearAllCycletestFlags(void)655 static void cc_clearAllCycletestFlags(void)
656 {
657 struct Unit* UnitPtr;
658
659 FOR_ALL_UNITS(UnitPtr) {
660 if (UnitPtr->lln < 0)
661 UnitPtr->lln = (-1) - UnitPtr->lln;
662 }
663 }
664
665
666 /*****************************************************************************
667 FUNCTION : cc_clearFlags
668
669 PURPOSE : Clears all CC flags.
670 NOTES :
671
672 UPDATE : 5.2.93
673 ******************************************************************************/
cc_clearFlags(void)674 static void cc_clearFlags(void)
675 {
676 struct Unit *unitPtr;
677
678 cc_clearAllCycletestFlags();
679
680 FOR_ALL_UNITS(unitPtr){
681 if(UNIT_IN_USE(unitPtr)){
682 unitPtr->flags &= ~UFLAG_REFRESH;
683 LINKS_LEAVING(unitPtr) = 0;
684 LINKS_ARRIVEING(unitPtr) = 0;
685 INPUT_LINKS(unitPtr) = 0;
686 }
687 }
688 }
689
690
691 /*****************************************************************************
692 FUNCTION : DepthFirst4
693
694 PURPOSE : Depth search routine for topological sorting.
695 NOTES :
696
697 UPDATE : 5.2.93
698 ******************************************************************************/
DepthFirst4(struct Unit * unit_ptr,int depth)699 static void DepthFirst4(struct Unit *unit_ptr, int depth )
700 {
701
702 struct Site *site_ptr;
703 struct Link *link_ptr;
704
705 if (unit_ptr->flags & UFLAG_REFRESH){
706 /* the 'touch' flag is set: don't continue search */
707 topo_msg.src_error_unit = unit_ptr - unit_array; /* store unit number */
708
709 if IS_OUTPUT_UNIT( unit_ptr ){
710 /* this output unit has a output connection to another unit */
711 if (topo_msg.error_code == KRERR_NO_ERROR)
712 topo_msg.error_code = KRERR_O_UNITS_CONNECT;
713 }else if (cc_testCycletestFlag(unit_ptr)){
714 /* logical layer no. isn't set => Cycle found */
715 topo_msg.no_of_cycles++;
716 if (topo_msg.error_code == KRERR_NO_ERROR)
717 topo_msg.error_code = KRERR_CYCLES;
718 }
719
720 return;
721 }else
722 /* set the 'touch' flag */
723 unit_ptr->flags |= UFLAG_REFRESH;
724
725 switch (unit_ptr->flags & UFLAG_INPUT_PAT){
726
727 case UFLAG_DLINKS: /* unit has direct links */
728 FOR_ALL_LINKS(unit_ptr,link_ptr){
729 DepthFirst4( link_ptr->to, depth + 1 ); /* increase depth */
730 if(IS_INPUT_UNIT(link_ptr->to)){
731 INPUT_LINKS(unit_ptr)++;
732 }
733 if((IS_HIDDEN_UNIT(link_ptr->to)) && (IS_HIDDEN_UNIT(unit_ptr))){
734 LINKS_LEAVING(link_ptr->to)++;
735 LINKS_ARRIVEING(unit_ptr)++;
736 }
737 }
738 break;
739 case UFLAG_SITES: /* unit has sites */
740 FOR_ALL_SITES_AND_LINKS(unit_ptr,site_ptr, link_ptr) {
741 DepthFirst4( link_ptr->to, depth + 1 ); /* increase depth */
742 if(IS_INPUT_UNIT(link_ptr->to)){
743 INPUT_LINKS(unit_ptr)++;
744 }
745 if((IS_HIDDEN_UNIT(link_ptr->to)) && (IS_HIDDEN_UNIT(unit_ptr))){
746 LINKS_LEAVING(link_ptr->to)++;
747 LINKS_ARRIVEING(unit_ptr)++;
748 }
749 }
750 break;
751 }
752
753 /* remember the depth (for cycle detection and statistics) */
754 cc_setCycletestFlag(unit_ptr);
755
756 /* store only hidden units */
757 if IS_HIDDEN_UNIT( unit_ptr )
758 *global_topo_ptr++ = unit_ptr; /* store sorted unit pointer */
759 }
760
761
762
763 /*****************************************************************************
764 FUNCTION : DepthFirst5
765
766 PURPOSE : Depth search routine for topological sorting.
767 NOTES :
768
769 UPDATE : 5.2.93
770 ******************************************************************************/
DepthFirst5(struct Unit * unit_ptr,int depth)771 static void DepthFirst5(struct Unit *unit_ptr, int depth )
772 {
773 struct Site *site_ptr;
774 struct Link *link_ptr;
775
776 if (unit_ptr->flags & UFLAG_REFRESH){
777 /* the 'touch' flag is set: don't continue search */
778 topo_msg.src_error_unit = unit_ptr - unit_array; /* store unit number */
779
780 if IS_OUTPUT_UNIT( unit_ptr ){
781 /* this output unit has a output connection to another unit */
782 if (topo_msg.error_code == KRERR_NO_ERROR)
783 topo_msg.error_code = KRERR_O_UNITS_CONNECT;
784 }else if (cc_testCycletestFlag(unit_ptr)){
785 /* logical layer no. isn't set => Cycle found */
786 topo_msg.no_of_cycles++;
787 if (topo_msg.error_code == KRERR_NO_ERROR)
788 topo_msg.error_code = KRERR_CYCLES;
789 }
790
791 return;
792 }else
793 /* set the 'touch' flag */
794 unit_ptr->flags |= UFLAG_REFRESH;
795
796 switch (unit_ptr->flags & UFLAG_INPUT_PAT){
797
798 case UFLAG_DLINKS: /* unit has direct links */
799 FOR_ALL_LINKS(unit_ptr,link_ptr) {
800 if((IS_HIDDEN_UNIT(unit_ptr)) && (link_ptr->to == unit_ptr)) {
801 /* RCC code deleted */
802 }else{
803 DepthFirst5( link_ptr->to, depth + 1 ); /* increase depth */
804 if(IS_INPUT_UNIT(link_ptr->to)){
805 INPUT_LINKS(unit_ptr)++;
806 }
807 if((IS_HIDDEN_UNIT(link_ptr->to))&&(IS_HIDDEN_UNIT(unit_ptr))){
808 LINKS_LEAVING(link_ptr->to)++;
809 LINKS_ARRIVEING(unit_ptr)++;
810 }
811 }
812 }
813 break;
814 case UFLAG_SITES: /* unit has sites */
815 FOR_ALL_SITES_AND_LINKS(unit_ptr,site_ptr, link_ptr) {
816 if((IS_HIDDEN_UNIT(unit_ptr)) && (link_ptr->to == unit_ptr)) {
817 /* RCC code deleted */
818 }else{
819 DepthFirst5( link_ptr->to, depth + 1 ); /* increase depth */
820 if(IS_INPUT_UNIT(link_ptr->to)){
821 INPUT_LINKS(unit_ptr)++;
822 }
823 if((IS_HIDDEN_UNIT(link_ptr->to))&&(IS_HIDDEN_UNIT(unit_ptr))){
824 LINKS_LEAVING(link_ptr->to)++;
825 LINKS_ARRIVEING(unit_ptr)++;
826 }
827 }
828 }
829 break;
830 }
831
832 cc_setCycletestFlag(unit_ptr);
833
834 /* store only hidden units */
835 if IS_HIDDEN_UNIT( unit_ptr )
836 *global_topo_ptr++ = unit_ptr; /* store sorted unit pointer */
837 }
838
839
840 /*****************************************************************************
841 FUNCTION : cc_topoSort
842
843 PURPOSE : Calls the Main routine for topological sorting for CC
844 and clears all cycletestFlags.
845
846 UPDATE : 5.2.93
847 ******************************************************************************/
cc_topoSort(int topoSortID)848 krui_err cc_topoSort(int topoSortID)
849 {
850 int Error;
851
852 Error = cc_topoSortMain(topoSortID);
853 cc_clearAllCycletestFlags();
854 return (Error);
855 }
856
857
858
859 /*****************************************************************************
860 FUNCTION : cc_topoSortMain
861
862 PURPOSE : Main routine for topological sorting for CC.
863 NOTES :
864
865 UPDATE : 5.2.93
866 ******************************************************************************/
cc_topoSortMain(int topoSortId)867 krui_err cc_topoSortMain(int topoSortId)
868 {
869 register struct Unit *unit_ptr;
870 int io_units,h,counter=0;
871
872 KernelErrorCode = KRERR_NO_ERROR; /* reset return code */
873 if(topoSortId == TOPOLOGICAL_CC) {
874 cc_clearFlags(); /* reset units 'touch' flags */
875 }
876
877 global_topo_ptr = topo_ptr_array; /* initialize global pointer */
878
879 /* limit left side of the topological array with NULL pointer */
880 *global_topo_ptr++ = NULL;
881
882 /* put all input units in the topologic array */
883 io_units = 0;
884 FOR_ALL_UNITS( unit_ptr )
885 if (IS_INPUT_UNIT( unit_ptr ) && UNIT_IN_USE( unit_ptr )){
886 if UNIT_HAS_INPUTS( unit_ptr ){
887 /* this input unit has a connection to another unit */
888 topo_msg.dest_error_unit = unit_ptr - unit_array;
889
890 KernelErrorCode = KRERR_I_UNITS_CONNECT;
891 return( KernelErrorCode );
892 }
893
894 io_units++; /* there is a input unit */
895 *global_topo_ptr++ = unit_ptr; /* save input unit */
896 }
897
898 if ((NoOfInputUnits = io_units) == 0){
899 /* no input units */
900 KernelErrorCode = KRERR_NO_INPUT_UNITS;
901 return( KernelErrorCode );
902 }
903
904 /* limit input units in the topological array with NULL pointer */
905 *global_topo_ptr++ = NULL;
906
907 /* begin depth search at the first output unit */
908 io_units = 0;
909 FOR_ALL_UNITS( unit_ptr )
910 if (IS_OUTPUT_UNIT( unit_ptr ) && UNIT_IN_USE( unit_ptr )){
911 io_units++; /* there is a output unit */
912 if(topoSortId == TOPOLOGICAL_CC){
913 DepthFirst4( unit_ptr, 1 );
914 }
915 else { /* topoSortId == TOPOLOGICAL_BCC */
916 DepthFirst4(unit_ptr,1);
917 }
918 if (topo_msg.error_code != KRERR_NO_ERROR){
919 /* stop if an error occured */
920 KernelErrorCode = topo_msg.error_code;
921 return( KernelErrorCode );
922 }
923 }
924
925
926 if ((NoOfOutputUnits = io_units) == 0){
927 /* no output units */
928 KernelErrorCode = KRERR_NO_OUTPUT_UNITS;
929 return( KernelErrorCode );
930 }
931
932 /* limit hidden units in the topological array with NULL pointer */
933 *global_topo_ptr++ = NULL;
934
935 /* put all output units in the topological array */
936 FOR_ALL_UNITS( unit_ptr )
937 if (IS_OUTPUT_UNIT(unit_ptr ) && UNIT_IN_USE( unit_ptr ))
938 *global_topo_ptr++ = unit_ptr; /* save output unit */
939
940 /* limit right side of the topologic array with NULL pointer */
941 *global_topo_ptr++ = NULL;
942
943 FOR_ALL_UNITS( unit_ptr ) {
944 if (IS_SPECIAL_UNIT(unit_ptr) && UNIT_IN_USE( unit_ptr )) {
945 *global_topo_ptr++ = unit_ptr; /* save output unit */
946 unit_ptr->flags |= UFLAG_REFRESH;
947 }
948 }
949 /* limit right side of the topologic array with NULL pointer */
950 *global_topo_ptr++ = NULL;
951
952 /* calc. no. of sorted units */
953 no_of_topo_units = (global_topo_ptr - topo_ptr_array) - 5;
954
955 /* search for dead units i.e. units without inputs */
956 FOR_ALL_UNITS( unit_ptr )
957 if (!(unit_ptr->flags & UFLAG_REFRESH) && UNIT_IN_USE( unit_ptr )){
958 topo_msg.no_of_dead_units++;
959 if (topo_msg.src_error_unit == 0)
960 topo_msg.src_error_unit = unit_ptr - unit_array;
961 }
962
963 if (topo_msg.no_of_dead_units != 0)
964 /* KernelErrorCode = KRERR_DEAD_UNITS;
965 * allowed for compression */
966 if(KernelErrorCode == KRERR_NO_ERROR){
967 FirstHiddenUnitPtr = (struct Unit **)(&topo_ptr_array[1]) +
968 NoOfInputUnits + 1;
969 FOR_ALL_HIDDEN_UNITS(unit_ptr,h){
970 switch(topoSortId){
971 case TOPOLOGICAL_CC :
972 break;
973 case TOPOLOGICAL_BCC :
974 if((LINKS_LEAVING(unit_ptr)+LINKS_ARRIVEING(unit_ptr)+1) !=
975 NoOfHiddenUnits) {
976 KernelErrorCode = KRERR_CC_ERROR6;
977 return(KernelErrorCode);
978 }
979 if(LINKS_ARRIVEING(unit_ptr) != counter++) {
980 KernelErrorCode = KRERR_CC_ERROR6;
981 return(KernelErrorCode);
982 }
983 if(counter == NoOfHiddenUnits) {
984 counter = 0;
985 }
986 break;
987 }
988 }
989 }
990 return( KernelErrorCode );
991 }
992
993
994
995
996
997
998