athos@671
|
1 |
// -*- c++ -*-
|
athos@671
|
2 |
#include <iostream>
|
athos@671
|
3 |
#include <fstream>
|
athos@671
|
4 |
|
athos@671
|
5 |
#include <sage_graph.h>
|
athos@671
|
6 |
//#include <smart_graph.h>
|
alpar@921
|
7 |
#include <lemon/dimacs.h>
|
alpar@921
|
8 |
#include <lemon/time_measure.h>
|
alpar@921
|
9 |
#include <lemon/for_each_macros.h>
|
athos@671
|
10 |
#include <bfs_dfs.h>
|
athos@671
|
11 |
|
alpar@921
|
12 |
using namespace lemon;
|
athos@671
|
13 |
|
athos@671
|
14 |
int main() {
|
athos@671
|
15 |
typedef SageGraph Graph;
|
athos@671
|
16 |
typedef Graph::Node Node;
|
athos@671
|
17 |
typedef Graph::NodeIt NodeIt;
|
athos@671
|
18 |
typedef Graph::Edge Edge;
|
athos@671
|
19 |
typedef Graph::EdgeIt EdgeIt;
|
athos@671
|
20 |
typedef Graph::OutEdgeIt OutEdgeIt;
|
athos@671
|
21 |
|
athos@671
|
22 |
Graph g;
|
athos@671
|
23 |
Node s, t;
|
athos@671
|
24 |
Graph::EdgeMap<int> cap(g);
|
athos@671
|
25 |
//readDimacsMaxFlow(std::cin, g, s, t, cap);
|
athos@671
|
26 |
readDimacs(std::cin, g);
|
athos@671
|
27 |
|
athos@671
|
28 |
Graph::NodeMap<OutEdgeIt> pred(g);
|
athos@671
|
29 |
|
athos@671
|
30 |
Timer ts;
|
athos@671
|
31 |
/*
|
athos@671
|
32 |
{
|
athos@671
|
33 |
ts.reset();
|
athos@671
|
34 |
Graph::NodeMap<bool> reached(g);
|
athos@671
|
35 |
reached.set(s, true);
|
athos@671
|
36 |
pred.set(s, INVALID);
|
athos@671
|
37 |
std::queue<Node> bfs_queue;
|
athos@671
|
38 |
bfs_queue.push(t);
|
athos@671
|
39 |
while (!bfs_queue.empty()) {
|
athos@671
|
40 |
Node v=bfs_queue.front();
|
athos@671
|
41 |
bfs_queue.pop();
|
athos@671
|
42 |
OutEdgeIt e;
|
athos@671
|
43 |
for(g.first(e,v); g.valid(e); g.next(e)) {
|
alpar@986
|
44 |
Node w=g.target(e);
|
athos@671
|
45 |
if (!reached[w]) {
|
athos@671
|
46 |
bfs_queue.push(w);
|
athos@671
|
47 |
reached.set(w, true);
|
athos@671
|
48 |
pred.set(w, e);
|
athos@671
|
49 |
}
|
athos@671
|
50 |
}
|
athos@671
|
51 |
}
|
athos@671
|
52 |
|
athos@671
|
53 |
std::cout << ts << std::endl;
|
athos@671
|
54 |
}
|
athos@671
|
55 |
*/
|
athos@671
|
56 |
|
athos@671
|
57 |
{
|
athos@671
|
58 |
ts.reset();
|
athos@671
|
59 |
Graph::NodeMap<bool> bfs_reached(g);
|
athos@671
|
60 |
Graph::NodeMap<Edge> bfs_pred(g);
|
athos@671
|
61 |
Graph::NodeMap<int> bfs_dist(g);
|
athos@671
|
62 |
|
athos@671
|
63 |
Bfs< Graph, Graph::NodeMap<bool>,
|
athos@671
|
64 |
Graph::NodeMap<Edge>, Graph::NodeMap<int> >
|
athos@671
|
65 |
bfs(g,bfs_reached, bfs_pred, bfs_dist );
|
athos@671
|
66 |
bfs.run(s);
|
athos@671
|
67 |
/*
|
athos@671
|
68 |
pred.set(s, INVALID);
|
athos@671
|
69 |
while (!bfs.finished()) {
|
athos@671
|
70 |
++bfs;
|
athos@671
|
71 |
if (g.valid(bfs) && bfs.isBNodeNewlyReached())
|
athos@671
|
72 |
pred.set(bfs.bNode(), bfs);
|
athos@671
|
73 |
}
|
athos@671
|
74 |
*/
|
athos@671
|
75 |
std::cout << ts << std::endl;
|
athos@671
|
76 |
}
|
athos@671
|
77 |
|
athos@671
|
78 |
return 0;
|
athos@671
|
79 |
}
|