# HG changeset patch
# User jacint
# Date 1079813183 0
# Node ID 7deda4d6a07a456743fe79324f4cc3cdd2a7563b
# Parent  132dd3eb0f338b6ec13ca9bbfcd687404753e9a5
*** empty log message ***

diff -r 132dd3eb0f33 -r 7deda4d6a07a src/work/jacint/README_FLOW
--- a/src/work/jacint/README_FLOW	Sat Mar 20 19:39:42 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 132dd3eb0f33 -r 7deda4d6a07a src/work/jacint/dijkstra.h
--- a/src/work/jacint/dijkstra.h	Sat Mar 20 19:39:42 2004 +0000
+++ b/src/work/jacint/dijkstra.h	Sat Mar 20 20:06:23 2004 +0000
@@ -80,7 +80,7 @@
       while ( !heap.empty() ) {
 	
 	Node v=heap.top(); 
-	T oldvalue=heap[v];
+	T oldvalue=heap.get(v);
 	heap.pop();
 	distance.set(v, oldvalue);
 	scanned.set(v,true);
@@ -94,7 +94,7 @@
 	      reach.set(w,true);
 	      heap.push(w,oldvalue+length[e]); 
 	      predecessor.set(w,e);
-	    } else if ( oldvalue+length[e] < heap[w] ) {
+	    } else if ( oldvalue+length[e] < heap.get(w) ) {
 	      predecessor.set(w,e);
 	      heap.decrease(w, oldvalue+length[e]); 
 	    }
diff -r 132dd3eb0f33 -r 7deda4d6a07a src/work/jacint/fib_heap.h
--- a/src/work/jacint/fib_heap.h	Sat Mar 20 19:39:42 2004 +0000
+++ b/src/work/jacint/fib_heap.h	Sat Mar 20 20:06:23 2004 +0000
@@ -143,20 +143,20 @@
     }
     
 
-
-
     PrioType& operator[](const Item& it) {
       return container[iimap[it]].prio;
     }
+
     
     const PrioType& operator[](const Item& it) const {
       return container[iimap[it]].prio;
     }
 
-//     const PrioType get(const Item& it) const {
-//       return container[iimap[it]].prio;
-//     }
 
