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