1.1 --- a/src/work/marci/bfsit_vs_byhand.cc	Wed Oct 13 15:52:35 2004 +0000
     1.2 +++ b/src/work/marci/bfsit_vs_byhand.cc	Sat Oct 16 00:20:13 2004 +0000
     1.3 @@ -2,12 +2,14 @@
     1.4  #include <iostream>
     1.5  #include <fstream>
     1.6  
     1.7 -#include <sage_graph.h>
     1.8 +//#include <sage_graph.h>
     1.9  #include <lemon/smart_graph.h>
    1.10 +#include <lemon/list_graph.h>
    1.11  #include <lemon/dimacs.h>
    1.12  #include <lemon/time_measure.h>
    1.13  //#include <lemon/for_each_macros.h>
    1.14 -#include <bfs_dfs.h>
    1.15 +#include <bfs_mm.h>
    1.16 +#include <lemon/bfs.h>
    1.17  
    1.18  using namespace lemon;
    1.19  
    1.20 @@ -15,7 +17,9 @@
    1.21  using std::endl;
    1.22  
    1.23  int main() {
    1.24 -  typedef SageGraph Graph; 
    1.25 +  //  typedef SageGraph Graph; 
    1.26 +  typedef SmartGraph Graph ;
    1.27 +  //typedef ListGraph Graph; 
    1.28    typedef Graph::Node Node;
    1.29    typedef Graph::NodeIt NodeIt;
    1.30    typedef Graph::Edge Edge;
    1.31 @@ -23,12 +27,8 @@
    1.32    typedef Graph::OutEdgeIt OutEdgeIt;
    1.33  
    1.34    Graph g;
    1.35 -  //Node s;
    1.36 -  //Graph::EdgeMap<int> cap(g);
    1.37 -  //readDimacsMaxFlow(std::cin, g, s, t, cap);
    1.38    readDimacs(std::cin, g);
    1.39 -  NodeIt s;
    1.40 -  g.first(s);
    1.41 +  NodeIt s(g);
    1.42  
    1.43    cout << g.nodeNum() << endl;
    1.44    cout << g.edgeNum() << endl;
    1.45 @@ -36,8 +36,9 @@
    1.46    Graph::NodeMap<Edge> pred(g);
    1.47    cout << "iteration time of bfs written by hand..." << endl;
    1.48    Timer ts;
    1.49 +  ts.reset();
    1.50 +  for (int i=0; i<100; ++i)
    1.51    {
    1.52 -    ts.reset();
    1.53      Graph::NodeMap<bool> reached(g);
    1.54      reached.set(s, true);
    1.55      pred.set(s, INVALID);
    1.56 @@ -46,8 +47,7 @@
    1.57      while (!bfs_queue.empty()) {
    1.58        Node v=bfs_queue.front();	
    1.59        bfs_queue.pop();
    1.60 -      OutEdgeIt e;
    1.61 -      for(g.first(e,v); g.valid(e); g.next(e)) {
    1.62 +      for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
    1.63  	Node w=g.head(e);
    1.64  	if (!reached[w]) {
    1.65  	  bfs_queue.push(w);
    1.66 @@ -56,23 +56,35 @@
    1.67  	}
    1.68        }
    1.69      }
    1.70 -
    1.71 -    std::cout << ts << std::endl;
    1.72    }
    1.73 +  std::cout << ts << std::endl;
    1.74  
    1.75    cout << "iteration time with bfs iterator..." << endl;
    1.76 +  ts.reset();      
    1.77 +  for (int i=0; i<100; ++i)
    1.78    {
    1.79 -    ts.reset();      
    1.80 -    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
    1.81 +    Graph::NodeMap<bool> reached(g);
    1.82 +    marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached);
    1.83      bfs.pushAndSetReached(s);
    1.84      pred.set(s, INVALID);
    1.85      while (!bfs.finished()) { 
    1.86        ++bfs; 
    1.87 -      if (g.valid(bfs) && bfs.isBNodeNewlyReached()) 
    1.88 +      if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached()) 
    1.89  	pred.set(bfs.head(), Graph::Edge(bfs));
    1.90      }
    1.91 -    std::cout << ts << std::endl;
    1.92    }
    1.93 +  std::cout << ts << std::endl;
    1.94 +
    1.95 +  cout << "iteration time with bfs aplar..." << endl;
    1.96 +  ts.reset();      
    1.97 +  for (int i=0; i<100; ++i)
    1.98 +  {
    1.99 +    Bfs<Graph> bfs(g);
   1.100 +    bfs.setPredMap(pred);
   1.101 +    bfs.run(s);
   1.102 +  }
   1.103 +  std::cout << ts << std::endl;
   1.104 +
   1.105  
   1.106    return 0;
   1.107  }