1 // -*- c++ -*- |
|
2 #include <iostream> |
|
3 #include <fstream> |
|
4 |
|
5 //#include <sage_graph.h> |
|
6 #include <lemon/smart_graph.h> |
|
7 #include <lemon/list_graph.h> |
|
8 #include <lemon/dimacs.h> |
|
9 #include <lemon/time_measure.h> |
|
10 //#include <lemon/for_each_macros.h> |
|
11 #include <bfs_mm.h> |
|
12 #include <lemon/bfs.h> |
|
13 |
|
14 using namespace lemon; |
|
15 |
|
16 using std::cout; |
|
17 using std::endl; |
|
18 |
|
19 int main() { |
|
20 // typedef SageGraph Graph; |
|
21 typedef SmartGraph Graph ; |
|
22 //typedef ListGraph Graph; |
|
23 typedef Graph::Node Node; |
|
24 typedef Graph::NodeIt NodeIt; |
|
25 typedef Graph::Edge Edge; |
|
26 typedef Graph::EdgeIt EdgeIt; |
|
27 typedef Graph::OutEdgeIt OutEdgeIt; |
|
28 |
|
29 Graph g; |
|
30 readDimacs(std::cin, g); |
|
31 NodeIt s(g); |
|
32 |
|
33 cout << g.nodeNum() << endl; |
|
34 cout << g.edgeNum() << endl; |
|
35 |
|
36 Graph::NodeMap<Edge> pred(g); |
|
37 cout << "iteration time of bfs written by hand..." << endl; |
|
38 Timer ts; |
|
39 ts.reset(); |
|
40 for (int i=0; i<100; ++i) |
|
41 { |
|
42 Graph::NodeMap<bool> reached(g); |
|
43 reached.set(s, true); |
|
44 pred.set(s, INVALID); |
|
45 std::queue<Node> bfs_queue; |
|
46 bfs_queue.push(s); |
|
47 while (!bfs_queue.empty()) { |
|
48 Node v=bfs_queue.front(); |
|
49 bfs_queue.pop(); |
|
50 for(OutEdgeIt e(g,v); e!=INVALID; ++e) { |
|
51 Node w=g.target(e); |
|
52 if (!reached[w]) { |
|
53 bfs_queue.push(w); |
|
54 reached.set(w, true); |
|
55 pred.set(w, e); |
|
56 } |
|
57 } |
|
58 } |
|
59 } |
|
60 std::cout << ts << std::endl; |
|
61 |
|
62 cout << "iteration time with bfs iterator..." << endl; |
|
63 ts.reset(); |
|
64 for (int i=0; i<100; ++i) |
|
65 { |
|
66 Graph::NodeMap<bool> reached(g); |
|
67 marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached); |
|
68 bfs.pushAndSetReached(s); |
|
69 pred.set(s, INVALID); |
|
70 while (!bfs.finished()) { |
|
71 ++bfs; |
|
72 if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached()) |
|
73 pred.set(bfs.target(), Graph::Edge(bfs)); |
|
74 } |
|
75 } |
|
76 std::cout << ts << std::endl; |
|
77 |
|
78 cout << "iteration time with bfs aplar..." << endl; |
|
79 ts.reset(); |
|
80 for (int i=0; i<100; ++i) |
|
81 { |
|
82 Bfs<Graph> bfs(g); |
|
83 bfs.setPredMap(pred); |
|
84 bfs.run(s); |
|
85 } |
|
86 std::cout << ts << std::endl; |
|
87 |
|
88 |
|
89 return 0; |
|
90 } |
|