# HG changeset patch
# User marci
# Date 1082060366 0
# Node ID e0a80761dfd999cd704d516d390c967c05b52343
# Parent  5dc61ba307309a0b9b74d5c5319fea0d48704b38
makroizeles

diff -r 5dc61ba30730 -r e0a80761dfd9 src/work/marci/edmonds_karp_demo.cc
--- a/src/work/marci/edmonds_karp_demo.cc	Thu Apr 15 19:01:00 2004 +0000
+++ b/src/work/marci/edmonds_karp_demo.cc	Thu Apr 15 20:19:26 2004 +0000
@@ -9,6 +9,7 @@
 #include <time_measure.h>
 //#include <graph_wrapper.h>
 #include <preflow.h>
+#include <for_each_macros.h>
 
 using namespace hugo;
 
@@ -66,59 +67,27 @@
   Node s, t;
   Graph::EdgeMap<int> cap(G);
   readDimacsMaxFlow(std::cin, G, s, t, cap);
+  Timer ts;
+  Graph::EdgeMap<int> flow(G); //0 flow
+  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
+    pre_flow_test(G, s, t, cap, flow);
+  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
+    max_flow_test(G, s, t, cap, flow);
 
   {
     std::cout << "preflow ..." << std::endl;
-    Graph::EdgeMap<int> flow(G); //0 flow
-
-    Timer ts;
     ts.reset();
-
-    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      max_flow_test(G, s, t, cap, flow);
-    max_flow_test.run();
-//    int i=0;
-//    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 
-//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
-//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//     }
-//     std::cout<<std::endl;
-//      ++i; 
-//    }
-
-//   std::cout << "maximum flow: "<< std::endl;
-//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
-//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//   }
-//   std::cout<<std::endl;
+    pre_flow_test.run();
     std::cout << "elapsed time: " << ts << std::endl;
-//    std::cout << "number of augmentation phases: " << i << std::endl; 
-    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+    std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
   }
 
   {
     std::cout << "physical blocking flow augmentation ..." << std::endl;
-    Graph::EdgeMap<int> flow(G); //0 flow
-
-    Timer ts;
+    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     ts.reset();
-
-    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      max_flow_test(G, s, t, cap, flow);
     int i=0;
-    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 
-//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
-//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//     }
-//     std::cout<<std::endl;
-      ++i; 
-    }
-
-//   std::cout << "maximum flow: "<< std::endl;
-//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
-//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//   }
-//   std::cout<<std::endl;
+    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
     std::cout << "elapsed time: " << ts << std::endl;
     std::cout << "number of augmentation phases: " << i << std::endl; 
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
@@ -126,27 +95,10 @@
 
   {
     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
-    Graph::EdgeMap<int> flow(G); //0 flow
-
-    Timer ts;
+    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     ts.reset();
-
-    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      max_flow_test(G, s, t, cap, flow);
     int i=0;
-    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 
-//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
-//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//     }
-//     std::cout<<std::endl;
-      ++i; 
-    }
-
-//   std::cout << "maximum flow: "<< std::endl;
-//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
-//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//   }
-//   std::cout<<std::endl;
+    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
     std::cout << "elapsed time: " << ts << std::endl;
     std::cout << "number of augmentation phases: " << i << std::endl; 
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
@@ -154,27 +106,10 @@
 
   {
     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
-    Graph::EdgeMap<int> flow(G); //0 flow
-
-    Timer ts;
+    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     ts.reset();
-
-    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      max_flow_test(G, s, t, cap, flow);
     int i=0;
-    while (max_flow_test.augmentOnBlockingFlow2()) { 
-//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
-//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//     }
-//     std::cout<<std::endl;
-      ++i; 
-    }
-
-//   std::cout << "maximum flow: "<< std::endl;
-//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
-//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//   }
-//   std::cout<<std::endl;
+    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
     std::cout << "elapsed time: " << ts << std::endl;
     std::cout << "number of augmentation phases: " << i << std::endl; 
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
@@ -182,27 +117,10 @@
 
   {
     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
-    Graph::EdgeMap<int> flow(G); //0 flow
-
-    Timer ts;
+    FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
     ts.reset();
-
-    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
-      max_flow_test(G, s, t, cap, flow);
     int i=0;
-    while (max_flow_test.augmentOnShortestPath()) { 
-//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
-//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//     }
-//     std::cout<<std::endl;
-      ++i; 
-    }
-
-//   std::cout << "maximum flow: "<< std::endl;
-//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
-//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-//   }
-//   std::cout<<std::endl;
+    while (max_flow_test.augmentOnShortestPath()) { ++i; }
     std::cout << "elapsed time: " << ts << std::endl;
     std::cout << "number of augmentation phases: " << i << std::endl; 
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
diff -r 5dc61ba30730 -r e0a80761dfd9 src/work/marci/for_each_macros.h
--- a/src/work/marci/for_each_macros.h	Thu Apr 15 19:01:00 2004 +0000
+++ b/src/work/marci/for_each_macros.h	Thu Apr 15 20:19:26 2004 +0000
@@ -43,13 +43,13 @@
 
 //FIXME ezt hogy a gorcsbe birja levezetni. Csak ugy leveszi a const-ot??
   template<typename It, typename Graph> 
-  It loopFirst(const It& i, const Graph& g) {
-    It e=i; g.first(e); return e; 
+  It loopFirst(const It&, const Graph& g) {
+    It e; g.first(e); return e; 
   }
 
   template<typename It, typename Graph, typename Node> 
-  It loopFirst(const It& i, const Graph& g, const Node& v) {
-    It e=i; g.first(e, v); return e; 
+  It loopFirst(const It&, const Graph& g, const Node& v) {
+    It e; g.first(e, v); return e; 
   }
 
 //   template<typename Graph> 
@@ -71,10 +71,10 @@
 //     typename Graph::InEdgeIt e; g.first(e, n); return e; 
 //   }
 
-#define FOR_EACH_LOC(Ittype, e, g) for(Ittype (e)=loopFirst(Ittype(), (g)); (g).valid((e)); (g).next((e)))
-#define FOR_EACH_INC_LOC(Ittype, e, g, v) for(Ittype (e)=loopFirst(Ittype(), (g), (v)); (g).valid((e)); (g).next((e)))
+#define FOR_EACH_LOC(Ittype, e, g) for(Ittype e=loopFirst(Ittype(), (g)); (g).valid(e); (g).next(e))
+#define FOR_EACH_INC_LOC(Ittype, e, g, v) for(Ittype e=loopFirst(Ittype(), (g), (v)); (g).valid(e); (g).next(e))
 
-// #define FOR_EACH_EDGE_LOC(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
+// #define FOR_EACH_EDGE_LOC(e, g) ezt nem tom hogy kell for((g).first((e)); (g).valid((e)); (g).next((e)))
 // #define FOR_EACH_NODE_LOC(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
 // #define FOR_EACH_INEDGE_LOC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
 // #define FOR_EACH_OUTEDGE_LOC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
diff -r 5dc61ba30730 -r e0a80761dfd9 src/work/marci/graph_concept.h
--- a/src/work/marci/graph_concept.h	Thu Apr 15 19:01:00 2004 +0000
+++ b/src/work/marci/graph_concept.h	Thu Apr 15 20:19:26 2004 +0000
@@ -364,8 +364,29 @@
     GraphSkeleturo(const GraphSkeleturo &G) {}
   };
 
-  /// An empty graph class which provides a function to get the number 
-  /// of its nodes.
+  /// An empty node-eraseable graph class.
+  
+  /// An empty graph class which provides a function to 
+  /// delete any of its nodes.
+  class NodeEraseableGraphSkeleturo : public GraphSkeleturo
+  {
+  public:
+    /// Deletes a node.
+    void erase(Node n) {}
+  };
+
+  /// An empty edge-eraseable graph class.
+  
+  /// An empty graph class which provides a function to delete any 
+  /// of its edges.
+  class EdgeEraseableGraphSkeleturo : public GraphSkeleturo
+  {
+  public:
+    /// Deletes a node.
+    void erase(Edge n) {}
+  };
+
+  /// An empty graph class which provides a function to get the number of its nodes.
   
   /// This graph class provides a function for getting the number of its 
   /// nodes. 
@@ -373,15 +394,14 @@
   /// function. For wrappers or graphs which are given in an implicit way, 
   /// the implementation can be circumstantial, that is why this composes a 
   /// separate concept.
-  class NodeCountingGraphSkeleturo 
+  class NodeCountingGraphSkeleturo : public GraphSkeleturo
   {
   public:
     /// Returns the number of nodes.
     int nodeNum() const { return 0;}
   };
 
-  /// An empty graph class which provides a function to get the number of its 
-  /// edges.
+  /// An empty graph class which provides a function to get the number of its edges.
   
   /// This graph class provides a function for getting the number of its 
   /// edges. 
@@ -389,7 +409,7 @@
   /// function. For wrappers or graphs which are given in an implicit way, 
   /// the implementation can be circumstantial, that is why this composes a 
   /// separate concept.
-  class EdgeCountingGraphSkeleturo 
+  class EdgeCountingGraphSkeleturo : public GraphSkeleturo
   {
   public:
     /// Returns the number of edges.