examples/graphcol.log

   1 BLOCK\r
   2   UNIT BACKTRACK: CLASS;\r
   3     HIDDEN SE,ELEM,TOP;\r
   4     VAR  ROOT:NODE,SEARCH:SE,FOUND,OPT:NODE,\r
   5          NUMBER_OF_NODES,NUMBER_OF_LEAVES,NUMBER_OF_ANSWERS:INTEGER;\r
   6     \r
   7     UNIT NODE: COROUTINE(FATHER:NODE);\r
   8       VAR NSONS,LEVEL: INTEGER , DEADEND:BOOLEAN;\r
   9       UNIT VIRTUAL LEAF:  FUNCTION :BOOLEAN;\r
  10       END LEAF;\r
  11       UNIT VIRTUAL ANSWER :FUNCTION :BOOLEAN;\r
  12       END ANSWER;\r
  13       UNIT VIRTUAL LASTSON: FUNCTION : BOOLEAN;\r
  14       END LASTSON;\r
  15       UNIT VIRTUAL NEXTSON: FUNCTION : NODE;\r
  16       END NEXTSON;\r
  17       UNIT VIRTUAL EQUAL : FUNCTION (W:NODE):BOOLEAN;\r
  18       END EQUAL;\r
  19       UNIT VIRTUAL COST: FUNCTION :REAL;\r
  20       END COST;\r
  21     BEGIN\r
  22       IF FATHER =/= NONE\r
  23       THEN\r
  24         LEVEL:=FATHER.LEVEL+1\r
  25       ELSE\r
  26         LEVEL:=0\r
  27       FI;\r
  28     END NODE;\r
  29   \r
  30     UNIT OK: FUNCTION (V:NODE):BOOLEAN;\r
  31       VAR W:NODE;\r
  32     BEGIN\r
  33       IF V=NONE THEN RESULT:=FALSE; RETURN FI;\r
  34       RESULT:=TRUE; W:=V.FATHER;\r
  35       WHILE W =/= NONE\r
  36       DO\r
  37         IF V.EQUAL(W) THEN RESULT:=FALSE; RETURN FI;\r
  38         W:=W.FATHER\r
  39       OD\r
  40     END OK;\r
  41   \r
  42     UNIT PURGE: PROCEDURE (V:NODE);\r
  43       VAR W: NODE;\r
  44     BEGIN\r
  45       IF V=NONE THEN RETURN FI;\r
  46       DO\r
  47         W:=V.FATHER; KILL(V);\r
  48         IF W=NONE THEN RETURN FI;\r
  49         W.NSONS:=W.NSONS-1;\r
  50         IF W.NSONS =/= 0 THEN RETURN FI;\r
  51         V:=W\r
  52       OD;\r
  53     END PURGE;\r
  54 \r
  55     VAR TOP:ELEM;\r
  56 \r
  57     UNIT ELEM: CLASS (NEXT:ELEM, V:NODE);\r
  58     END ELEM;\r
  59  \r
  60     UNIT VIRTUAL INSERT: PROCEDURE(V:NODE);\r
  61     BEGIN\r
  62       TOP:=NEW ELEM(TOP,V); \r
  63     END INSERT;\r
  64   \r
  65     UNIT VIRTUAL DELETE: FUNCTION :NODE;\r
  66       VAR E:ELEM;\r
  67     BEGIN\r
  68       IF TOP =/= NONE\r
  69       THEN\r
  70         RESULT:=TOP.V; \r
  71         E:=TOP; TOP:=TOP.NEXT; KILL(E);\r
  72       FI; \r
  73     END DELETE;\r
  74   \r
  75     UNIT SE: COROUTINE ;\r
  76       VAR I:INTEGER,V,W:NODE;\r
  77     BEGIN\r
  78       RETURN; CALL INSERT(ROOT);\r
  79       DO\r
  80         V:=DELETE; \r
  81         IF V=NONE THEN EXIT FI;\r
  82         ATTACH(V); \r
  83         IF V.ANSWER\r
  84         THEN\r
  85           NUMBER_OF_ANSWERS:=NUMBER_OF_ANSWERS+1;\r
  86           FOUND:=V;\r
  87           IF OPT=NONE ORIF V.COST < OPT.COST\r
  88           THEN\r
  89              OPT:=V\r
  90           FI;\r
  91           DETACH;\r
  92           (* HERE THE USER OF BACKTRACK MAY UNDERTAKE SOME ACTIONS\r
  93              ON THE ANSWER NODES. IF NOT NECESSARY DO ATTACH      *) \r
  94         ELSE\r
  95           IF V.DEADEND\r
  96           THEN\r
  97             NUMBER_OF_LEAVES:=NUMBER_OF_LEAVES+1;\r
  98             CALL PURGE(V);\r
  99           ELSE\r
 100             DO\r
 101               W:=V.NEXTSON; V.NSONS:=V.NSONS+1;\r
 102               NUMBER_OF_NODES:=NUMBER_OF_NODES+1; \r
 103               IF OK(W)\r
 104               THEN \r
 105                 W.DEADEND:=W.LEAF; CALL INSERT(W);\r
 106               FI;\r
 107               IF V.LASTSON THEN EXIT FI;  \r
 108             OD;\r
 109           FI;\r
 110         FI;\r
 111       OD;\r
 112       FOUND:=NONE;\r
 113     END SE;\r
 114   \r
 115       \r
 116     UNIT KILLALL :PROCEDURE;\r
 117       VAR V:NODE;\r
 118     BEGIN\r
 119       DO\r
 120         V:=DELETE;\r
 121         IF V=NONE THEN RETURN FI;\r
 122         CALL PURGE(V);\r
 123       OD;\r
 124     END KILLALL;\r
 125 \r
 126   BEGIN\r
 127     SEARCH:=NEW SE;\r
 128     INNER;\r
 129     KILL(SEARCH); CALL KILLALL;\r
 130   END BACKTRACK;\r
 131  \r
 132  \r
 133   VAR N,M,I,J:INTEGER,H1,H2,H3:CHAR;\r
 134   VAR INC: ARRAYOF ARRAYOF BOOLEAN;  \r
 135   BEGIN \r
 136    DO\r
 137     WRITE(" NUMBER OF VERTICES= ");\r
 138     READLN(N);\r
 139     IF N=0 THEN EXIT FI;\r
 140     WRITE(" NUMBER OF COLOURS= ");\r
 141     READLN(M);\r
 142     ARRAY INC DIM (1:N);\r
 143     FOR I:=1 TO N DO ARRAY INC(I) DIM (1:I); OD;\r
 144     WRITELN(" GIVE A GRAPH BY DEFINING SUCCESSIVE EDGES");\r
 145     WRITELN(" TO END A LIST WRITE 0");\r
 146     FOR I:=1 TO N\r
 147     DO\r
 148       WRITELN(" VERTEX ",I:3," IS INCIDENT WITH VERTICES=");\r
 149       DO\r
 150         READ(J);\r
 151         IF J>1 AND J<=N THEN INC(J,I):=TRUE ELSE EXIT FI;\r
 152       OD;\r
 153       WRITELN(" END OF EDGES WITH VERTEX", I:3)\r
 154     OD;\r
 155     WRITELN(" GRAPH HAS THE FOLLOWING INCIDENCE MATRIX");\r
 156     FOR I:=1 TO N\r
 157     DO\r
 158       FOR J:=1 TO I\r
 159       DO\r
 160         IF INC(I,J) THEN WRITE(1:2) ELSE WRITE(0:2) FI;\r
 161       OD;\r
 162       WRITELN;\r
 163     OD;      \r
 164     PREF BACKTRACK BLOCK\r
 165     VAR K:INTEGER;\r
 166      UNIT STATE: NODE CLASS(I,J,NC:INTEGER);\r
 167      \r
 168          (*I- VERTEX, J-COLOUR, NC-NUMBER OF COLOURS *)\r
 169 \r
 170       UNIT VIRTUAL ANSWER: FUNCTION: BOOLEAN;\r
 171       BEGIN\r
 172         RESULT:= I=N AND OKGO(THIS STATE)\r
 173       END ANSWER;\r
 174  \r
 175       UNIT VIRTUAL LEAF: FUNCTION :BOOLEAN;\r
 176       BEGIN\r
 177         RESULT:=I=N OR NOT OKGO(THIS STATE)\r
 178       END LEAF;\r
 179   \r
 180       UNIT OKGO: FUNCTION(V:STATE) : BOOLEAN;\r
 181       VAR I,J:INTEGER;\r
 182       BEGIN\r
 183         I:=V.I; J:=V.J;\r
 184         DO\r
 185          V:=V.FATHER;\r
 186          IF V=NONE THEN RESULT:=TRUE; EXIT FI;\r
 187          IF V.J=J AND INC(I,V.I) THEN EXIT FI;\r
 188         OD;\r
 189       END OKGO;\r
 190 \r
 191         \r
 192       UNIT VIRTUAL LASTSON: FUNCTION :BOOLEAN;\r
 193       BEGIN\r
 194         IF K=M\r
 195         THEN\r
 196           RESULT:=TRUE;\r
 197           K:=0;\r
 198         FI; \r
 199       END LASTSON;\r
 200  \r
 201       UNIT VIRTUAL NEXTSON : FUNCTION :STATE;\r
 202       VAR V:STATE,NCK:INTEGER;\r
 203       BEGIN\r
 204         V:=THIS STATE;\r
 205         K:=K+1;\r
 206         NCK:=NC;\r
 207         DO\r
 208           IF V=NONE THEN NCK:=NCK+1; EXIT FI;\r
 209           IF V.J=K THEN EXIT FI;\r
 210           V:=V.FATHER;\r
 211         OD;        \r
 212         RESULT:=NEW STATE(THIS STATE,I+1,K,NCK);\r
 213      END NEXTSON;\r
 214 \r
 215       UNIT VIRTUAL EQUAL: FUNCTION(S:STATE):BOOLEAN;\r
 216       BEGIN\r
 217         RESULT:=I=S.I AND J=S.J\r
 218       END EQUAL;\r
 219   \r
 220       UNIT VIRTUAL COST: FUNCTION :REAL;\r
 221       BEGIN\r
 222         RESULT:=NC\r
 223       END COST;\r
 224           \r
 225                 \r
 226     BEGIN\r
 227       RETURN;\r
 228       DO\r
 229         DETACH   \r
 230       OD;\r
 231     END STATE;\r
 232 \r
 233         \r
 234     UNIT DISPLAY: PROCEDURE(V:STATE);\r
 235     BEGIN\r
 236       IF V=NONE THEN WRITELN(" NO SOLUTIONS"); RETURN FI;\r
 237       WRITELN("VERTEX       COLOUR");\r
 238       DO\r
 239         WRITE(V.I); WRITE("     "); WRITELN(V.J);\r
 240         V:=V.FATHER;\r
 241         IF V=NONE THEN EXIT FI \r
 242       OD;\r
 243       WRITELN;\r
 244     END DISPLAY;\r
 245     \r
 246     BEGIN\r
 247       READLN;\r
 248       ROOT:=NEW STATE(NONE,1,1,1); \r
 249       WRITE("DO YOU WANT TO OPTIMIZE ");\r
 250       WRITELN("OR TO PRINT ALL THE SOLUTIONS ?");\r
 251       WRITELN(" (ANSWER OPT OR ALL)");\r
 252       READLN(H1,H2,H3);\r
 253       IF H1='O' AND H2='P' AND H3='T'\r
 254       THEN\r
 255         DO\r
 256           ATTACH(SEARCH);\r
 257           IF FOUND=NONE THEN EXIT FI;\r
 258           IF OPT =/= NONE ANDIF OPT.COST<FOUND.COST\r
 259           THEN\r
 260             EXIT\r
 261           FI;  \r
 262         OD;\r
 263         IF OPT =/= NONE\r
 264         THEN\r
 265           CALL DISPLAY(OPT);\r
 266           WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);\r
 267           WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);\r
 268           WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);\r
 269         ELSE\r
 270           WRITELN("NO SOLUTIONS");\r
 271           WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);\r
 272           WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);\r
 273         FI;\r
 274       ELSE       \r
 275         IF H1='A' AND H2='L' AND H3='L'\r
 276         THEN\r
 277           DO\r
 278             ATTACH(SEARCH); \r
 279             CALL DISPLAY(FOUND);\r
 280             WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);\r
 281             WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);\r
 282             WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);\r
 283             IF FOUND=NONE THEN EXIT FI;\r
 284             WRITELN("DO YOU WANT TO CONTINUE?");\r
 285             READ(H1,H2);\r
 286             IF H1=/='Y' ORIF H2=/='E' THEN EXIT FI;\r
 287             READLN(H3);\r
 288             IF H3=/='S' THEN EXIT FI;\r
 289           OD;\r
 290         FI\r
 291       FI;\r
 292     END;\r
 293   OD;\r
 294 \r
 295    \r
 296    \r
 297   END;  \r
 298     \r
 299 END\r
 300 \r
 301   \r