COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/bfs_test.cc @ 1314:9269c76551cf

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

Naming changes:

  • head -> target
  • tail -> source
File size: 1.6 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <sage_graph.h>
6//#include <smart_graph.h>
7#include <lemon/dimacs.h>
8#include <lemon/time_measure.h>
9#include <lemon/for_each_macros.h>
10#include <bfs_dfs.h>
11
12using namespace lemon;
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
30  Timer ts;
31  /*
32  {
33    ts.reset();
34    Graph::NodeMap<bool> reached(g);
35    reached.set(s, true);
36    pred.set(s, INVALID);
37    std::queue<Node> bfs_queue;
38    bfs_queue.push(t);
39    while (!bfs_queue.empty()) {
40      Node v=bfs_queue.front();
41      bfs_queue.pop();
42      OutEdgeIt e;
43      for(g.first(e,v); g.valid(e); g.next(e)) {
44        Node w=g.target(e);
45        if (!reached[w]) {
46          bfs_queue.push(w);
47          reached.set(w, true);
48          pred.set(w, e);
49        }
50      }
51    }
52
53    std::cout << ts << std::endl;
54  }
55  */
56
57  {
58    ts.reset();
59    Graph::NodeMap<bool> bfs_reached(g);
60    Graph::NodeMap<Edge> bfs_pred(g);
61    Graph::NodeMap<int> bfs_dist(g);
62     
63    Bfs< Graph, Graph::NodeMap<bool>,
64      Graph::NodeMap<Edge>, Graph::NodeMap<int> >
65      bfs(g,bfs_reached, bfs_pred, bfs_dist );
66    bfs.run(s);
67    /*
68    pred.set(s, INVALID);
69    while (!bfs.finished()) {
70      ++bfs;
71      if (g.valid(bfs) && bfs.isBNodeNewlyReached())
72        pred.set(bfs.bNode(), bfs);
73    }
74    */
75    std::cout << ts << std::endl;
76  }
77
78  return 0;
79}
Note: See TracBrowser for help on using the repository browser.