+    const PrioType get(const Item& it) const {
+      return container[iimap[it]].prio;
+    }
+    
     void pop() {
       /*The first case is that there are only one root.*/
       if ( container[minimum].left_neighbor==minimum ) {
diff -r 132dd3eb0f33 -r 7deda4d6a07a src/work/jacint/makefile
--- a/src/work/jacint/makefile	Sat Mar 20 19:39:42 2004 +0000
+++ b/src/work/jacint/makefile	Sat Mar 20 20:06:23 2004 +0000
@@ -1,6 +1,6 @@
 CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
 CXX2 = g++-2.95
-CXXFLAGS = -W -Wall -ansi -pedantic
+CXXFLAGS = -W -Wall -ansi -pedantic -O3 -I. -I.. -I../marci -I../alpar -I../../include  
 LEDAROOT ?= /ledasrc/LEDA-4.1
 
 BINARIES = dijkstra prim preflow
@@ -11,13 +11,13 @@
 sinclude .depend
 
 preflow: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o preflow preflow.cc 
+	$(CXX3) $(CXXFLAGS)  -o preflow preflow.cc 
 
 dijkstra: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar  -o dijkstra dijkstra.cc
+	$(CXX3) $(CXXFLAGS)  -o dijkstra dijkstra.cc
 
 prim: 
-	$(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o prim prim.cc
+	$(CXX3) $(CXXFLAGS)  -o prim prim.cc
 
 clean:
 	$(RM) *.o $(BINARIES) .depend
diff -r 132dd3eb0f33 -r 7deda4d6a07a src/work/jacint/preflow.cc
--- a/src/work/jacint/preflow.cc	Sat Mar 20 19:39:42 2004 +0000
+++ b/src/work/jacint/preflow.cc	Sat Mar 20 20:06:23 2004 +0000
@@ -1,6 +1,7 @@
 #include <iostream>
 #include <fstream>
 
+#include <smart_graph.h>
 #include <list_graph.h>
 #include <dimacs.h>
 #include <preflow.h>
@@ -11,12 +12,12 @@
 // Use a DIMACS max flow file as stdin.
 // read_dimacs_demo < dimacs_max_flow_file
 int main(int, char **) {
-  typedef ListGraph::Node Node;
-  typedef ListGraph::EdgeIt EdgeIt;
+  typedef SmartGraph::Node Node;
+  typedef SmartGraph::EdgeIt EdgeIt;
 
-  ListGraph G;
+  SmartGraph G;
   Node s, t;
-  ListGraph::EdgeMap<int> cap(G);
+  SmartGraph::EdgeMap<int> cap(G);
   readDimacsMaxFlow(std::cin, G, s, t, cap);
 
   std::cout << "preflow demo ..." << std::endl;
@@ -24,40 +25,40 @@
   double mintime=1000000;
 
   for ( int i=1; i!=11; ++i ) {
-    ListGraph::EdgeMap<int> flow(G);
+    SmartGraph::EdgeMap<int> flow(G);
     double pre_time=currTime();
-    Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
+    Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow);
     max_flow_test.run();
     double post_time=currTime();
     if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
   }
 
-  ListGraph::EdgeMap<int> flow(G);
-  Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
+  SmartGraph::EdgeMap<int> flow(G);
+  Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow);
   max_flow_test.run();
   
-  ListGraph::NodeMap<bool> cut(G);
+  SmartGraph::NodeMap<bool> cut(G);
   max_flow_test.minCut(cut); 
   int min_cut_value=0;
   EdgeIt e;
   for(G.first(e); G.valid(e); G.next(e)) {
-    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
+    if (cut[G.tail(e)] && !cut[G.head(e)]) min_cut_value+=cap[e];
   }
 
-  ListGraph::NodeMap<bool> cut1(G);
+  SmartGraph::NodeMap<bool> cut1(G);
   max_flow_test.minMinCut(cut1); 
   int min_min_cut_value=0;
   for(G.first(e); G.valid(e); G.next(e)) {
-    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) 
-      min_min_cut_value+=cap.get(e);
+    if (cut[G.tail(e)] && !cut[G.head(e)]) 
+      min_min_cut_value+=cap[e];
   }
 
-  ListGraph::NodeMap<bool> cut2(G);
+  SmartGraph::NodeMap<bool> cut2(G);
   max_flow_test.maxMinCut(cut2); 
   int max_min_cut_value=0;
   for(G.first(e); G.valid(e); G.next(e)) {
-    if (cut2.get(G.tail(e)) && !cut2.get(G.head(e))) 
-      max_min_cut_value+=cap.get(e);
+    if (cut2[G.tail(e)] && !cut2[G.head(e)]) 
+      max_min_cut_value+=cap[e];
       }
   
   std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl; 
diff -r 132dd3eb0f33 -r 7deda4d6a07a src/work/jacint/prim.cc
--- a/src/work/jacint/prim.cc	Sat Mar 20 19:39:42 2004 +0000
+++ b/src/work/jacint/prim.cc	Sat Mar 20 20:06:23 2004 +0000
@@ -1,6 +1,7 @@
 #include <iostream>
 #include <fstream>
 
+#include <smart_graph.h>
 #include <list_graph.h>
 #include <dimacs.h>
 #include <prim.h>
@@ -12,18 +13,18 @@
 using namespace hugo;
 
 int main(int, char **) {
-  typedef ListGraph::Node Node;
+  typedef SmartGraph::Node Node;
 
-  ListGraph G;
+  SmartGraph G;
   Node s, t;
-  ListGraph::EdgeMap<int> cap(G);
+  SmartGraph::EdgeMap<int> cap(G);
   readDimacsMaxFlow(std::cin, G, s, t, cap);
 
   std::cout << "prim demo ..." << std::endl;
   
   double pre_time=currTime();
-    Prim<ListGraph, int, FibHeap<ListGraph::Node, int, 
-    ListGraph::NodeMap<int> > > prim_test(G, cap);
+    Prim<SmartGraph, int, FibHeap<SmartGraph::Node, int, 
+    SmartGraph::NodeMap<int> > > prim_test(G, cap);
     prim_test.run();
   double post_time=currTime();
     
@@ -31,8 +32,8 @@
 	    << post_time-pre_time << " sec"<< std::endl; 
  
   pre_time=currTime();
-  Prim<ListGraph, int, BinHeap<ListGraph::Node, int, 
-    ListGraph::NodeMap<int> > > prim_test2(G, cap);
+  Prim<SmartGraph, int, BinHeap<SmartGraph::Node, int, 
+    SmartGraph::NodeMap<int> > > prim_test2(G, cap);
   prim_test2.run();
   post_time=currTime();