Critical Path Analysis (Model A)


Even if critical path analysis does not exactly excite you, this program can be used to find the longest or shortest route through a large maze. As dimensioned, it will handle a network of up to 50 nodes or junctions, each of which may have up to 5 outlets. The joining links can represent distance or time and the program will list all possible paths, or the longest path, or the one with most nodes. Loop back conditions are automatically rejected by the program. Draw your own network on paper and enter the separate link details in the DATA statements onwards. Then press the key sit back and watch the computer display the path analysis.

    1 REM *** BBC VERSION ***
    2 REM *** CRITICAL PATH ANALYSIS ***
   10 GOTO 500
   20 CRITICAL PATH ANALYSIS
   30 CONVERTED & MODIFIED FOR BBC MICRO
   40   BY Max Lang    25 June 1983
   50   :
   60   FROM A SPECTRUM PROGRAM BY
   70   MICHAEL BEWS
   80   :
   90   ROUTINE INDEX
  100   -------------
  110   MAIN PROGRAM:.....500
  120   INITIATE:........1000
  130   DATA:............1200
  140   DISPLAY:.........1500
  150   SEEK PATH:.......2000
  160   RECORD A PATH:...2200
  170   UPDATE:..........2300
  180   TITLE:..........10000
  190   WAIT:...........10200
  200   YN:.............10300
  210   SPACEBAR:.......10500
  220   ::::::::::::::::::::::::::::::::::
  500   REM MAIN PROGRAM
  510   MODE 7
  520   PROC_TITLE("CRITICAL PATH ANALYSIS",1
)
  530   PROC_INITIATE
  540   PROC_DATA
  550   MODE 4
  560   PROC_DISPLAY
  570   PRINT
  580   INPUT "Enter number of start node",ST
ART
  590   INPUT "Enter number of finish node",F
INISH
  600   PRINT
  610   NE(FINISH)=-1:REM SET NUMBER OF EXITS
 AT FINISH NODE TO -1
  620   PROC_SEEK_PATH(START)
  630   PRINT:PRINT "Number of paths from ";S
TART;" to ";FINISH;" =";TAB(33);TP
  640   IF TP=0 THEN GOTO 680
  650   PRINT:PRINT "Path No.";MNP;" has the 
most nodes =";TAB(33);MN
  660   PRINT:PRINT "Path No.";LP;" is the lo
ngest =";TAB(33);L
  670   PRINT:PRINT "Path No.";SP;" is the sh
ortest =";TAB(33);S
  680   VDU 26:REM RESTORE WINDOWS
  690   VDU 15:REM PAGE MODE OFF
  700   PRINT TAB(0,31);
  710   END
  720   ::::::::::::::::::::::::::::::::::
 1000   DEF PROC_INITIATE
 1010   DIM F(30,5): REM FINISH NODE(START,NO
DE,PATH NUMBER)
 1020   DIM L(30,5): REM LENGTH OF PATH(START
,NODE,PATH NUMBR)
 1030   DIM NE(30):  REM NUMBER OF EXITS(STAR
T NODE)
 1040   DIM FL(30):  REM FLAG OF NODE PASSED 
THROUGH(NODE NUMBER)
 1050   DIM P(30):   REM PATH FOLLOWED(ORDER 
OF NODES)
 1060   TP=0:        REM TOTAL NUMBER OF PATH
S FOUND
 1070   MNP=0:       REM PATH WITH MOST NODES
 1080   MN=0:        REM NUMBER OF NODES IN P
ATH WITH MOST NODES
 1090   PL=0:        REM LENGTH OF PATH FOLLO
W 1070
 1100   LP=0:        REM LONGEST PATH
 1110   L=0:         REM LENGTH OF LONGEST PA
TH
 1120   SP=0:        REM SHORTEST PATH
 1130   S=999999:    REM LENGTH OF SHORTEST P
