Changeset 333:e0a80761dfd9 in lemon-0.x for src

Timestamp:

04/15/04 22:19:26 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

makroizeles

Location:

src/work/marci

Files:

• edmonds_karp_demo.cc (modified) (5 diffs)
• for_each_macros.h (modified) (2 diffs)
• graph_concept.h (modified) (4 diffs)

src/work/marci/edmonds_karp_demo.cc

@@ -10 +10 @@
 //#include <graph_wrapper.h>
 #include <preflow.h>
+#include <for_each_macros.h>
 
 using namespace hugo;
@@ -67 +68 @@
   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; 
@@ -127 +96 @@
   {
     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; 
@@ -155 +107 @@
   {
     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; 
@@ -183 +118 @@
   {
     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; 

src/work/marci/for_each_macros.h

@@ -44 +44 @@
 //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; 
   }
 
@@ -72 +72 @@
 //   }
 
-#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)))

src/work/marci/graph_concept.h

@@ -365 +365 @@
   };
 
-  /// 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 
@@ -374 +395 @@
   /// the implementation can be circumstantial, that is why this composes a 
   /// separate concept.
-  class NodeCountingGraphSkeleturo 
+  class NodeCountingGraphSkeleturo : public GraphSkeleturo
   {
   public:
@@ -381 +402 @@
   };
 
-  /// 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 
@@ -390 +410 @@
   /// the implementation can be circumstantial, that is why this composes a 
   /// separate concept.
-  class EdgeCountingGraphSkeleturo 
+  class EdgeCountingGraphSkeleturo : public GraphSkeleturo
   {
   public: