# TITLE: Maximum Flow Algorithm # AUTHOR: Roy F.A. Maclean # EMAIL: rfamgm at gmail # WEB: http://www.spiderpixel.co.uk/caspro # DATE: 17th Jan 2007 # MAKE: CASIO # MODEL: 9850 or later # #---------------------------------------------------------------------- # inputs: either Mat A or List 1,List 2,List 3,List 4 # # uses: List 5, List 6, List Ans, Mat C, vars: A,B,C,D,G,H,J,K,L,M,N,P # # outputs: Ans=Max flow, Mat B #---------------------------------------------------------------------- # # Reference: "Networks and Algorithms - An Introductory Approach" by Alan Dolan and Joan Aldous # # Instructions: # # Take a basic network with the nodes labelled sequentially from 1 to N # with the source as 1 and the sink as N. # Each arc will have a start node, an end node, a flow, and a capacity. # # Enter the data for each arc into the rows of Mat A, # or if you prefer, enter the list of start nodes into List 1, the end nodes into List 2, the flows into List 3 # and the capacities into List 4. # # If you want to start with a zero flow then the quickest way to enter this into List 3 is to type 0List 1->List 3 # while in Run mode, assuming you have already filled up List 1. # # The rows of data should be entered with the start nodes in descending order. # # Example: # # 1 2 0 40 # 1 3 0 70 # 1 4 0 30 # 2 3 0 15 # 2 5 0 50 # 3 2 0 15 # 3 4 0 20 # 3 5 0 20 # 4 6 0 24 # 4 7 0 40 # 5 6 0 22 # 5 8 0 36 # 6 7 0 12 # 6 8 0 48 # 7 6 0 18 # 7 8 0 60 # # # To use the program, run either MFLMAT or MFLLIST depending on whether you entered the data in Mat A or # in the lists. # # When the program is finished it displays the value of the maximum flow. Press EXE. Then Mat B will be displayed # with the third column containing the flow which has been found. # #------------------------------------------------------------------- # # Keys: # # <> not equals [shift][vars][f6][f3][f2] # => if..then arrow [shift][vars][f3][f3] # -> assignment arrow ( own button above the AC/on button ) # _ the display triangle [shift][vars][f5] # # List->Mat( [optn][f1][f2] # Mat->List( [optn][f2][f2] # #----------------------------------------------------------------------------------------------------------------------- @@ Program "MFLMAT" ClrText "COUNTING..." Mat A->Mat B Dim Mat B List Ans[1->M Seq(0,A,1,M,1->List 5 List->Mat(List 5)->Mat C 1->J:1->K For 1->D To M Mat B[D,1->L If L<>K Then J+1->J L->K IfEnd Next Seq(0,A,1,J,1->List 5 List 5->List 6 J+1->N 1->J:1->K For 1->D To M Mat B[D,1->L If L<>K Then J+1->J L->K D->List 5[J D-1->List 6[J-1 IfEnd Next 1->List 5[1 M->List 6[N-1 List 6 Prog "MFLLOOP" @@ Program "MFLLIST" ClrText "COUNTING..." Dim List 1->M List->Mat(List 1)->Mat C 1->J:1->K For 1->D To M List 1[D->L If L<>K Then J+1->J L->K IfEnd Next Seq(0,A,1,J,1->List 5 List 5->List 6 J+1->N 1->J:1->K For 1->D To M List 1[D->L If L<>K Then J+1->J L->K D->List 5[J D-1->List 6[J-1 IfEnd Next 1->List 5[1 M->List 6[N-1 List 6 List->Mat(List 1,List 2,List 3,List 4)->Mat B Prog "MFLLOOP" @@ Program "MFLLOOP" ClrText "SEARCHING..." 0->P Lbl 0 0List 6->List 6 1->A:1->J Lbl 1 1->List 6[A List 5[A]-1->D List Ans[A->C 0->G Do D+1->D Mat B[D,2->H Mat B[D,4]-Mat B[D,3->L L>0->G G=1=>H<>N=>List 6[H]=0->G:LpWhile (G=0) And (DGoto 2 A=1=>Goto 3 List 5[2]-1->D 0->F Do D+1->D Mat B[D,1->H Mat B[D,2]=A=>Mat B[D,3->L If L>0 Then If List 6[H]=0 Then (-)1->G Else 0->L:IfEnd:IfEnd LpWhile (G=0) And (DGoto 2 J-1->J If J=1 Then 1->A Else Mat C[J-1,1->D 2->C D<0=>1->C Mat B[Abs D,C->A IfEnd Goto 1 Lbl 2 H->A J<>1=>KK->L:L->K GD->Mat C[J,1 J+1->J A<>N=>Goto 1 P+1->P For 1->B To J-1 Mat C[B,1->D D/Abs D Abs D->D AnsL+Mat B[D,3->Mat B[D,3 Next ' 11 Spaces follows Locate 1,2," " Locate 1,2,Sum (Mat->List(Mat B,3)(Mat->List(Mat B,2)=N Goto 0 Lbl 3 If P=0 Then "NO NEW PATHS" Else ClrText "MAX FLOW =" Sum (Mat->List(Mat B,3)(Mat->List(Mat B,2)=N_ Mat B_ IfEnd "PRESS AC ON" "TO STOP" Lbl 4 Goto 4