ATH
 1140   NC=0:        REM NODE COUNTER
 1150   ENDPROC
 1160   ::::::::::::::::::::::::::::::::::
 1200   DEF PROC_DATA
 1210   RESTORE 1280
 1220   READ start,finish,length
 1230   IF start=-1 THEN ENDPROC
 1240   NE(start)=NE(start)+1
 1250   F(start,NE(start))=finish
 1260   L(start,NE(start))=length
 1270   GOTO 1220
 1280   DATA 1,4,4
 1290   DATA 1,2,2
 1300   DATA 1,3,4
 1310   DATA 1,8,11
 1320   DATA 2,3,1
 1330   DATA 2,5,3
 1340   DATA 3,7,5
 1350   DATA 4,5,1
 1360   DATA 5,6,1
 1370   DATA 6,7,2
 1380   DATA 6,11,7
 1390   DATA 7,8,0
 1400   DATA 7,12,11
 1410   DATA 8,9,3
 1420   DATA 8,10,3
 1430   DATA 9,10,2
 1440   DATA 10,12,9
 1450   DATA 11,12,3
 1460   DATA -1,-1,-1
 1470   ::::::::::::::::::::::::::::::::::
 1500   DEF PROC_DISPLAY
 1510   MOVE 0,825:DRAW 225,975:DRAW 425,875:
DRAW 500,975:DRAW 825,975:DRAW 1125,825
 1520   MOVE 0,825:DRAW 225,875:DRAW 425,750:
DRAW 550,875:DRAW 1125,825
 1530   MOVE 0,825:DRAW 625,575:DRAW 725,525:
DRAW 825,575:DRAW 1125,825
 1540   MOVE 0,825:DRAW 425,750
 1550   MOVE 625,575:DRAW 825,575
 1560   MOVE 225,875:DRAW 425,875
 1570   MOVE 500,975:DRAW 550,875
 1580   MOVE 550,875:DRAW 625,550
 1590   COLOUR0:COLOUR129
 1600   PRINTTAB(0,6)"1"
 1610   PRINTTAB(7,1)"4"
 1620   PRINTTAB(7,4)"2"
 1630   PRINTTAB(13,4)"5"
 1640   PRINTTAB(13,8)"3"
 1650   PRINTTAB(19,14)"8"
 1660   PRINTTAB(22,15)"9"
 1670   PRINTTAB(15,1)"6"
 1680   PRINTTAB(25,1)"11"
 1690   PRINTTAB(17,4)"7"
 1700   PRINTTAB(25,14)"10"
 1710   PRINTTAB(34,6)"12"
 1720   PRINTTAB(0,13)"NODE"
 1730   COLOUR1:COLOUR128
 1740   PRINTTAB(3,3)"4"
 1750   PRINTTAB(4,5)"2"
 1760   PRINTTAB(7,7)"4"
 1770   PRINTTAB(10,6)"1"
 1780   PRINTTAB(10,10)"11"
 1790   PRINTTAB(10,2)"1"
 1800   PRINTTAB(10,4)"3"
 1810   PRINTTAB(14,3)"1"
 1820   PRINTTAB(16,3)"2"
 1830   PRINTTAB(15,6)"5"
 1840   PRINTTAB(20,1)"7"
 1850   PRINTTAB(18,9)"0"
 1860   PRINTTAB(24,5)"11"
 1870   PRINTTAB(22,13)"3"
 1880   PRINTTAB(20,15)"3"
 1890   PRINTTAB(24,15)"2"
 1900   PRINTTAB(30,10)"9"
 1910   PRINTTAB(30,3)"3"
 1920   PRINTTAB(30,13)"LENGTH"
 1930   VDU 28,0,31,39,17
 1940   VDU 14
 1950   ENDPROC
 1960   ::::::::::::::::::::::::::::::::::
 1970   DEF PROC_SEEK_PATH(NODE)
 2000   DEF PROC_SEEK_PATH(NODE)
 2010   FL(NODE)=1
 2020   NC=NC+1
 2030   P(NC)=NODE
 2040   LOCAL C
 2050   C=0
 2060   REPEAT
 2070     C=C+1
 2080     PL=PL+L(NODE,C)
 2090     IF NE(F(NODE,C))<0 THEN PROC_RECORD
