# HG changeset patch
# User jacint
# Date 1078161874 0
# Node ID 01d47457aff3b950dc8534f3f7fb796e438f3ead
# Parent  a17d2a6462ee5c041e8cbec25fa6c8398b1dc1e4
nagytakaritas

diff -r a17d2a6462ee -r 01d47457aff3 src/work/jacint/README_FLOW
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/README_FLOW	Mon Mar 01 17:24:34 2004 +0000
@@ -0,0 +1,55 @@
+   Heurisztikak:
+
+gap: ha egy 0<i<n szint kiurul, az [i+1,n-1] szinten levoket felrakjuk az 
+	n szintre, ezzel nem sertve a tavolsagcimke tulajdonsagot
+
+highest label: a legnagyobb szintu aktivon pumpalunk (2 phase eseten
+	persze az n alattiak kozul a legnagyobb szintun)
+
+bound_decrease: nem highest label. Egy b valtozoval lepegetunk lefele
+	mig 0-hoz erunk, amikor megemeljuk n-ig (vagy k-ig ha
+	az nyilvan volt tartva). Mindig egy b szintu aktivon
+	pumpalunk (ha van ilyen, ha nem: --b). Relabel utan tehat 
+	nem megyunk a csucs utan, ot majd csak b ujboli felemelese utan
+	tudjuk pumpalni. Meglepoen hatekony.
+
+highest label + bound_decrease: preflow.h-ban H0*n relabel-enkent a 
+	bound_decrease, mig H1*n relabel-enkent a highest label valtozatot
+	futtatjuk az 1. fazisban (a masodik fazis igen gyors az elsohoz
+	kepest, igy itt sima highest label fut). Ez igen hatekonynak 
+	tunik, ugy latszik, hogy egyesul a ket eljaras elonye. Teszteles
+	alapjan a H0=20, H1=1 valasztas elfogadhatonak tunik.
+
+2 phase: az elso fazisban csak az [1,n-1] szintu aktivokon pumpalunk, 
+	es alkalmazzuk gap-et. Ha alul nincs aktiv, fentrol kifujjuk
+	s-bol a fenti csucsokat a segedgraf egy vissza bfs-evel, es 
+	visszacsurgatunk ugyanugy, mint az elso fazisban. Az elso fazis
+	utan az n. szint alatti csucsok egy min vagast adnak, es t
+	excesse a max folyamertek.
+
+level_list: kezzel irunk egy listat minden szintre az ottani csucsokrol.
+ 	Ha meg egy k valtozoban nyilvantartjuk a legnagyobb nemures 
+	szintet az [1,n] intervallumban, akkor nagyon gyorsan tudunk
+	gap eseten a gap feletti csucsokat az n szintre tenni. Ilyenkor
+	arra sincs szukseg (ami maskor igen hasznos), hogy nyilvantartsuk
+	melyik szinten hany csucs van. 
+
+
+    A LEDA flowja
+
+max_flow.t tartalmazza a LEDA flowjait, a legutolso fuggveny, 
+MAX_FLOW_T a default. Semmi kulonoset nem csinal, 2 fazisu highest label, 
+gap eseten bfs-sel szivja fel a csucsokat az n szintre (ez igen rossz 
+megoldas suru grafnal). Nyilvan tartja az aktivokat egy valamilyen stackben,
+es hogy melyik szinten hany pont van. 5*m lepesenkent (h=5 defaultbol) 
+csinal egy bfs-t vagy t-bol (1. fazis) vagy s-bol (2. fazis). Van benne
+par rossz megoldas, pl. az elsorol a 2. fazisra valo atteresnel nem kell
+egy bfs a t-bol.
+
+
+
+    Egy erdekes tapasztalat:
+
+Meglepo modon nagyon sokat gyorsitott amikor az stl stack-jet kezzel
+megirtam. Ez talan a G.id(NodeIt v) hatekonysaganak koszonheto. 
+
diff -r a17d2a6462ee -r 01d47457aff3 src/work/jacint/READ_FLOW
--- a/src/work/jacint/READ_FLOW	Mon Mar 01 16:32:50 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,55 +0,0 @@
-   Heurisztikak:
-
-gap: ha egy 0<i<n szint kiurul, az [i+1,n-1] szinten levoket felrakjuk az 
-	n szintre, ezzel nem sertve a tavolsagcimke tulajdonsagot
-
-highest label: a legnagyobb szintu aktivon pumpalunk (2 phase eseten
-	persze az n alattiak kozul a legnagyobb szintun)
-
-bound_decrease: nem highest label. Egy b valtozoval lepegetunk lefele
-	mig 0-hoz erunk, amikor megemeljuk n-ig (vagy k-ig ha
-	az nyilvan volt tartva). Mindig egy b szintu aktivon
-	pumpalunk (ha van ilyen, ha nem: --b). Relabel utan tehat 
-	nem megyunk a csucs utan, ot majd csak b ujboli felemelese utan
-	tudjuk pumpalni. Meglepoen hatekony.
-
-highest label + bound_decrease: preflow.h-ban H0*n relabel-enkent a 
-	bound_decrease, mig H1*n relabel-enkent a highest label valtozatot
-	futtatjuk az 1. fazisban (a masodik fazis igen gyors az elsohoz
-	kepest, igy itt sima highest label fut). Ez igen hatekonynak 
-	tunik, ugy latszik, hogy egyesul a ket eljaras elonye. Teszteles
-	alapjan a H0=20, H1=1 valasztas elfogadhatonak tunik.
-
-2 phase: az elso fazisban csak az [1,n-1] szintu aktivokon pumpalunk, 
-	es alkalmazzuk gap-et. Ha alul nincs aktiv, fentrol kifujjuk
-	s-bol a fenti csucsokat a segedgraf egy vissza bfs-evel, es 
-	visszacsurgatunk ugyanugy, mint az elso fazisban. Az elso fazis
-	utan az n. szint alatti csucsok egy min vagast adnak, es t
-	excesse a max folyamertek.
-
-level_list: kezzel irunk egy listat minden szintre az ottani csucsokrol.
- 	Ha meg egy k valtozoban nyilvantartjuk a legnagyobb nemures 
-	szintet az [1,n] intervallumban, akkor nagyon gyorsan tudunk
-	gap eseten a gap feletti csucsokat az n szintre tenni. Ilyenkor
-	arra sincs szukseg (ami maskor igen hasznos), hogy nyilvantartsuk
-	melyik szinten hany csucs van. 
-
-
-    A LEDA flowja
-
-max_flow.t tartalmazza a LEDA flowjait, a legutolso fuggveny, 
-MAX_FLOW_T a default. Semmi kulonoset nem csinal, 2 fazisu highest label, 
-gap eseten bfs-sel szivja fel a csucsokat az n szintre (ez igen rossz 
-megoldas suru grafnal). Nyilvan tartja az aktivokat egy valamilyen stackben,
-es hogy melyik szinten hany pont van. 5*m lepesenkent (h=5 defaultbol) 
-csinal egy bfs-t vagy t-bol (1. fazis) vagy s-bol (2. fazis). Van benne
-par rossz megoldas, pl. az elsorol a 2. fazisra valo atteresnel nem kell
-egy bfs a t-bol.
-
-
-
-    Egy erdekes tapasztalat:
-
-Meglepo modon nagyon sokat gyorsitott amikor az stl stack-jet kezzel
-megirtam. Ez talan a G.id(NodeIt v) hatekonysaganak koszonheto. 
-
diff -r a17d2a6462ee -r 01d47457aff3 src/work/jacint/dijkstra.hh
--- a/src/work/jacint/dijkstra.hh	Mon Mar 01 16:32:50 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,192 +0,0 @@
-/*
- *dijkstra
- *by jacint
- *Performs Dijkstra's algorithm from Node s. 
- *
- *Constructor: 
- *
- *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance)
- *
- *
- *
- *Member functions:
- *
- *void run()
- *
- *  The following function should be used after run() was already run.
- *
- *
- *T dist(NodeIt v) : returns the distance from s to v. 
- *   It is 0 if v is not reachable from s.
- *
- *
- *EdgeIt pred(NodeIt v)
- *   Returns the last Edge of a shortest s-v path. 
- *   Returns an invalid iterator if v=s or v is not
- *   reachable from s.
- *
- *
- *bool reach(NodeIt v) : true if v is reachable from s
- *
- *
- *
- *
- *
- *Problems: 
- * 
- *Heap implementation is needed, because the priority queue of stl
- *does not have a mathod for key-decrease, so we had to use here a 
- *g\'any solution.
- * 
- *The implementation of infinity would be desirable, see after line 100. 
- */
-
-#ifndef DIJKSTRA_HH
-#define DIJKSTRA_HH
-
-#include <queue>
-#include <algorithm>
-
-#include <marci_graph_traits.hh>
-#include <marciMap.hh>
-
-
-namespace std {
-  namespace hugo {
-
-
-
-
-
-    template <typename graph_type, typename T>
-    class dijkstra{
-      typedef typename graph_traits<graph_type>::NodeIt NodeIt;
-      typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
-      typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
-      typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
-      typedef typename graph_traits<graph_type>::OutEdgeIt OutEdgeIt;
-      
-      
-      graph_type& G;
-      NodeIt s;
-      NodeMap<graph_type, EdgeIt> predecessor;
-      NodeMap<graph_type, T> distance;
-      EdgeMap<graph_type, T> length;
-      NodeMap<graph_type, bool> reached;
-          
-  public :
-
-    /*
-      The distance of all the Nodes is 0.
-    */
-    dijkstra(graph_type& _G, NodeIt _s, EdgeMap<graph_type, T>& _length) : 
-      G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { }
-    
-
-      
-      /*By Misi.*/
-      struct Node_dist_comp
-      {
-	NodeMap<graph_type, T> &d;
-	Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} 
-	
-	bool operator()(const NodeIt& u, const NodeIt& v) const 
-	{ return d.get(u) < d.get(v); }
-      };
-
-
-      
-      void run() {
-	
-	NodeMap<graph_type, bool> scanned(G, false);
-	std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp> 
-	  heap(( Node_dist_comp(distance) ));
-      
-	heap.push(s);
-	reached.put(s, true);
-
-	while (!heap.empty()) {
-
-	  NodeIt v=heap.top();	
-	  heap.pop();
-
-
-	  if (!scanned.get(v)) {
-	
-	    for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
-	      NodeIt w=G.head(e);
-
-	      if (!scanned.get(w)) {
-		if (!reached.get(w)) {
-		  reached.put(w,true);
-		  distance.put(w, distance.get(v)-length.get(e));
-		  predecessor.put(w,e);
-		} else if (distance.get(v)-length.get(e)>distance.get(w)) {
-		  distance.put(w, distance.get(v)-length.get(e));
-		  predecessor.put(w,e);
-		}
-		
-		heap.push(w);
-	      
-	      } 
-
-	    } 
-	    scanned.put(v,true);
-	    
-	  } // if (!scanned.get(v))
-	  
-	  
-	  
-	} // while (!heap.empty())
-
-	
-      } //void run()
-      
-      
-      
-
-
-      /*
-       *Returns the distance of the Node v.
-       *It is 0 for the root and for the Nodes not
-       *reachable form the root.
-       */      
-      T dist(NodeIt v) {
-	return -distance.get(v);
-      }
-
-
-
-      /*
-       *  Returns the last Edge of a shortest s-v path. 
-       *  Returns an invalid iterator if v=root or v is not
-       *  reachable from the root.
-       */      
-      EdgeIt pred(NodeIt v) {
-	if (v!=s) { return predecessor.get(v);}
-	else {return EdgeIt();}
-      }
-     
-
-      
-      bool reach(NodeIt v) {
-	return reached.get(v);
-      }
-
-
-
-
-
-
-
-
-
-    };// class dijkstra
-
-
-
-  } // namespace hugo
-}
-#endif //DIJKSTRA_HH
-
-
diff -r a17d2a6462ee -r 01d47457aff3 src/work/jacint/makefile
--- a/src/work/jacint/makefile	Mon Mar 01 16:32:50 2004 +0000
+++ b/src/work/jacint/makefile	Mon Mar 01 17:24:34 2004 +0000
@@ -3,44 +3,15 @@
 CXXFLAGS = -W -Wall -ansi -pedantic
 LEDAROOT = /ledasrc/LEDA-4.1
 
-BINARIES = preflow_jgraph
+BINARIES = preflow
 
 all: $(BINARIES)
 
 makefile: .depend
 sinclude .depend
 
-
-
-preflow_jgraph: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_jgraph preflow_jgraph.cc
-
-preflowalpar: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../alpar -I../jacint -o preflowalpar preflowalpar.cc
-
-preflow_max_flow: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint  -o preflow_max_flow preflow_max_flow.cc
-
 preflow: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow preflow.cc
-
-preflow_hl0: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_hl0 preflow_hl0.cc
-
-preflow_hl1: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_hl1 preflow_hl1.cc
-
-preflow_hl2: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_hl2 preflow_hl2.cc
-
-preflow_hl3: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_hl3 preflow_hl3.cc
-
-preflow_hl4: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_hl4 preflow_hl4.cc
-
-preflow_param: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../jacint -o preflow_param preflow_param.cc
+	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o preflow preflow.cc
 
 clean:
 	$(RM) *.o $(BINARIES) .depend