# HG changeset patch
# User marci
# Date 1082062203 0
# Node ID 63703ea7d02f440dd27cb9916bdddc2b5eec5124
# Parent  e0a80761dfd999cd704d516d390c967c05b52343
brrr

diff -r e0a80761dfd9 -r 63703ea7d02f src/work/marci/graph_concept.h
--- a/src/work/marci/graph_concept.h	Thu Apr 15 20:19:26 2004 +0000
+++ b/src/work/marci/graph_concept.h	Thu Apr 15 20:50:03 2004 +0000
@@ -109,55 +109,6 @@
       bool operator<(Edge n) const { return true; }
     };
     
-    /// This iterator goes trough the outgoing edges of a node.
-
-    /// This iterator goes trough the \e outgoing edges of a certain node
-    /// of a graph.
-    /// Its usage is quite simple, for example you can count the number
-    /// of outgoing edges of a node \c n
-    /// in graph \c G of type \c Graph as follows.
-    /// \code
-    ///int count=0;
-    ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
-    /// \endcode
-    
-    class OutEdgeIt : public Edge {
-    public:
-      /// @warning The default constructor sets the iterator
-      /// to an undefined value.
-      OutEdgeIt() {}
-      /// Initialize the iterator to be invalid
-      OutEdgeIt(Invalid) {}
-      /// This constructor sets the iterator to first outgoing edge.
-    
-      /// This constructor set the iterator to the first outgoing edge of
-      /// node
-      ///@param n the node
-      ///@param G the graph
-      OutEdgeIt(const GraphSkeleturo & G, Node n) {}
-    };
-
-    /// This iterator goes trough the incoming edges of a node.
-
-    /// This iterator goes trough the \e incoming edges of a certain node
-    /// of a graph.
-    /// Its usage is quite simple, for example you can count the number
-    /// of outgoing edges of a node \c n
-    /// in graph \c G of type \c Graph as follows.
-    /// \code
-    ///int count=0;
-    ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
-    /// \endcode
-
-    class InEdgeIt : public Edge {
-    public:
-      /// @warning The default constructor sets the iterator
-      /// to an undefined value.
-      InEdgeIt() {}
-      /// Initialize the iterator to be invalid
-      InEdgeIt(Invalid) {}
-      InEdgeIt(const GraphSkeleturo &, Node) {}    
-    };
     //  class SymEdgeIt : public Edge {};
 
     /// This iterator goes through each edge.
@@ -364,6 +315,79 @@
     GraphSkeleturo(const GraphSkeleturo &G) {}
   };
 
+  /// An empty out-edge-iterable graph class.
+  
+  /// An empty graph class which provides a function to 
+  /// iterate on out-edges of any node.
+  class OutEdgeIterableGraphSkeleturo : public GraphSkeleturo
+  {
+  public:
+
+    /// This iterator goes trough the outgoing edges of a node.
+
+    /// This iterator goes trough the \e outgoing edges of a certain node
+    /// of a graph.
+    /// Its usage is quite simple, for example you can count the number
+    /// of outgoing edges of a node \c n
+    /// in graph \c G of type \c Graph as follows.
+    /// \code
+    ///int count=0;
+    ///for(Graph::OutEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;
+    /// \endcode
+    class OutEdgeIt : public Edge {
+    public:
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      OutEdgeIt() {}
+      /// Initialize the iterator to be invalid
+      OutEdgeIt(Invalid) {}
+      /// This constructor sets the iterator to first outgoing edge.
+    
+      /// This constructor set the iterator to the first outgoing edge of
+      /// node
+      ///@param n the node
+      ///@param G the graph
+      OutEdgeIt(const GraphSkeleturo & G, Node n) {}
+    };
+  };
+
+  /// An empty in-edge-iterable graph class.
+  
+  /// An empty graph class which provides a function to 
+  /// iterate on in-edges of any node.
+  class InEdgeIterableGraphSkeleturo : public GraphSkeleturo
+  {
+  public:
+
+    /// This iterator goes trough the incoming edges of a node.
+
+    /// This iterator goes trough the \e incoming edges of a certain node
+    /// of a graph.
+    /// Its usage is quite simple, for example you can count the number
+    /// of incoming edges of a node \c n
+    /// in graph \c G of type \c Graph as follows.
+    /// \code
+    ///int count=0;
+    ///for(Graph::InEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;
+    /// \endcode
+    class InEdgeIt : public Edge {
+    public:
+      /// @warning The default constructor sets the iterator
+      /// to an undefined value.
+      InEdgeIt() {}
+      /// Initialize the iterator to be invalid
+      InEdgeIt(Invalid) {}
+      /// This constructor sets the iterator to first incomig edge.
+    
+      /// This constructor set the iterator to the first incomig edge of
+      /// node
+      ///@param n the node
+      ///@param G the graph
+      InEdgeIt(const GraphSkeleturo & G, Node n) {}
+    };
+  };
+
+
   /// An empty node-eraseable graph class.
   
   /// An empty graph class which provides a function to 
