COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/READ_FLOW @ 137:6364b07f8cd4

Last change on this file since 137:6364b07f8cd4 was 110:3c53698842dd, checked in by jacint, 20 years ago

leiras

File size: 2.4 KB
Line 
1   Heurisztikak:
2
3gap: 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
5
6highest label: a legnagyobb szintu aktivon pumpalunk (2 phase eseten
7        persze az n alattiak kozul a legnagyobb szintun)
8
9bound_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.
15
16highest 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.
22
232 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.
29
30level_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.
36
37
38    A LEDA flowja
39
40max_flow.t tartalmazza a LEDA flowjait, a legutolso fuggveny,
41MAX_FLOW_T a default. Semmi kulonoset nem csinal, 2 fazisu highest label,
42gap eseten bfs-sel szivja fel a csucsokat az n szintre (ez igen rossz
43megoldas suru grafnal). Nyilvan tartja az aktivokat egy valamilyen stackben,
44es hogy melyik szinten hany pont van. 5*m lepesenkent (h=5 defaultbol)
45csinal egy bfs-t vagy t-bol (1. fazis) vagy s-bol (2. fazis). Van benne
46par rossz megoldas, pl. az elsorol a 2. fazisra valo atteresnel nem kell
47egy bfs a t-bol.
48
49
50
51    Egy erdekes tapasztalat:
52
53Meglepo modon nagyon sokat gyorsitott amikor az stl stack-jet kezzel
54megirtam. Ez talan a G.id(NodeIt v) hatekonysaganak koszonheto.
55
Note: See TracBrowser for help on using the repository browser.