6 #include <hugo/dimacs.h> |
6 #include <hugo/dimacs.h> |
7 #include <bfs_dfs_misc.h> |
7 #include <bfs_dfs_misc.h> |
8 #include <list_graph.h> |
8 #include <list_graph.h> |
9 #include <hugo/graph_wrapper.h> |
9 #include <hugo/graph_wrapper.h> |
10 #include <hugo/maps.h> |
10 #include <hugo/maps.h> |
|
11 #include <for_each_macros.h> |
11 |
12 |
12 using namespace hugo; |
13 using namespace hugo; |
|
14 |
|
15 using std::cout; |
|
16 using std::endl; |
13 |
17 |
14 int main() { |
18 int main() { |
15 typedef ListGraph Graph; |
19 typedef ListGraph Graph; |
16 Graph g; |
20 Graph g; |
17 readDimacs(std::cin, g); |
21 readDimacs(std::cin, g); |
|
22 |
18 { |
23 { |
19 std::list<Graph::Node> l; |
24 std::list<Graph::Node> l; |
20 NullMap<Graph::Node, Graph::Edge> pred; |
25 //NullMap<Graph::Node, Graph::Edge> pred; |
|
26 Graph::NodeMap<Graph::Edge> pred(g, INVALID); |
21 topSort(g, l, pred); |
27 topSort(g, l, pred); |
22 std::cout << "Leaving order of dfs which is pretopological..." << std::endl; |
28 cout << "Leaving order of dfs which is pretopological..." << endl; |
23 for(std::list<Graph::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) { |
29 for(std::list<Graph::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) { |
24 std::cout << *i << " "; |
30 cout << *i << " "; |
25 } |
31 } |
26 std::cout << std::endl; |
32 cout << endl; |
|
33 |
|
34 FOR_EACH_LOC(Graph::NodeIt, n, g) { |
|
35 cout << "pred of node " << n << " is " << pred[n] << endl; |
|
36 } |
27 } |
37 } |
28 |
38 |
29 { |
39 { |
30 typedef RevGraphWrapper<Graph> GW; |
40 typedef RevGraphWrapper<Graph> GW; |
31 GW gw(g); |
41 GW gw(g); |
32 std::list<GW::Node> l; |
42 std::list<GW::Node> l; |
33 NullMap<GW::Node, GW::Edge> pred; |
43 //NullMap<GW::Node, GW::Edge> pred; |
|
44 GW::NodeMap<Graph::Edge> pred(gw, INVALID); |
34 topSort(gw, l, pred); |
45 topSort(gw, l, pred); |
35 std::cout << "Same in the revered oriented graph..." << std::endl; |
46 cout << "Same in the reversed oriented graph..." << endl; |
36 for(std::list<GW::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) { |
47 for(std::list<GW::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) { |
37 std::cout << *i << " "; |
48 cout << *i << " "; |
38 } |
49 } |
39 std::cout << std::endl; |
50 cout << endl; |
|
51 |
|
52 FOR_EACH_LOC(GW::NodeIt, n, gw) { |
|
53 cout << "pred of node " << n << " is " << pred[n] << endl; |
|
54 } |
40 } |
55 } |
41 |
56 |
42 return 0; |
57 return 0; |
43 } |
58 } |