COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfsit_vs_byhand.cc @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 15 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 2.0 KB
RevLine 
[358]1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
[944]5//#include <sage_graph.h>
[921]6#include <lemon/smart_graph.h>
[944]7#include <lemon/list_graph.h>
[921]8#include <lemon/dimacs.h>
9#include <lemon/time_measure.h>
10//#include <lemon/for_each_macros.h>
[944]11#include <bfs_mm.h>
12#include <lemon/bfs.h>
[358]13
[921]14using namespace lemon;
[358]15
[773]16using std::cout;
17using std::endl;
18
[358]19int main() {
[944]20  //  typedef SageGraph Graph;
21  typedef SmartGraph Graph ;
22  //typedef ListGraph Graph;
[358]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
[577]29  Graph g;
30  readDimacs(std::cin, g);
[944]31  NodeIt s(g);
[773]32
33  cout << g.nodeNum() << endl;
34  cout << g.edgeNum() << endl;
[577]35
[777]36  Graph::NodeMap<Edge> pred(g);
[773]37  cout << "iteration time of bfs written by hand..." << endl;
[358]38  Timer ts;
[944]39  ts.reset();
40  for (int i=0; i<100; ++i)
[358]41  {
[577]42    Graph::NodeMap<bool> reached(g);
[358]43    reached.set(s, true);
44    pred.set(s, INVALID);
45    std::queue<Node> bfs_queue;
[773]46    bfs_queue.push(s);
[358]47    while (!bfs_queue.empty()) {
48      Node v=bfs_queue.front();
49      bfs_queue.pop();
[944]50      for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
[986]51        Node w=g.target(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  }
[944]60  std::cout << ts << std::endl;
[358]61
[773]62  cout << "iteration time with bfs iterator..." << endl;
[944]63  ts.reset();     
64  for (int i=0; i<100; ++i)
[358]65  {
[944]66    Graph::NodeMap<bool> reached(g);
67    marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached);
[358]68    bfs.pushAndSetReached(s);
69    pred.set(s, INVALID);
70    while (!bfs.finished()) {
71      ++bfs;
[944]72      if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached())
[986]73        pred.set(bfs.target(), Graph::Edge(bfs));
[358]74    }
75  }
[944]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
[358]88
89  return 0;
90}
Note: See TracBrowser for help on using the repository browser.