|
1 #include <iostream> |
|
2 #include <vector> |
|
3 #include <string> |
|
4 |
|
5 #include <list_graph.hh> |
|
6 #include <bfs_iterator.hh> |
|
7 #include <graph_wrapper.h> |
|
8 |
|
9 using namespace marci; |
|
10 |
|
11 int main (int, char*[]) |
|
12 { |
|
13 typedef ListGraph::NodeIt NodeIt; |
|
14 typedef ListGraph::EdgeIt EdgeIt; |
|
15 typedef ListGraph::EachNodeIt EachNodeIt; |
|
16 typedef ListGraph::EachEdgeIt EachEdgeIt; |
|
17 typedef ListGraph::OutEdgeIt OutEdgeIt; |
|
18 typedef ListGraph::InEdgeIt InEdgeIt; |
|
19 typedef ListGraph::SymEdgeIt SymEdgeIt; |
|
20 |
|
21 ListGraph G; |
|
22 |
|
23 NodeIt s=G.addNode(); |
|
24 NodeIt v1=G.addNode(); |
|
25 NodeIt v2=G.addNode(); |
|
26 NodeIt v3=G.addNode(); |
|
27 NodeIt v4=G.addNode(); |
|
28 NodeIt t=G.addNode(); |
|
29 |
|
30 G.addEdge(s, v1); |
|
31 G.addEdge(s, v2); |
|
32 G.addEdge(v1, v2); |
|
33 G.addEdge(v2, v1); |
|
34 G.addEdge(v1, v3); |
|
35 G.addEdge(v3, v2); |
|
36 G.addEdge(v2, v4); |
|
37 G.addEdge(v4, v3); |
|
38 G.addEdge(v3, t); |
|
39 G.addEdge(v4, t); |
|
40 |
|
41 std::cout << "bfs and dfs demo on the directed graph" << std::endl; |
|
42 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { |
|
43 std::cout << i << ": "; |
|
44 std::cout << "out edges: "; |
|
45 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) |
|
46 std::cout << j << " "; |
|
47 std::cout << "in edges: "; |
|
48 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) |
|
49 std::cout << j << " "; |
|
50 std::cout << std::endl; |
|
51 } |
|
52 |
|
53 { |
|
54 std::cout << "iterator bfs demo 4 ..." << std::endl; |
|
55 BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G); |
|
56 bfs.pushAndSetReached(s); |
|
57 while (!bfs.finished()) { |
|
58 if (OutEdgeIt(bfs).valid()) { |
|
59 std::cout << "OutEdgeIt: " << bfs; |
|
60 std::cout << " aNode: " << G.aNode(bfs); |
|
61 std::cout << " bNode: " << G.bNode(bfs) << " "; |
|
62 } else { |
|
63 std::cout << "OutEdgeIt: " << "invalid"; |
|
64 std::cout << " aNode: " << bfs.aNode(); |
|
65 std::cout << " bNode: " << "invalid" << " "; |
|
66 } |
|
67 if (bfs.isBNodeNewlyReached()) { |
|
68 std::cout << "bNodeIsNewlyReached "; |
|
69 } else { |
|
70 std::cout << "bNodeIsNotNewlyReached "; |
|
71 } |
|
72 if (bfs.isANodeExamined()) { |
|
73 std::cout << "aNodeIsExamined "; |
|
74 } else { |
|
75 std::cout << "aNodeIsNotExamined "; |
|
76 } |
|
77 std::cout<<std::endl; |
|
78 ++bfs; |
|
79 } |
|
80 } |
|
81 |
|
82 typedef ConstTrivGraphWrapper<ListGraph> CTGW; |
|
83 CTGW wG(G); |
|
84 |
|
85 std::cout << "bfs and dfs demo on the directed graph" << std::endl; |
|
86 for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) { |
|
87 std::cout << i << ": "; |
|
88 std::cout << "out edges: "; |
|
89 for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j) |
|
90 std::cout << j << " "; |
|
91 std::cout << "in edges: "; |
|
92 for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j) |
|
93 std::cout << j << " "; |
|
94 std::cout << std::endl; |
|
95 } |
|
96 |
|
97 |
|
98 { |
|
99 std::cout << "iterator bfs demo 5 ..." << std::endl; |
|
100 BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG); |
|
101 bfs.pushAndSetReached(s); |
|
102 while (!bfs.finished()) { |
|
103 if (OutEdgeIt(bfs).valid()) { |
|
104 std::cout << "OutEdgeIt: " << bfs; |
|
105 std::cout << " aNode: " << wG.aNode(bfs); |
|
106 std::cout << " bNode: " << wG.bNode(bfs) << " "; |
|
107 } else { |
|
108 std::cout << "OutEdgeIt: " << "invalid"; |
|
109 std::cout << " aNode: " << bfs.aNode(); |
|
110 std::cout << " bNode: " << "invalid" << " "; |
|
111 } |
|
112 if (bfs.isBNodeNewlyReached()) { |
|
113 std::cout << "bNodeIsNewlyReached "; |
|
114 } else { |
|
115 std::cout << "bNodeIsNotNewlyReached "; |
|
116 } |
|
117 if (bfs.isANodeExamined()) { |
|
118 std::cout << "aNodeIsExamined "; |
|
119 } else { |
|
120 std::cout << "aNodeIsNotExamined "; |
|
121 } |
|
122 std::cout<<std::endl; |
|
123 ++bfs; |
|
124 } |
|
125 } |
|
126 |
|
127 |
|
128 return 0; |
|
129 } |