comp :- consult('GaleRyser.pl').

:- consult('lib.pl').

:- nl,write('**************************************************************'),nl,nl,
   write('Dieses Programm produziert eine 5x5 Matrix mit 0-1-Eintraegen,'),nl,
   write('so dass die Zeilensummen 5,3,3,2,2, und die Spaltensummen'),nl,
   write('4,4,4,2,1 ergeben. Um eine solche Matrix zu erhalten, muss'),nl,
   write('"mach_matrix." eingegeben werden.'),nl,nl,
   write('Um eine 0-1-Matrix bezueglich anderen Partitionen zu erhalten,'),nl,
   write('muss das Programm entsprechend geaendert werden und zwar im'),nl,
   write('Teil, wo das Praedikat "kante" definiert wird. Dort werden'),nl,
   write('zuerst die "Zeilenzufluesse" (in diesem Fall 5,3,2,2) und'),nl,
   write('dann die "Spaltenabfluesse definiert (in diesem Fall 4,4,4,'),nl,
   write('2,1), danach werden die Kanten in der Matrix definiert. Falls'),nl,
   write('auch die Dimension der Matrix (in diesem Falle 5x5) geaendert'),nl,
   write('wird, so muss zusaetzlich die Ausgabe beim Praedikat "max_fluss"'),nl,
   write('geaendert werden.'),nl,nl,
   write('**************************************************************'),nl,nl. 

kante(s,l1,5).
kante(s,l2,3).
kante(s,l3,3).
kante(s,l4,2).
kante(s,l5,2).

kante(m1,t,4).
kante(m2,t,4).
kante(m3,t,4).
kante(m4,t,2).
kante(m5,t,1).

kante(l1,m1,1).
kante(l1,m2,1).
kante(l1,m3,1).
kante(l1,m4,1).
kante(l1,m5,1).
kante(l2,m1,1).
kante(l2,m2,1).
kante(l2,m3,1).
kante(l2,m4,1).
kante(l2,m5,1).
kante(l3,m1,1).
kante(l3,m2,1).
kante(l3,m3,1).
kante(l3,m4,1).
kante(l3,m5,1).
kante(l4,m1,1).
kante(l4,m2,1).
kante(l4,m3,1).
kante(l4,m4,1).
kante(l4,m5,1).
kante(l5,m1,1).
kante(l5,m2,1).
kante(l5,m3,1).
kante(l5,m4,1).
kante(l5,m5,1).

scho_gmacht(0).
create:- scho_gmacht(1).
create:- kante(V1,V2,_),assertz(fluss(V1,V2,0)),fail.
create:- asserta(scho_gmacht(1)).

weg(V1,V3,L):- L=[V1|Rest],kante(V1,V2,B),
               fluss(V1,V2,F1),FF is B-F1,FF > 0,
               Rest=[V2|_],weg([V1],V2,V3,Rest).

weg(_,V,V,[V]).
weg(V1,V3,L):- L=[V1|Rest],kante(V2,V1,_),
               fluss(V2,V1,F1),F1 > 0,
               Rest=[V2|_],weg([V1],V2,V3,Rest).
weg(L1,V1,V3,L):- L=[V1|Rest],kante(V1,V2,B),
               fluss(V1,V2,F1),FF is B-F1,FF > 0,
               nit(in_list(V2,L1)),
               Rest=[V2|_],append_list([V2],L1,L2),weg(L2,V2,V3,Rest).
weg(L1,V1,V3,L):- L=[V1|Rest],kante(V2,V1,_),
               fluss(V2,V1,F1),F1 > 0,
               nit(in_list(V2,L1)),
               Rest=[V2|_],append_list([V2],L1,L2),weg(L2,V2,V3,Rest).

mach_matrix:- create, max_fluss.

max_fluss:- fluss_durch_weg(F,L),erhoehe(F,L),
            fail.
max_fluss:- nl,
            fluss(l1,m1,F11),write(F11),
            fluss(l1,m2,F12),write(F12),
            fluss(l1,m3,F13),write(F13),
            fluss(l1,m4,F14),write(F14),
            fluss(l1,m5,F15),write(F15),nl,
            fluss(l2,m1,F21),write(F21),
            fluss(l2,m2,F22),write(F22),
            fluss(l2,m3,F23),write(F23),
            fluss(l2,m4,F24),write(F24),
            fluss(l2,m5,F25),write(F25),nl,
            fluss(l3,m1,F31),write(F31),
            fluss(l3,m2,F32),write(F32),
            fluss(l3,m3,F33),write(F33),
            fluss(l3,m4,F34),write(F34),
            fluss(l3,m5,F35),write(F35),nl,
            fluss(l4,m1,F41),write(F41),
            fluss(l4,m2,F42),write(F42),
            fluss(l4,m3,F43),write(F43),
            fluss(l4,m4,F44),write(F44),
            fluss(l4,m5,F45),write(F45),nl,
            fluss(l5,m1,F51),write(F51),
            fluss(l5,m2,F52),write(F52),
            fluss(l5,m3,F53),write(F53),
            fluss(l5,m4,F54),write(F54),
            fluss(l5,m5,F55),write(F55),nl.
            
erhoehe(F,L):- L=[V1|Rest],Rest=[V2|_],
               fluss(V1,V2,F1),retract(fluss(V1,V2,F1)),
               FF is F1+F, asserta(fluss(V1,V2,FF)),
               erhoehe(F,Rest).
erhoehe(F,L):- L=[V1|Rest],Rest=[V2|_],
               fluss(V2,V1,F1),retract(fluss(V2,V1,F1)),
               FF is F1-F, asserta(fluss(V2,V1,FF)),
               erhoehe(F,Rest).
erhoehe(_,L):- L=[t].

fluss_durch_weg(F,L):- weg(s,t,L),minimum(L,F),F>0.

minimum(L,F):- L=[V1|Rest],Rest=[V2|_],kante(V1,V2,B),
               fluss(V1,V2,F1),FF is B-F1, minimum(Rest,F2),
               min(F2,FF,F).
minimum(L,F):- L=[V1|Rest],Rest=[V2|_],kante(V2,V1,_),
               fluss(V2,V1,F1), minimum(Rest,F2),
               min(F2,F1,F).
minimum(L,F):- L=[V|[t]],kante(V,t,B),
               fluss(V,t,F1),F is B-F1.

/* EOF */