diff -r e0a80761dfd9 -r 63703ea7d02f src/work/marci/lg_vs_sg.cc
--- a/src/work/marci/lg_vs_sg.cc	Thu Apr 15 20:19:26 2004 +0000
+++ b/src/work/marci/lg_vs_sg.cc	Thu Apr 15 20:50:03 2004 +0000
@@ -7,8 +7,9 @@
 #include <smart_graph.h>
 #include <dimacs.h>
 #include <edmonds_karp.h>
+#include <preflow.h>
 #include <time_measure.h>
-#include <graph_wrapper.h>
+#include <for_each_macros.h>
 
 using namespace hugo;
 
@@ -31,50 +32,62 @@
     std::ifstream ins(in.c_str());
     readDimacsMaxFlow(ins, 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 << "ListGraph ..." << std::endl;
+
     {
-      std::cout << "ListGraph..." << std::endl;
-      std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
-      Graph::EdgeMap<int> flow(G); //0 flow
+      std::cout << "preflow ..." << std::endl;
+      ts.reset();
+      pre_flow_test.run();
+      std::cout << "elapsed time: " << ts << std::endl;
+      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+    }
 
-      Timer ts;
+    {
+      std::cout << "physical blocking flow augmentation ..." << std::endl;
+      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, flow, cap);
       int i=0;
       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;
     }
 
     {
-      std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
-      Graph::EdgeMap<int> flow(G); //0 flow
-
-      Timer ts;
+      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
+      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, flow, cap);
       int i=0;
-      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
-
+      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;
     }
 
     {
-      std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
-      Graph::EdgeMap<int> flow(G); //0 flow
+      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
+      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+      ts.reset();
+      int i=0;
+      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;
+    }
 
-      Timer ts;
+    {
+      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
+      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, flow, cap);
       int i=0;
       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;
@@ -93,55 +106,71 @@
     std::ifstream ins(in.c_str());
     readDimacsMaxFlow(ins, 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 << "SmatrGraph ..." << std::endl;
+
     {
-      std::cout << "SmartGraph..." << std::endl;
-      std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
-      Graph::EdgeMap<int> flow(G); //0 flow
+      std::cout << "preflow ..." << std::endl;
+      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+      ts.reset();
+      pre_flow_test.run();
+      std::cout << "elapsed time: " << ts << std::endl;
+      std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
+    }
 
-      Timer ts;
+    {
+      std::cout << "physical blocking flow augmentation ..." << std::endl;
+      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, flow, cap);
       int i=0;
       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;
     }
 
     {
-      std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
-      Graph::EdgeMap<int> flow(G); //0 flow
-
-      Timer ts;
+      std::cout << "faster physical blocking flow augmentation ..." << std::endl;
+      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, flow, cap);
       int i=0;
-      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
-
+      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;
     }
 
     {
-      std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
-      Graph::EdgeMap<int> flow(G); //0 flow
+      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
+      FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
+      ts.reset();
+      int i=0;
+      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;
+    }
 
-      Timer ts;
+    {
+      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
+      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, flow, cap);
       int i=0;
       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;
     }
   }
 
+
+
+
   return 0;
 }
diff -r e0a80761dfd9 -r 63703ea7d02f src/work/marci/makefile
--- a/src/work/marci/makefile	Thu Apr 15 20:19:26 2004 +0000
+++ b/src/work/marci/makefile	Thu Apr 15 20:50:03 2004 +0000
@@ -11,8 +11,8 @@
 LEDAINCLUDE ?= -I$(LEDAROOT)/incl
 CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
 
-LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test
+LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
+BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg
 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
 
 all: $(BINARIES)