1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/jacint/README_FLOW Mon Mar 01 17:24:34 2004 +0000
1.3 @@ -0,0 +1,55 @@
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/READ_FLOW Mon Mar 01 16:32:50 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,55 +0,0 @@
2.4 - Heurisztikak:
2.5 -
2.6 -gap: ha egy 0<i<n szint kiurul, az [i+1,n-1] szinten levoket felrakjuk az
2.7 - n szintre, ezzel nem sertve a tavolsagcimke tulajdonsagot
2.8 -
2.9 -highest label: a legnagyobb szintu aktivon pumpalunk (2 phase eseten
2.10 - persze az n alattiak kozul a legnagyobb szintun)
2.11 -
2.12 -bound_decrease: nem highest label. Egy b valtozoval lepegetunk lefele
2.13 - mig 0-hoz erunk, amikor megemeljuk n-ig (vagy k-ig ha
2.14 - az nyilvan volt tartva). Mindig egy b szintu aktivon
2.15 - pumpalunk (ha van ilyen, ha nem: --b). Relabel utan tehat
2.16 - nem megyunk a csucs utan, ot majd csak b ujboli felemelese utan
2.17 - tudjuk pumpalni. Meglepoen hatekony.
2.18 -
2.19 -highest label + bound_decrease: preflow.h-ban H0*n relabel-enkent a
2.20 - bound_decrease, mig H1*n relabel-enkent a highest label valtozatot
2.21 - futtatjuk az 1. fazisban (a masodik fazis igen gyors az elsohoz
2.22 - kepest, igy itt sima highest label fut). Ez igen hatekonynak
2.23 - tunik, ugy latszik, hogy egyesul a ket eljaras elonye. Teszteles
2.24 - alapjan a H0=20, H1=1 valasztas elfogadhatonak tunik.
2.25 -
2.26 -2 phase: az elso fazisban csak az [1,n-1] szintu aktivokon pumpalunk,
2.27 - es alkalmazzuk gap-et. Ha alul nincs aktiv, fentrol kifujjuk
2.28 - s-bol a fenti csucsokat a segedgraf egy vissza bfs-evel, es
2.29 - visszacsurgatunk ugyanugy, mint az elso fazisban. Az elso fazis
2.30 - utan az n. szint alatti csucsok egy min vagast adnak, es t
2.31 - excesse a max folyamertek.
2.32 -
2.33 -level_list: kezzel irunk egy listat minden szintre az ottani csucsokrol.
2.34 - Ha meg egy k valtozoban nyilvantartjuk a legnagyobb nemures
2.35 - szintet az [1,n] intervallumban, akkor nagyon gyorsan tudunk
2.36 - gap eseten a gap feletti csucsokat az n szintre tenni. Ilyenkor
2.37 - arra sincs szukseg (ami maskor igen hasznos), hogy nyilvantartsuk
2.38 - melyik szinten hany csucs van.
2.39 -
2.40 -
2.41 - A LEDA flowja
2.42 -
2.43 -max_flow.t tartalmazza a LEDA flowjait, a legutolso fuggveny,
2.44 -MAX_FLOW_T a default. Semmi kulonoset nem csinal, 2 fazisu highest label,
2.45 -gap eseten bfs-sel szivja fel a csucsokat az n szintre (ez igen rossz
2.46 -megoldas suru grafnal). Nyilvan tartja az aktivokat egy valamilyen stackben,
2.47 -es hogy melyik szinten hany pont van. 5*m lepesenkent (h=5 defaultbol)
2.48 -csinal egy bfs-t vagy t-bol (1. fazis) vagy s-bol (2. fazis). Van benne
2.49 -par rossz megoldas, pl. az elsorol a 2. fazisra valo atteresnel nem kell
2.50 -egy bfs a t-bol.
2.51 -
2.52 -
2.53 -
2.54 - Egy erdekes tapasztalat:
2.55 -
2.56 -Meglepo modon nagyon sokat gyorsitott amikor az stl stack-jet kezzel
2.57 -megirtam. Ez talan a G.id(NodeIt v) hatekonysaganak koszonheto.
2.58 -
3.1 --- a/src/work/jacint/dijkstra.hh Mon Mar 01 16:32:50 2004 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,192 +0,0 @@
3.4 -/*
3.5 - *dijkstra
3.6 - *by jacint
3.7 - *Performs Dijkstra's algorithm from Node s.
3.8 - *
3.9 - *Constructor:
3.10 - *
3.11 - *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance)
3.12 - *
3.13 - *
3.14 - *
3.15 - *Member functions:
3.16 - *
3.17 - *void run()
3.18 - *
3.19 - * The following function should be used after run() was already run.
3.20 - *
3.21 - *
3.22 - *T dist(NodeIt v) : returns the distance from s to v.
3.23 - * It is 0 if v is not reachable from s.
3.24 - *
3.25 - *
3.26 - *EdgeIt pred(NodeIt v)
3.27 - * Returns the last Edge of a shortest s-v path.
3.28 - * Returns an invalid iterator if v=s or v is not
3.29 - * reachable from s.
3.30 - *
3.31 - *
3.32 - *bool reach(NodeIt v) : true if v is reachable from s
3.33 - *
3.34 - *
3.35 - *
3.36 - *
3.37 - *
3.38 - *Problems:
3.39 - *
3.40 - *Heap implementation is needed, because the priority queue of stl
3.41 - *does not have a mathod for key-decrease, so we had to use here a
3.42 - *g\'any solution.
3.43 - *
3.44 - *The implementation of infinity would be desirable, see after line 100.
3.45 - */
3.46 -
3.47 -#ifndef DIJKSTRA_HH
3.48 -#define DIJKSTRA_HH
3.49 -
3.50 -#include <queue>
3.51 -#include <algorithm>
3.52 -
3.53 -#include <marci_graph_traits.hh>
3.54 -#include <marciMap.hh>
3.55 -
3.56 -
3.57 -namespace std {
3.58 - namespace hugo {
3.59 -
3.60 -
3.61 -
3.62 -
3.63 -
3.64 - template <typename graph_type, typename T>
3.65 - class dijkstra{
3.66 - typedef typename graph_traits<graph_type>::NodeIt NodeIt;
3.67 - typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
3.68 - typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
3.69 - typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
3.70 - typedef typename graph_traits<graph_type>::OutEdgeIt OutEdgeIt;
3.71 -
3.72 -
3.73 - graph_type& G;
3.74 - NodeIt s;
3.75 - NodeMap<graph_type, EdgeIt> predecessor;
3.76 - NodeMap<graph_type, T> distance;
3.77 - EdgeMap<graph_type, T> length;
3.78 - NodeMap<graph_type, bool> reached;
3.79 -
3.80 - public :
3.81 -
3.82 - /*
3.83 - The distance of all the Nodes is 0.
3.84 - */
3.85 - dijkstra(graph_type& _G, NodeIt _s, EdgeMap<graph_type, T>& _length) :
3.86 - G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { }
3.87 -
3.88 -
3.89 -
3.90 - /*By Misi.*/
3.91 - struct Node_dist_comp
3.92 - {
3.93 - NodeMap<graph_type, T> &d;
3.94 - Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {}
3.95 -
3.96 - bool operator()(const NodeIt& u, const NodeIt& v) const
3.97 - { return d.get(u) < d.get(v); }
3.98 - };
3.99 -
3.100 -
3.101 -
3.102 - void run() {
3.103 -
3.104 - NodeMap<graph_type, bool> scanned(G, false);
3.105 - std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp>
3.106 - heap(( Node_dist_comp(distance) ));
3.107 -
3.108 - heap.push(s);
3.109 - reached.put(s, true);
3.110 -
3.111 - while (!heap.empty()) {
3.112 -
3.113 - NodeIt v=heap.top();
3.114 - heap.pop();
3.115 -
3.116 -
3.117 - if (!scanned.get(v)) {
3.118 -
3.119 - for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
3.120 - NodeIt w=G.head(e);
3.121 -
3.122 - if (!scanned.get(w)) {
3.123 - if (!reached.get(w)) {
3.124 - reached.put(w,true);
3.125 - distance.put(w, distance.get(v)-length.get(e));
3.126 - predecessor.put(w,e);
3.127 - } else if (distance.get(v)-length.get(e)>distance.get(w)) {
3.128 - distance.put(w, distance.get(v)-length.get(e));
3.129 - predecessor.put(w,e);
3.130 - }
3.131 -
3.132 - heap.push(w);
3.133 -
3.134 - }
3.135 -
3.136 - }
3.137 - scanned.put(v,true);
3.138 -
3.139 - } // if (!scanned.get(v))
3.140 -
3.141 -
3.142 -
3.143 - } // while (!heap.empty())
3.144 -
3.145 -
3.146 - } //void run()
3.147 -
3.148 -
3.149 -
3.150 -
3.151 -
3.152 - /*
3.153 - *Returns the distance of the Node v.
3.154 - *It is 0 for the root and for the Nodes not
3.155 - *reachable form the root.
3.156 - */
3.157 - T dist(NodeIt v) {
3.158 - return -distance.get(v);
3.159 - }
3.160 -
3.161 -
3.162 -
3.163 - /*
3.164 - * Returns the last Edge of a shortest s-v path.
3.165 - * Returns an invalid iterator if v=root or v is not
3.166 - * reachable from the root.
3.167 - */
3.168 - EdgeIt pred(NodeIt v) {
3.169 - if (v!=s) { return predecessor.get(v);}
3.170 - else {return EdgeIt();}
3.171 - }
3.172 -
3.173 -
3.174 -
3.175 - bool reach(NodeIt v) {
3.176 - return reached.get(v);
3.177 - }
3.178 -
3.179 -
3.180 -
3.181 -
3.182 -
3.183 -
3.184 -
3.185 -
3.186 -
3.187 - };// class dijkstra
3.188 -
3.189 -
3.190 -
3.191 - } // namespace hugo
3.192 -}
3.193 -#endif //DIJKSTRA_HH
3.194 -
3.195 -
4.1 --- a/src/work/jacint/makefile Mon Mar 01 16:32:50 2004 +0000
4.2 +++ b/src/work/jacint/makefile Mon Mar 01 17:24:34 2004 +0000
4.3 @@ -3,44 +3,15 @@
4.4 CXXFLAGS = -W -Wall -ansi -pedantic
4.5 LEDAROOT = /ledasrc/LEDA-4.1
4.6
4.7 -BINARIES = preflow_jgraph
4.8 +BINARIES = preflow
4.9
4.10 all: $(BINARIES)
4.11
4.12 makefile: .depend
4.13 sinclude .depend
4.14
4.15 -
4.16 -
4.17 -preflow_jgraph:
4.18 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_jgraph preflow_jgraph.cc
4.19 -
4.20 -preflowalpar:
4.21 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../alpar -I../jacint -o preflowalpar preflowalpar.cc
4.22 -
4.23 -preflow_max_flow:
4.24 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_max_flow preflow_max_flow.cc
4.25 -
4.26 preflow:
4.27 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow preflow.cc
4.28 -
4.29 -preflow_hl0:
4.30 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_hl0 preflow_hl0.cc
4.31 -
4.32 -preflow_hl1:
4.33 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_hl1 preflow_hl1.cc
4.34 -
4.35 -preflow_hl2:
4.36 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_hl2 preflow_hl2.cc
4.37 -
4.38 -preflow_hl3:
4.39 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_hl3 preflow_hl3.cc
4.40 -
4.41 -preflow_hl4:
4.42 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_hl4 preflow_hl4.cc
4.43 -
4.44 -preflow_param:
4.45 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_param preflow_param.cc
4.46 + $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o preflow preflow.cc
4.47
4.48 clean:
4.49 $(RM) *.o $(BINARIES) .depend