COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfsit_vs_byhand.cc @ 985:741f3108a90f

Last change on this file since 985:741f3108a90f was 944:4f064aff855e, checked in by marci, 15 years ago

It's time to design an iterable generic bfs

File size: 2.0 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5//#include <sage_graph.h>
6#include <lemon/smart_graph.h>
7#include <lemon/list_graph.h>
8#include <lemon/dimacs.h>
9#include <lemon/time_measure.h>
10//#include <lemon/for_each_macros.h>
11#include <bfs_mm.h>
12#include <lemon/bfs.h>
13
14using namespace lemon;
15
16using std::cout;
17using std::endl;
18
19int main() {
20  //  typedef SageGraph Graph;
21  typedef SmartGraph Graph ;
22  //typedef ListGraph Graph;
23  typedef Graph::Node Node;
24  typedef Graph::NodeIt NodeIt;
25  typedef Graph::Edge Edge;
26  typedef Graph::EdgeIt EdgeIt;
27  typedef Graph::OutEdgeIt OutEdgeIt;
28
29  Graph g;
30  readDimacs(std::cin, g);
31  NodeIt s(g);
32
33  cout << g.nodeNum() << endl;
34  cout << g.edgeNum() << endl;
35
36  Graph::NodeMap<Edge> pred(g);
37  cout << "iteration time of bfs written by hand..." << endl;
38  Timer ts;
39  ts.reset();
40  for (int i=0; i<100; ++i)
41  {
42    Graph::NodeMap<bool> reached(g);
43    reached.set(s, true);
44    pred.set(s, INVALID);
45    std::queue<Node> bfs_queue;
46    bfs_queue.push(s);
47    while (!bfs_queue.empty()) {
48      Node v=bfs_queue.front();
49      bfs_queue.pop();
50      for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
51        Node w=g.head(e);
52        if (!reached[w]) {
53          bfs_queue.push(w);
54          reached.set(w, true);
55          pred.set(w, e);
56        }
57      }
58    }
59  }
60  std::cout << ts << std::endl;
61
62  cout << "iteration time with bfs iterator..." << endl;
63  ts.reset();     
64  for (int i=0; i<100; ++i)
65  {
66    Graph::NodeMap<bool> reached(g);
67    marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached);
68    bfs.pushAndSetReached(s);
69    pred.set(s, INVALID);
70    while (!bfs.finished()) {
71      ++bfs;
72      if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached())
73        pred.set(bfs.head(), Graph::Edge(bfs));
74    }
75  }
76  std::cout << ts << std::endl;
77
78  cout << "iteration time with bfs aplar..." << endl;
79  ts.reset();     
80  for (int i=0; i<100; ++i)
81  {
82    Bfs<Graph> bfs(g);
83    bfs.setPredMap(pred);
84    bfs.run(s);
85  }
86  std::cout << ts << std::endl;
87
88
89  return 0;
90}
Note: See TracBrowser for help on using the repository browser.