3 gap: ha egy 0<i<n szint kiurul, az [i+1,n-1] szinten levoket felrakjuk az
4 n szintre, ezzel nem sertve a tavolsagcimke tulajdonsagot
6 highest label: a legnagyobb szintu aktivon pumpalunk (2 phase eseten
7 persze az n alattiak kozul a legnagyobb szintun)
9 bound_decrease: nem highest label. Egy b valtozoval lepegetunk lefele
10 mig 0-hoz erunk, amikor megemeljuk n-ig (vagy k-ig ha
11 az nyilvan volt tartva). Mindig egy b szintu aktivon
12 pumpalunk (ha van ilyen, ha nem: --b). Relabel utan tehat
13 nem megyunk a csucs utan, ot majd csak b ujboli felemelese utan
14 tudjuk pumpalni. Meglepoen hatekony.
16 highest label + bound_decrease: preflow.h-ban H0*n relabel-enkent a
17 bound_decrease, mig H1*n relabel-enkent a highest label valtozatot
18 futtatjuk az 1. fazisban (a masodik fazis igen gyors az elsohoz
19 kepest, igy itt sima highest label fut). Ez igen hatekonynak
20 tunik, ugy latszik, hogy egyesul a ket eljaras elonye. Teszteles
21 alapjan a H0=20, H1=1 valasztas elfogadhatonak tunik.
23 2 phase: az elso fazisban csak az [1,n-1] szintu aktivokon pumpalunk,
24 es alkalmazzuk gap-et. Ha alul nincs aktiv, fentrol kifujjuk
25 s-bol a fenti csucsokat a segedgraf egy vissza bfs-evel, es
26 visszacsurgatunk ugyanugy, mint az elso fazisban. Az elso fazis
27 utan az n. szint alatti csucsok egy min vagast adnak, es t
28 excesse a max folyamertek.
30 level_list: kezzel irunk egy listat minden szintre az ottani csucsokrol.
31 Ha meg egy k valtozoban nyilvantartjuk a legnagyobb nemures
32 szintet az [1,n] intervallumban, akkor nagyon gyorsan tudunk
33 gap eseten a gap feletti csucsokat az n szintre tenni. Ilyenkor
34 arra sincs szukseg (ami maskor igen hasznos), hogy nyilvantartsuk
35 melyik szinten hany csucs van.
40 max_flow.t tartalmazza a LEDA flowjait, a legutolso fuggveny,
41 MAX_FLOW_T a default. Semmi kulonoset nem csinal, 2 fazisu highest label,
42 gap eseten bfs-sel szivja fel a csucsokat az n szintre (ez igen rossz
43 megoldas suru grafnal). Nyilvan tartja az aktivokat egy valamilyen stackben,
44 es hogy melyik szinten hany pont van. 5*m lepesenkent (h=5 defaultbol)
45 csinal egy bfs-t vagy t-bol (1. fazis) vagy s-bol (2. fazis). Van benne
46 par rossz megoldas, pl. az elsorol a 2. fazisra valo atteresnel nem kell
51 Egy erdekes tapasztalat:
53 Meglepo modon nagyon sokat gyorsitott amikor az stl stack-jet kezzel
54 megirtam. Ez talan a G.id(NodeIt v) hatekonysaganak koszonheto.