COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfsit_vs_byhand.cc @ 358:caf183989ec4

Last change on this file since 358:caf183989ec4 was 358:caf183989ec4, checked in by marci, 20 years ago

time comparison for bfs iterator and iterator by hand

File size: 1.4 KB
RevLine 
[358]1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <list_graph.h>
6#include <smart_graph.h>
7#include <dimacs.h>
8#include <time_measure.h>
9#include <for_each_macros.h>
10#include <bfs_iterator.h>
11
12using namespace hugo;
13
14int main() {
15  typedef ListGraph Graph;
16  typedef Graph::Node Node;
17  typedef Graph::NodeIt NodeIt;
18  typedef Graph::Edge Edge;
19  typedef Graph::EdgeIt EdgeIt;
20  typedef Graph::OutEdgeIt OutEdgeIt;
21
22  Graph G;
23  Node s, t;
24  Graph::EdgeMap<int> cap(G);
25  readDimacsMaxFlow(std::cin, G, s, t, cap);
26  Graph::NodeMap<OutEdgeIt> pred(G);
27  Timer ts;
28  {
29    ts.reset();
30    Graph::NodeMap<bool> reached(G);
31    /*Reverse_bfs from t, to find the starting level.*/
32    reached.set(s, true);
33    pred.set(s, INVALID);
34    std::queue<Node> bfs_queue;
35    bfs_queue.push(t);
36    while (!bfs_queue.empty()) {
37      Node v=bfs_queue.front();
38      bfs_queue.pop();
39      OutEdgeIt e;
40      for(G.first(e,v); G.valid(e); G.next(e)) {
41        Node w=G.head(e);
42        if (!reached[w]) {
43          bfs_queue.push(w);
44          reached.set(w, true);
45          pred.set(w, e);
46        }
47      }
48    }
49
50    std::cout << ts << std::endl;
51  }
52
53  {
54    ts.reset();     
55    BfsIterator5< Graph, Graph::NodeMap<bool> > bfs(G);
56    bfs.pushAndSetReached(s);
57    pred.set(s, INVALID);
58    while (!bfs.finished()) {
59      ++bfs;
60      if (G.valid(bfs) && bfs.isBNodeNewlyReached())
61        pred.set(bfs.bNode(), bfs);
62    }
63    std::cout << ts << std::endl;
64  }
65
66  return 0;
67}
Note: See TracBrowser for help on using the repository browser.