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