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 <smart_graph.h> |
6 #include <hugo/smart_graph.h> |
7 #include <hugo/dimacs.h> |
7 #include <hugo/dimacs.h> |
8 #include <hugo/time_measure.h> |
8 #include <hugo/time_measure.h> |
9 //#include <hugo/for_each_macros.h> |
9 //#include <hugo/for_each_macros.h> |
10 #include <bfs_dfs.h> |
10 #include <bfs_dfs.h> |
11 |
11 |
12 using namespace hugo; |
12 using namespace hugo; |
|
13 |
|
14 using std::cout; |
|
15 using std::endl; |
13 |
16 |
14 int main() { |
17 int main() { |
15 typedef SageGraph Graph; |
18 typedef SageGraph Graph; |
16 typedef Graph::Node Node; |
19 typedef Graph::Node Node; |
17 typedef Graph::NodeIt NodeIt; |
20 typedef Graph::NodeIt NodeIt; |
18 typedef Graph::Edge Edge; |
21 typedef Graph::Edge Edge; |
19 typedef Graph::EdgeIt EdgeIt; |
22 typedef Graph::EdgeIt EdgeIt; |
20 typedef Graph::OutEdgeIt OutEdgeIt; |
23 typedef Graph::OutEdgeIt OutEdgeIt; |
21 |
24 |
22 Graph g; |
25 Graph g; |
23 Node s, t; |
26 //Node s; |
24 //Graph::EdgeMap<int> cap(g); |
27 //Graph::EdgeMap<int> cap(g); |
25 //readDimacsMaxFlow(std::cin, g, s, t, cap); |
28 //readDimacsMaxFlow(std::cin, g, s, t, cap); |
26 readDimacs(std::cin, g); |
29 readDimacs(std::cin, g); |
|
30 NodeIt s; |
|
31 g.first(s); |
|
32 |
|
33 cout << g.nodeNum() << endl; |
|
34 cout << g.edgeNum() << endl; |
27 |
35 |
28 Graph::NodeMap<OutEdgeIt> pred(g); |
36 Graph::NodeMap<OutEdgeIt> pred(g); |
|
37 cout << "iteration time of bfs written by hand..." << endl; |
29 Timer ts; |
38 Timer ts; |
30 { |
39 { |
31 ts.reset(); |
40 ts.reset(); |
32 Graph::NodeMap<bool> reached(g); |
41 Graph::NodeMap<bool> reached(g); |
33 reached.set(s, true); |
42 reached.set(s, true); |
34 pred.set(s, INVALID); |
43 pred.set(s, INVALID); |
35 std::queue<Node> bfs_queue; |
44 std::queue<Node> bfs_queue; |
36 bfs_queue.push(t); |
45 bfs_queue.push(s); |
37 while (!bfs_queue.empty()) { |
46 while (!bfs_queue.empty()) { |
38 Node v=bfs_queue.front(); |
47 Node v=bfs_queue.front(); |
39 bfs_queue.pop(); |
48 bfs_queue.pop(); |
40 OutEdgeIt e; |
49 OutEdgeIt e; |
41 for(g.first(e,v); g.valid(e); g.next(e)) { |
50 for(g.first(e,v); g.valid(e); g.next(e)) { |