COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfsit_vs_byhand.cc @ 921:818510fa3d99

Last change on this file since 921:818510fa3d99 was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

File size: 1.6 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/dimacs.h>
8#include <lemon/time_measure.h>
9//#include <lemon/for_each_macros.h>
10#include <bfs_dfs.h>
11
12using namespace lemon;
13
14using std::cout;
15using std::endl;
16
17int main() {
18  typedef SageGraph Graph;
19  typedef Graph::Node Node;
20  typedef Graph::NodeIt NodeIt;
21  typedef Graph::Edge Edge;
22  typedef Graph::EdgeIt EdgeIt;
23  typedef Graph::OutEdgeIt OutEdgeIt;
24
25  Graph g;
26  //Node s;
27  //Graph::EdgeMap<int> cap(g);
28  //readDimacsMaxFlow(std::cin, g, s, t, cap);
29  readDimacs(std::cin, g);
30  NodeIt s;
31  g.first(s);
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  {
40    ts.reset();
41    Graph::NodeMap<bool> reached(g);
42    reached.set(s, true);
43    pred.set(s, INVALID);
44    std::queue<Node> bfs_queue;
45    bfs_queue.push(s);
46    while (!bfs_queue.empty()) {
47      Node v=bfs_queue.front();
48      bfs_queue.pop();
49      OutEdgeIt e;
50      for(g.first(e,v); g.valid(e); g.next(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
63  cout << "iteration time with bfs iterator..." << endl;
64  {
65    ts.reset();     
66    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
67    bfs.pushAndSetReached(s);
68    pred.set(s, INVALID);
69    while (!bfs.finished()) {
70      ++bfs;
71      if (g.valid(bfs) && bfs.isBNodeNewlyReached())
72        pred.set(bfs.head(), Graph::Edge(bfs));
73    }
74    std::cout << ts << std::endl;
75  }
76
77  return 0;
78}
Note: See TracBrowser for help on using the repository browser.