COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfsit_vs_byhand.cc @ 762:511200bdb71f

Last change on this file since 762:511200bdb71f was 762:511200bdb71f, checked in by marci, 20 years ago

technical corrections

File size: 1.4 KB
RevLine 
[358]1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
[642]5#include <sage_graph.h>
[389]6//#include <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
14int main() {
[642]15  typedef SageGraph Graph;
[358]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
[577]22  Graph g;
[358]23  Node s, t;
[762]24  //Graph::EdgeMap<int> cap(g);
[577]25  //readDimacsMaxFlow(std::cin, g, s, t, cap);
26  readDimacs(std::cin, g);
27
28  Graph::NodeMap<OutEdgeIt> pred(g);
[358]29  Timer ts;
30  {
31    ts.reset();
[577]32    Graph::NodeMap<bool> reached(g);
[358]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;
[577]41      for(g.first(e,v); g.valid(e); g.next(e)) {
42        Node w=g.head(e);
[358]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();     
[577]56    BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
[358]57    bfs.pushAndSetReached(s);
58    pred.set(s, INVALID);
59    while (!bfs.finished()) {
60      ++bfs;
[577]61      if (g.valid(bfs) && bfs.isBNodeNewlyReached())
[358]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.