_PATH:GOTO 2120
 2100     IF NE(F(NODE,C))=0 THEN GOTO 2120
 2110     IF FL(F(NODE,C))<>1 THEN PROC_SEEK_
PATH(F(NODE,C))
 2120     PL=PL-L(NODE,C)
 2130   UNTIL C=NE(NODE)
 2140   FL(NODE)=0
 2150   P(NC)=0
 2160   NC=NC-1
 2170   ENDPROC
 2180   ::::::::::::::::::::::::::::::::::
 2200   DEF PROC_RECORD_PATH
 2210   TP=TP+1
 2220   PRINT;TP;")";TAB(4);
 2230   Z=0
 2240   Z=Z+1
 2250   IF P(Z)=0 THEN PRINT;FINISH:PROC_UPDA
TE:ENDPROC
 2260   PRINT ;P(Z);",";
 2270   GOTO 2240
 2280   ::::::::::::::::::::::::::::::::::
 2300   DEF PROC_UPDATE
 2310   IF MN<Z THEN MN=Z:MNP=TP
 2320   IF L<PL THEN L=PL:LP=TP
 2330   IF S>PL THEN S=PL:SP=TP
 2340   ENDPROC
 2350   ::::::::::::::::::::::::::::::::::
 2400   DEF PROC_INSTRUCT
 2410   CLS
 2420   PRINT "CRITICAL PATH ANALYSIS"
 2430   PRINT "----------------------"
 2440   PRINT:PRINT "Critical Path Analysis c
an be applied   wherever several inter-depend
ent        activities need to be carried out 
in a  specified sequence to achieve a final  
 goal."
 2450   PRINT:PRINT "The goal might be the co
mpletion of a   large project or, more simply
, arrival  at a distant metro station by the 
      shortest possible route."
 2460   PRINT:PRINT "This program is suitable
 for use in     either case."
 2470   PRINT:PRINT "A demonstration network 
is shown and theprogram will trace out all po
ssible     paths through the network, indicat
ing   the longest and shortest routes."
 2480   PROC_SPACEBAR
 2490   ENDPROC
 2500   ::::::::::::::::::::::::::::::::::
10000   DEF PROC_TITLE(T$,I):REM I=0 - NO INS
TRUCTION OPTION, I=1 - OPTION
10010   CLS
10020   PRINT TAB(1,1)"Max Lang"
10030   PRINTTAB(19-LEN(T$)/2,10)CHR$(141);T$
10040   PRINTTAB(19-LEN(T$)/2,11)CHR$(141);T$
10050   PROC_WAIT(150)
10060   IF I=0 THEN ENDPROC
10070   PRINT TAB(0,22)"Do you require instru
ctions ? ";
10080   PROC_YN
10090   IF YES THEN PRINT "Yes"; ELSE PRINT "
No";
10100   PROC_WAIT(150)
10110   IF YES THEN PROC_INSTRUCT
10120   ENDPROC
10130   ::::::::::::::::::::::::::::::::::
10200   DEF PROC_WAIT(T)
10210   LOCAL NOW
10220   NOW=TIME
10230   REPEAT
10240   UNTIL TIME=NOW+T
10250   ENDPROC
10260   ::::::::::::::::::::::::::::::::::
10300   DEF PROC_YN
10310   *FX21,0
10320   LOCAL G
10330   REPEAT
10340     G=GET
10350     G=G+32*(G>95): REM CONVERT TO CAPIT
ALS
10360     YES=(G=89)
10370     NO=(G=78)
10380   UNTIL YES OR NO
10390   ENDPROC
10400   ::::::::::::::::::::::::::::::::::
10500   DEF PROC_SPACEBAR
10510   PRINT TAB(0,23)"Press SPACEBAR to con
tinue.";
10520   LOCAL G
10530   *FX21,0
10540   REPEAT
10550     G=GET
10560   UNTIL G=32
10570   CLS
10580   ENDPROC
10590   ::::::::::::::::::::::::::::::::::