COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfsit_vs_byhand.cc @ 360:91fba31268d6

Last change on this file since 360:91fba31268d6 was 360:91fba31268d6, checked in by marci, 16 years ago

work/marci/bfs_iterator.h BfsIterator5 -> BfsIterator?, DfsIterator5 -> DfsIterator?

File size: 1.4 KB
Line 
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    reached.set(s, true);
32    pred.set(s, INVALID);
33    std::queue<Node> bfs_queue;
34    bfs_queue.push(t);
35    while (!bfs_queue.empty()) {
36      Node v=bfs_queue.front();
37      bfs_queue.pop();
38      OutEdgeIt e;
39      for(G.first(e,v); G.valid(e); G.next(e)) {
40        Node w=G.head(e);
41        if (!reached[w]) {
42          bfs_queue.push(w);
43          reached.set(w, true);
44          pred.set(w, e);
45        }
46      }
47    }
48
49    std::cout << ts << std::endl;
50  }
51
52  {
53    ts.reset();     
54    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
55    bfs.pushAndSetReached(s);
56    pred.set(s, INVALID);
57    while (!bfs.finished()) {
58      ++bfs;
59      if (G.valid(bfs) && bfs.isBNodeNewlyReached())
60        pred.set(bfs.bNode(), bfs);
61    }
62    std::cout << ts << std::endl;
63  }
64
65  return 0;
66}
Note: See TracBrowser for help on using the repository browser.