COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfsit_vs_byhand.cc @ 773:ce9438c5a82d

Last change on this file since 773:ce9438c5a82d was 773:ce9438c5a82d, checked in by marci, 17 years ago

bug fix, test...

File size: 1.6 KB
RevLine 
[358]1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
[642]5#include <sage_graph.h>
[773]6#include <hugo/smart_graph.h>
[555]7#include <hugo/dimacs.h>
8#include <hugo/time_measure.h>
[762]9//#include <hugo/for_each_macros.h>
[602]10#include <bfs_dfs.h>
[358]11
12using namespace hugo;
13
[773]14using std::cout;
15using std::endl;
16
[358]17int main() {
[642]18  typedef SageGraph Graph;
[358]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
[577]25  Graph g;
[773]26  //Node s;
[762]27  //Graph::EdgeMap<int> cap(g);
[577]28  //readDimacsMaxFlow(std::cin, g, s, t, cap);
29  readDimacs(std::cin, g);
[773]30  NodeIt s;
31  g.first(s);
32
33  cout << g.nodeNum() << endl;
34  cout << g.edgeNum() << endl;
[577]35
36  Graph::NodeMap<OutEdgeIt> pred(g);
[773]37  cout << "iteration time of bfs written by hand..." << endl;
[358]38  Timer ts;
39  {
40    ts.reset();
[577]41    Graph::NodeMap<bool> reached(g);
[358]42    reached.set(s, true);
43    pred.set(s, INVALID);
44    std::queue<Node> bfs_queue;
[773]45    bfs_queue.push(s);
[358]46    while (!bfs_queue.empty()) {
47      Node v=bfs_queue.front();
48      bfs_queue.pop();
49      OutEdgeIt e;
[577]50      for(g.first(e,v); g.valid(e); g.next(e)) {
51        Node w=g.head(e);
[358]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
[773]63  cout << "iteration time with bfs iterator..." << endl;
[358]64  {
65    ts.reset();     
[577]66    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
[358]67    bfs.pushAndSetReached(s);
68    pred.set(s, INVALID);
69    while (!bfs.finished()) {
70      ++bfs;
[577]71      if (g.valid(bfs) && bfs.isBNodeNewlyReached())
[358]72        pred.set(bfs.bNode(), bfs);
73    }
74    std::cout << ts << std::endl;
75  }
76
77  return 0;
78}
Note: See TracBrowser for help on using the repository browser.