1.1 --- a/src/work/marci/bfsit_vs_byhand.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,90 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#include <iostream>
1.6 -#include <fstream>
1.7 -
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_mm.h>
1.15 -#include <lemon/bfs.h>
1.16 -
1.17 -using namespace lemon;
1.18 -
1.19 -using std::cout;
1.20 -using std::endl;
1.21 -
1.22 -int main() {
1.23 - // typedef SageGraph Graph;
1.24 - typedef SmartGraph Graph ;
1.25 - //typedef ListGraph Graph;
1.26 - typedef Graph::Node Node;
1.27 - typedef Graph::NodeIt NodeIt;
1.28 - typedef Graph::Edge Edge;
1.29 - typedef Graph::EdgeIt EdgeIt;
1.30 - typedef Graph::OutEdgeIt OutEdgeIt;
1.31 -
1.32 - Graph g;
1.33 - readDimacs(std::cin, g);
1.34 - NodeIt s(g);
1.35 -
1.36 - cout << g.nodeNum() << endl;
1.37 - cout << g.edgeNum() << endl;
1.38 -
1.39 - Graph::NodeMap<Edge> pred(g);
1.40 - cout << "iteration time of bfs written by hand..." << endl;
1.41 - Timer ts;
1.42 - ts.reset();
1.43 - for (int i=0; i<100; ++i)
1.44 - {
1.45 - Graph::NodeMap<bool> reached(g);
1.46 - reached.set(s, true);
1.47 - pred.set(s, INVALID);
1.48 - std::queue<Node> bfs_queue;
1.49 - bfs_queue.push(s);
1.50 - while (!bfs_queue.empty()) {
1.51 - Node v=bfs_queue.front();
1.52 - bfs_queue.pop();
1.53 - for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
1.54 - Node w=g.target(e);
1.55 - if (!reached[w]) {
1.56 - bfs_queue.push(w);
1.57 - reached.set(w, true);
1.58 - pred.set(w, e);
1.59 - }
1.60 - }
1.61 - }
1.62 - }
1.63 - std::cout << ts << std::endl;
1.64 -
1.65 - cout << "iteration time with bfs iterator..." << endl;
1.66 - ts.reset();
1.67 - for (int i=0; i<100; ++i)
1.68 - {
1.69 - Graph::NodeMap<bool> reached(g);
1.70 - marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached);
1.71 - bfs.pushAndSetReached(s);
1.72 - pred.set(s, INVALID);
1.73 - while (!bfs.finished()) {
1.74 - ++bfs;
1.75 - if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached())
1.76 - pred.set(bfs.target(), Graph::Edge(bfs));
1.77 - }
1.78 - }
1.79 - std::cout << ts << std::endl;
1.80 -
1.81 - cout << "iteration time with bfs aplar..." << endl;
1.82 - ts.reset();
1.83 - for (int i=0; i<100; ++i)
1.84 - {
1.85 - Bfs<Graph> bfs(g);
1.86 - bfs.setPredMap(pred);
1.87 - bfs.run(s);
1.88 - }
1.89 - std::cout << ts << std::endl;
1.90 -
1.91 -
1.92 - return 0;
1.93 -}