Changeset 220:7deda4d6a07a in lemon-0.x

Timestamp:

03/20/04 21:06:23 (21 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@316

Message:

* empty log message *

Location:

src/work/jacint

Files:

• README_FLOW (deleted)
• dijkstra.h (modified) (2 diffs)
• fib_heap.h (modified) (2 diffs)
• makefile (modified) (2 diffs)
• preflow.cc (modified) (4 diffs)
• prim.cc (modified) (4 diffs)

src/work/jacint/dijkstra.h

@@ -81 +81 @@
         
         Node v=heap.top(); 
-        T oldvalue=heap[v];
+        T oldvalue=heap.get(v);
         heap.pop();
         distance.set(v, oldvalue);
@@ -95 +95 @@
               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]); 

src/work/jacint/fib_heap.h

@@ -144 +144 @@
     
 
-
-
     PrioType& operator[](const Item& it) {
       return container[iimap[it]].prio;
     }
+
     
     const PrioType& operator[](const Item& it) const {
@@ -154 +153 @@
     }
 
-//     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.*/

src/work/jacint/makefile

@@ -1 +1 @@
 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
 
@@ -12 +12 @@
 
 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:

src/work/jacint/preflow.cc

@@ -2 +2 @@
 #include <fstream>
 
+#include <smart_graph.h>
 #include <list_graph.h>
 #include <dimacs.h>
@@ -12 +13 @@
 // 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);
 
@@ -25 +26 @@
 
   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();
@@ -33 +34 @@
   }
 
-  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];
       }
   

src/work/jacint/prim.cc

@@ -2 +2 @@
 #include <fstream>
 
+#include <smart_graph.h>
 #include <list_graph.h>
 #include <dimacs.h>
@@ -13 +14 @@
 
 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);
 
@@ -23 +24 @@
   
   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();
@@ -32 +33 @@
  
   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();