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