Changeset 944:4f064aff855e in lemon-0.x for src/work/marci/bfsit_vs_byhand.cc

Timestamp:

10/16/04 02:20:13 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

It's time to design an iterable generic bfs

File:

• src/work/marci/bfsit_vs_byhand.cc (modified) (6 diffs)

src/work/marci/bfsit_vs_byhand.cc

@@ -3 +3 @@
 #include <fstream>
 
-#include <sage_graph.h>
+//#include <sage_graph.h>
 #include <lemon/smart_graph.h>
+#include <lemon/list_graph.h>
 #include <lemon/dimacs.h>
 #include <lemon/time_measure.h>
 //#include <lemon/for_each_macros.h>
-#include <bfs_dfs.h>
+#include <bfs_mm.h>
+#include <lemon/bfs.h>
 
 using namespace lemon;
@@ -16 +18 @@
 
 int main() {
-  typedef SageGraph Graph; 
+  //  typedef SageGraph Graph; 
+  typedef SmartGraph Graph ;
+  //typedef ListGraph Graph; 
   typedef Graph::Node Node;
   typedef Graph::NodeIt NodeIt;
@@ -24 +28 @@
 
   Graph g;
-  //Node s;
-  //Graph::EdgeMap<int> cap(g);
-  //readDimacsMaxFlow(std::cin, g, s, t, cap);
   readDimacs(std::cin, g);
-  NodeIt s;
-  g.first(s);
+  NodeIt s(g);
 
   cout << g.nodeNum() << endl;
@@ -37 +37 @@
   cout << "iteration time of bfs written by hand..." << endl;
   Timer ts;
+  ts.reset();
+  for (int i=0; i<100; ++i)
   {
-    ts.reset();
     Graph::NodeMap<bool> reached(g);
     reached.set(s, true);
@@ -47 +48 @@
       Node v=bfs_queue.front(); 
       bfs_queue.pop();
-      OutEdgeIt e;
-      for(g.first(e,v); g.valid(e); g.next(e)) {
+      for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
         Node w=g.head(e);
         if (!reached[w]) {
@@ -57 +57 @@
       }
     }
-
-    std::cout << ts << std::endl;
   }
+  std::cout << ts << std::endl;
 
   cout << "iteration time with bfs iterator..." << endl;
+  ts.reset();      
+  for (int i=0; i<100; ++i)
   {
-    ts.reset();      
-    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
+    Graph::NodeMap<bool> reached(g);
+    marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached);
     bfs.pushAndSetReached(s);
     pred.set(s, INVALID);
     while (!bfs.finished()) { 
       ++bfs; 
-      if (g.valid(bfs) && bfs.isBNodeNewlyReached()) 
+      if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached()) 
         pred.set(bfs.head(), Graph::Edge(bfs));
     }
-    std::cout << ts << std::endl;
   }
+  std::cout << ts << std::endl;
+
+  cout << "iteration time with bfs aplar..." << endl;
+  ts.reset();      
+  for (int i=0; i<100; ++i)
+  {
+    Bfs<Graph> bfs(g);
+    bfs.setPredMap(pred);
+    bfs.run(s);
+  }
+  std::cout << ts << std::endl;
+
 
   return 0;