COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfsit_vs_byhand.cc @ 642:e812963087f0

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

To avoid confusion my old ListGraph? is can be used under name SageGraph?, work/sage_graph.h contains it.

File size: 1.4 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <sage_graph.h>
6//#include <smart_graph.h>
7#include <hugo/dimacs.h>
8#include <hugo/time_measure.h>
9#include <hugo/for_each_macros.h>
10#include <bfs_dfs.h>
11
12using namespace hugo;
13
14int main() {
15  typedef SageGraph 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  readDimacs(std::cin, g);
27
28  Graph::NodeMap<OutEdgeIt> pred(g);
29  Timer ts;
30  {
31    ts.reset();
32    Graph::NodeMap<bool> reached(g);
33    reached.set(s, true);
34    pred.set(s, INVALID);
35    std::queue<Node> bfs_queue;
36    bfs_queue.push(t);
37    while (!bfs_queue.empty()) {
38      Node v=bfs_queue.front();
39      bfs_queue.pop();
40      OutEdgeIt e;
41      for(g.first(e,v); g.valid(e); g.next(e)) {
42        Node w=g.head(e);
43        if (!reached[w]) {
44          bfs_queue.push(w);
45          reached.set(w, true);
46          pred.set(w, e);
47        }
48      }
49    }
50
51    std::cout << ts << std::endl;
52  }
53
54  {
55    ts.reset();     
56    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
57    bfs.pushAndSetReached(s);
58    pred.set(s, INVALID);
59    while (!bfs.finished()) {
60      ++bfs;
61      if (g.valid(bfs) && bfs.isBNodeNewlyReached())
62        pred.set(bfs.bNode(), bfs);
63    }
64    std::cout << ts << std::endl;
65  }
66
67  return 0;
68}
Note: See TracBrowser for help on using the repository browser.