1.1 --- a/src/work/jacint/README_FLOW Sat Mar 20 19:39:42 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,55 +0,0 @@
1.4 - Heurisztikak:
1.5 -
1.6 -gap: ha egy 0<i<n szint kiurul, az [i+1,n-1] szinten levoket felrakjuk az
1.7 - n szintre, ezzel nem sertve a tavolsagcimke tulajdonsagot
1.8 -
1.9 -highest label: a legnagyobb szintu aktivon pumpalunk (2 phase eseten
1.10 - persze az n alattiak kozul a legnagyobb szintun)
1.11 -
1.12 -bound_decrease: nem highest label. Egy b valtozoval lepegetunk lefele
1.13 - mig 0-hoz erunk, amikor megemeljuk n-ig (vagy k-ig ha
1.14 - az nyilvan volt tartva). Mindig egy b szintu aktivon
1.15 - pumpalunk (ha van ilyen, ha nem: --b). Relabel utan tehat
1.16 - nem megyunk a csucs utan, ot majd csak b ujboli felemelese utan
1.17 - tudjuk pumpalni. Meglepoen hatekony.
1.18 -
1.19 -highest label + bound_decrease: preflow.h-ban H0*n relabel-enkent a
1.20 - bound_decrease, mig H1*n relabel-enkent a highest label valtozatot
1.21 - futtatjuk az 1. fazisban (a masodik fazis igen gyors az elsohoz
1.22 - kepest, igy itt sima highest label fut). Ez igen hatekonynak
1.23 - tunik, ugy latszik, hogy egyesul a ket eljaras elonye. Teszteles
1.24 - alapjan a H0=20, H1=1 valasztas elfogadhatonak tunik.
1.25 -
1.26 -2 phase: az elso fazisban csak az [1,n-1] szintu aktivokon pumpalunk,
1.27 - es alkalmazzuk gap-et. Ha alul nincs aktiv, fentrol kifujjuk
1.28 - s-bol a fenti csucsokat a segedgraf egy vissza bfs-evel, es
1.29 - visszacsurgatunk ugyanugy, mint az elso fazisban. Az elso fazis
1.30 - utan az n. szint alatti csucsok egy min vagast adnak, es t
1.31 - excesse a max folyamertek.
1.32 -
1.33 -level_list: kezzel irunk egy listat minden szintre az ottani csucsokrol.
1.34 - Ha meg egy k valtozoban nyilvantartjuk a legnagyobb nemures
1.35 - szintet az [1,n] intervallumban, akkor nagyon gyorsan tudunk
1.36 - gap eseten a gap feletti csucsokat az n szintre tenni. Ilyenkor
1.37 - arra sincs szukseg (ami maskor igen hasznos), hogy nyilvantartsuk
1.38 - melyik szinten hany csucs van.
1.39 -
1.40 -
1.41 - A LEDA flowja
1.42 -
1.43 -max_flow.t tartalmazza a LEDA flowjait, a legutolso fuggveny,
1.44 -MAX_FLOW_T a default. Semmi kulonoset nem csinal, 2 fazisu highest label,
1.45 -gap eseten bfs-sel szivja fel a csucsokat az n szintre (ez igen rossz
1.46 -megoldas suru grafnal). Nyilvan tartja az aktivokat egy valamilyen stackben,
1.47 -es hogy melyik szinten hany pont van. 5*m lepesenkent (h=5 defaultbol)
1.48 -csinal egy bfs-t vagy t-bol (1. fazis) vagy s-bol (2. fazis). Van benne
1.49 -par rossz megoldas, pl. az elsorol a 2. fazisra valo atteresnel nem kell
1.50 -egy bfs a t-bol.
1.51 -
1.52 -
1.53 -
1.54 - Egy erdekes tapasztalat:
1.55 -
1.56 -Meglepo modon nagyon sokat gyorsitott amikor az stl stack-jet kezzel
1.57 -megirtam. Ez talan a G.id(NodeIt v) hatekonysaganak koszonheto.
1.58 -
2.1 --- a/src/work/jacint/dijkstra.h Sat Mar 20 19:39:42 2004 +0000
2.2 +++ b/src/work/jacint/dijkstra.h Sat Mar 20 20:06:23 2004 +0000
2.3 @@ -80,7 +80,7 @@
2.4 while ( !heap.empty() ) {
2.5
2.6 Node v=heap.top();
2.7 - T oldvalue=heap[v];
2.8 + T oldvalue=heap.get(v);
2.9 heap.pop();
2.10 distance.set(v, oldvalue);
2.11 scanned.set(v,true);
2.12 @@ -94,7 +94,7 @@
2.13 reach.set(w,true);
2.14 heap.push(w,oldvalue+length[e]);
2.15 predecessor.set(w,e);
2.16 - } else if ( oldvalue+length[e] < heap[w] ) {
2.17 + } else if ( oldvalue+length[e] < heap.get(w) ) {
2.18 predecessor.set(w,e);
2.19 heap.decrease(w, oldvalue+length[e]);
2.20 }
3.1 --- a/src/work/jacint/fib_heap.h Sat Mar 20 19:39:42 2004 +0000
3.2 +++ b/src/work/jacint/fib_heap.h Sat Mar 20 20:06:23 2004 +0000
3.3 @@ -143,20 +143,20 @@
3.4 }
3.5
3.6
3.7 -
3.8 -
3.9 PrioType& operator[](const Item& it) {
3.10 return container[iimap[it]].prio;
3.11 }
3.12 +
3.13
3.14 const PrioType& operator[](const Item& it) const {
3.15 return container[iimap[it]].prio;
3.16 }
3.17
3.18 -// const PrioType get(const Item& it) const {
3.19 -// return container[iimap[it]].prio;
3.20 -// }
3.21
3.22 + const PrioType get(const Item& it) const {
3.23 + return container[iimap[it]].prio;
3.24 + }
3.25 +
3.26 void pop() {
3.27 /*The first case is that there are only one root.*/
3.28 if ( container[minimum].left_neighbor==minimum ) {
4.1 --- a/src/work/jacint/makefile Sat Mar 20 19:39:42 2004 +0000
4.2 +++ b/src/work/jacint/makefile Sat Mar 20 20:06:23 2004 +0000
4.3 @@ -1,6 +1,6 @@
4.4 CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
4.5 CXX2 = g++-2.95
4.6 -CXXFLAGS = -W -Wall -ansi -pedantic
4.7 +CXXFLAGS = -W -Wall -ansi -pedantic -O3 -I. -I.. -I../marci -I../alpar -I../../include
4.8 LEDAROOT ?= /ledasrc/LEDA-4.1
4.9
4.10 BINARIES = dijkstra prim preflow
4.11 @@ -11,13 +11,13 @@
4.12 sinclude .depend
4.13
4.14 preflow:
4.15 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o preflow preflow.cc
4.16 + $(CXX3) $(CXXFLAGS) -o preflow preflow.cc
4.17
4.18 dijkstra:
4.19 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o dijkstra dijkstra.cc
4.20 + $(CXX3) $(CXXFLAGS) -o dijkstra dijkstra.cc
4.21
4.22 prim:
4.23 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o prim prim.cc
4.24 + $(CXX3) $(CXXFLAGS) -o prim prim.cc
4.25
4.26 clean:
4.27 $(RM) *.o $(BINARIES) .depend
5.1 --- a/src/work/jacint/preflow.cc Sat Mar 20 19:39:42 2004 +0000
5.2 +++ b/src/work/jacint/preflow.cc Sat Mar 20 20:06:23 2004 +0000
5.3 @@ -1,6 +1,7 @@
5.4 #include <iostream>
5.5 #include <fstream>
5.6
5.7 +#include <smart_graph.h>
5.8 #include <list_graph.h>
5.9 #include <dimacs.h>
5.10 #include <preflow.h>
5.11 @@ -11,12 +12,12 @@
5.12 // Use a DIMACS max flow file as stdin.
5.13 // read_dimacs_demo < dimacs_max_flow_file
5.14 int main(int, char **) {
5.15 - typedef ListGraph::Node Node;
5.16 - typedef ListGraph::EdgeIt EdgeIt;
5.17 + typedef SmartGraph::Node Node;
5.18 + typedef SmartGraph::EdgeIt EdgeIt;
5.19
5.20 - ListGraph G;
5.21 + SmartGraph G;
5.22 Node s, t;
5.23 - ListGraph::EdgeMap<int> cap(G);
5.24 + SmartGraph::EdgeMap<int> cap(G);
5.25 readDimacsMaxFlow(std::cin, G, s, t, cap);
5.26
5.27 std::cout << "preflow demo ..." << std::endl;
5.28 @@ -24,40 +25,40 @@
5.29 double mintime=1000000;
5.30
5.31 for ( int i=1; i!=11; ++i ) {
5.32 - ListGraph::EdgeMap<int> flow(G);
5.33 + SmartGraph::EdgeMap<int> flow(G);
5.34 double pre_time=currTime();
5.35 - Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
5.36 + Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow);
5.37 max_flow_test.run();
5.38 double post_time=currTime();
5.39 if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
5.40 }
5.41
5.42 - ListGraph::EdgeMap<int> flow(G);
5.43 - Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
5.44 + SmartGraph::EdgeMap<int> flow(G);
5.45 + Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow);
5.46 max_flow_test.run();
5.47
5.48 - ListGraph::NodeMap<bool> cut(G);
5.49 + SmartGraph::NodeMap<bool> cut(G);
5.50 max_flow_test.minCut(cut);
5.51 int min_cut_value=0;
5.52 EdgeIt e;
5.53 for(G.first(e); G.valid(e); G.next(e)) {
5.54 - if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
5.55 + if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=cap[e];
5.56 }
5.57
5.58 - ListGraph::NodeMap<bool> cut1(G);
5.59 + SmartGraph::NodeMap<bool> cut1(G);
5.60 max_flow_test.minMinCut(cut1);
5.61 int min_min_cut_value=0;
5.62 for(G.first(e); G.valid(e); G.next(e)) {
5.63 - if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
5.64 - min_min_cut_value+=cap.get(e);
5.65 + if (cut[G.tail(e)] && !cut[G.head(e)])
5.66 + min_min_cut_value+=cap[e];
5.67 }
5.68
5.69 - ListGraph::NodeMap<bool> cut2(G);
5.70 + SmartGraph::NodeMap<bool> cut2(G);
5.71 max_flow_test.maxMinCut(cut2);
5.72 int max_min_cut_value=0;
5.73 for(G.first(e); G.valid(e); G.next(e)) {
5.74 - if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
5.75 - max_min_cut_value+=cap.get(e);
5.76 + if (cut2[G.tail(e)] && !cut2[G.head(e)])
5.77 + max_min_cut_value+=cap[e];
5.78 }
5.79
5.80 std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
6.1 --- a/src/work/jacint/prim.cc Sat Mar 20 19:39:42 2004 +0000
6.2 +++ b/src/work/jacint/prim.cc Sat Mar 20 20:06:23 2004 +0000
6.3 @@ -1,6 +1,7 @@
6.4 #include <iostream>
6.5 #include <fstream>
6.6
6.7 +#include <smart_graph.h>
6.8 #include <list_graph.h>
6.9 #include <dimacs.h>
6.10 #include <prim.h>
6.11 @@ -12,18 +13,18 @@
6.12 using namespace hugo;
6.13
6.14 int main(int, char **) {
6.15 - typedef ListGraph::Node Node;
6.16 + typedef SmartGraph::Node Node;
6.17
6.18 - ListGraph G;
6.19 + SmartGraph G;
6.20 Node s, t;
6.21 - ListGraph::EdgeMap<int> cap(G);
6.22 + SmartGraph::EdgeMap<int> cap(G);
6.23 readDimacsMaxFlow(std::cin, G, s, t, cap);
6.24
6.25 std::cout << "prim demo ..." << std::endl;
6.26
6.27 double pre_time=currTime();
6.28 - Prim<ListGraph, int, FibHeap<ListGraph::Node, int,
6.29 - ListGraph::NodeMap<int> > > prim_test(G, cap);
6.30 + Prim<SmartGraph, int, FibHeap<SmartGraph::Node, int,
6.31 + SmartGraph::NodeMap<int> > > prim_test(G, cap);
6.32 prim_test.run();
6.33 double post_time=currTime();
6.34
6.35 @@ -31,8 +32,8 @@
6.36 << post_time-pre_time << " sec"<< std::endl;
6.37
6.38 pre_time=currTime();
6.39 - Prim<ListGraph, int, BinHeap<ListGraph::Node, int,
6.40 - ListGraph::NodeMap<int> > > prim_test2(G, cap);
6.41 + Prim<SmartGraph, int, BinHeap<SmartGraph::Node, int,
6.42 + SmartGraph::NodeMap<int> > > prim_test2(G, cap);
6.43 prim_test2.run();
6.44 post_time=currTime();
6.45