1 #include <iostream> |
|
2 #include <vector> |
|
3 #include <string> |
|
4 |
|
5 #include <list_graph.hh> |
|
6 #include <bfs_iterator.hh> |
|
7 |
|
8 using namespace lemon; |
|
9 |
|
10 int main (int, char*[]) |
|
11 { |
|
12 typedef ListGraph::NodeIt NodeIt; |
|
13 typedef ListGraph::EdgeIt EdgeIt; |
|
14 typedef ListGraph::EachNodeIt EachNodeIt; |
|
15 typedef ListGraph::EachEdgeIt EachEdgeIt; |
|
16 typedef ListGraph::OutEdgeIt OutEdgeIt; |
|
17 typedef ListGraph::InEdgeIt InEdgeIt; |
|
18 typedef ListGraph::SymEdgeIt SymEdgeIt; |
|
19 |
|
20 ListGraph G; |
|
21 |
|
22 NodeIt s=G.addNode(); |
|
23 NodeIt v1=G.addNode(); |
|
24 NodeIt v2=G.addNode(); |
|
25 NodeIt v3=G.addNode(); |
|
26 NodeIt v4=G.addNode(); |
|
27 NodeIt t=G.addNode(); |
|
28 |
|
29 G.addEdge(s, v1); |
|
30 G.addEdge(s, v2); |
|
31 G.addEdge(v1, v2); |
|
32 G.addEdge(v2, v1); |
|
33 G.addEdge(v1, v3); |
|
34 G.addEdge(v3, v2); |
|
35 G.addEdge(v2, v4); |
|
36 G.addEdge(v4, v3); |
|
37 G.addEdge(v3, t); |
|
38 G.addEdge(v4, t); |
|
39 |
|
40 std::cout << "bfs and dfs demo on the directed graph" << std::endl; |
|
41 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) { |
|
42 std::cout << i << ": "; |
|
43 std::cout << "out edges: "; |
|
44 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) |
|
45 std::cout << j << " "; |
|
46 std::cout << "in edges: "; |
|
47 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) |
|
48 std::cout << j << " "; |
|
49 std::cout << std::endl; |
|
50 } |
|
51 |
|
52 //std::cout << std::endl; |
|
53 //EachNodeIt u1=G.first<EachNodeIt>(); |
|
54 //EachEdgeIt u=G.first<EachEdgeIt>(); |
|
55 //OutEdgeIt u=G.first<OutEdgeIt>(s); |
|
56 //InEdgeIt u=G.first<InEdgeIt>(s); |
|
57 //SymEdgeIt u=G.first<SymEdgeIt>(s); |
|
58 //OutEdgeIt u=G.first<OutEdgeIt>(s); |
|
59 //EachNodeIt u=G.first<EachNodeIt>(); |
|
60 //EachEdgeIt u=G.first<EachEdgeIt>(); |
|
61 //OutEdgeIt u=G.first<OutEdgeIt>(s); |
|
62 //InEdgeIt u=G.first<InEdgeIt>(s); |
|
63 //SymEdgeIt u=G.first<SymEdgeIt>(s); |
|
64 //u=G.first(s); |
|
65 //u=G.first_ize(s, OutEdgeIt()); |
|
66 //std::cout << "ize " << u << std::endl; |
|
67 |
|
68 /* |
|
69 { |
|
70 std::cout << "iterator bfs demo..." << std::endl; |
|
71 NodePropertyVector<ListGraph, bool> reached(G, false); |
|
72 reached.set(s, true); |
|
73 std::queue<ListGraph::OutEdgeIt> bfs_queue; |
|
74 bfs_queue.push(G.firstOutEdge(G.firstNode())); |
|
75 BfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > bfs(G, bfs_queue, reached); |
|
76 for ( ; !bfs.finished(); ++bfs) { |
|
77 if (OutEdgeIt(bfs).valid()) { |
|
78 std::cout << "OutEdgeIt: " << bfs; |
|
79 std::cout << " aNode: " << G.aNode(bfs); |
|
80 std::cout << " bNode: " << G.bNode(bfs) << " "; |
|
81 } else { |
|
82 std::cout << "OutEdgeIt: " << "invalid"; |
|
83 std::cout << " aNode: " << G.aNode(bfs); |
|
84 std::cout << " bNode: " << "invalid" << " "; |
|
85 } |
|
86 if (bfs.bNodeIsNewlyReached()) { |
|
87 std::cout << "bNodeIsNewlyReached "; |
|
88 } else { |
|
89 std::cout << "bNodeIsNotNewlyReached "; |
|
90 } |
|
91 if (bfs.aNodeIsExamined()) { |
|
92 std::cout << "aNodeIsExamined "; |
|
93 } else { |
|
94 std::cout << "aNodeIsNotExamined "; |
|
95 } |
|
96 std::cout<<std::endl; |
|
97 } |
|
98 } |
|
99 |
|
100 { |
|
101 std::cout << "iterator dfs demo..." << std::endl; |
|
102 NodePropertyVector<ListGraph, bool> reached(G, false); |
|
103 reached.set(s, true); |
|
104 std::stack<ListGraph::OutEdgeIt> dfs_stack; |
|
105 dfs_stack.push(G.firstOutEdge(G.firstNode())); |
|
106 DfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > dfs(G, dfs_stack, reached); |
|
107 for(; !dfs.finished(); ++dfs) { |
|
108 if (OutEdgeIt(dfs).valid()) { |
|
109 std::cout << "OutEdgeIt: " << dfs; |
|
110 std::cout << " aNode: " << G.aNode(dfs); |
|
111 std::cout << " bNode: " << G.bNode(dfs) << " "; |
|
112 } else { |
|
113 std::cout << "OutEdgeIt: " << "invalid"; |
|
114 std::cout << " aNode: " << G.aNode(dfs); |
|
115 std::cout << " bNode: " << "invalid" << " "; |
|
116 } |
|
117 if (dfs.bNodeIsNewlyReached()) { |
|
118 std::cout << "bNodeIsNewlyReached "; |
|
119 } else { |
|
120 std::cout << "bNodeIsNotNewlyReached "; |
|
121 } |
|
122 if (dfs.aNodeIsLeaved()) { |
|
123 std::cout << "aNodeIsLeaved "; |
|
124 } else { |
|
125 std::cout << "aNodeIsNotLeaved "; |
|
126 } |
|
127 std::cout<<std::endl; |
|
128 } |
|
129 if (OutEdgeIt(dfs).valid()) { |
|
130 std::cout << "OutEdgeIt: " << dfs; |
|
131 std::cout << " aNode: " << G.aNode(dfs); |
|
132 std::cout << " bNode: " << G.bNode(dfs) << " "; |
|
133 } else { |
|
134 std::cout << "OutEdgeIt: " << "invalid"; |
|
135 std::cout << " aNode: " << G.aNode(dfs); |
|
136 std::cout << " bNode: " << "invalid" << " "; |
|
137 } |
|
138 if (dfs.bNodeIsNewlyReached()) { |
|
139 std::cout << "bNodeIsNewlyReached "; |
|
140 } else { |
|
141 std::cout << "bNodeIsNotNewlyReached "; |
|
142 } |
|
143 if (dfs.aNodeIsLeaved()) { |
|
144 std::cout << "aNodeIsLeaved "; |
|
145 } else { |
|
146 std::cout << "aNodeIsNotLeaved "; |
|
147 } |
|
148 std::cout<<std::endl; |
|
149 } |
|
150 */ |
|
151 |
|
152 { |
|
153 std::cout << "iterator bfs demo 1 ..." << std::endl; |
|
154 ListGraph::NodeMap<bool> reached(G, false); |
|
155 reached.set(s, true); |
|
156 std::queue<ListGraph::OutEdgeIt> bfs_queue; |
|
157 bfs_queue.push(G.first<OutEdgeIt>(s)); |
|
158 BfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached); |
|
159 while (!bfs.finished()) { |
|
160 if (OutEdgeIt(bfs).valid()) { |
|
161 std::cout << "OutEdgeIt: " << bfs; |
|
162 std::cout << " aNode: " << G.aNode(bfs); |
|
163 std::cout << " bNode: " << G.bNode(bfs) << " "; |
|
164 } else { |
|
165 std::cout << "OutEdgeIt: " << "invalid"; |
|
166 std::cout << " aNode: " << G.aNode(bfs); |
|
167 std::cout << " bNode: " << "invalid" << " "; |
|
168 } |
|
169 if (bfs.bNodeIsNewlyReached()) { |
|
170 std::cout << "bNodeIsNewlyReached "; |
|
171 } else { |
|
172 std::cout << "bNodeIsNotNewlyReached "; |
|
173 } |
|
174 if (bfs.aNodeIsExamined()) { |
|
175 std::cout << "aNodeIsExamined "; |
|
176 } else { |
|
177 std::cout << "aNodeIsNotExamined "; |
|
178 } |
|
179 std::cout<<std::endl; |
|
180 bfs.next(); |
|
181 } |
|
182 } |
|
183 |
|
184 { |
|
185 std::cout << "iterator bfs demo 2 ..." << std::endl; |
|
186 //ListGraph::NodeMap<bool> reached(G, false); |
|
187 //reached.set(s, true); |
|
188 //std::queue<ListGraph::OutEdgeIt> bfs_queue; |
|
189 //bfs_queue.push(G.first<OutEdgeIt>(s)); |
|
190 BfsIterator2< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G); |
|
191 bfs.pushAndSetReached(s); |
|
192 while (!bfs.finished()) { |
|
193 if (OutEdgeIt(bfs).valid()) { |
|
194 std::cout << "OutEdgeIt: " << bfs; |
|
195 std::cout << " aNode: " << G.aNode(bfs); |
|
196 std::cout << " bNode: " << G.bNode(bfs) << " "; |
|
197 } else { |
|
198 std::cout << "OutEdgeIt: " << "invalid"; |
|
199 std::cout << " aNode: " << G.aNode(bfs); |
|
200 std::cout << " bNode: " << "invalid" << " "; |
|
201 } |
|
202 if (bfs.isBNodeNewlyReached()) { |
|
203 std::cout << "bNodeIsNewlyReached "; |
|
204 } else { |
|
205 std::cout << "bNodeIsNotNewlyReached "; |
|
206 } |
|
207 if (bfs.isANodeExamined()) { |
|
208 std::cout << "aNodeIsExamined "; |
|
209 } else { |
|
210 std::cout << "aNodeIsNotExamined "; |
|
211 } |
|
212 std::cout<<std::endl; |
|
213 ++bfs; |
|
214 } |
|
215 } |
|
216 |
|
217 |
|
218 |
|
219 |
|
220 { |
|
221 std::cout << "iterator dfs demo 1..." << std::endl; |
|
222 ListGraph::NodeMap<bool> reached(G, false); |
|
223 reached.set(s, true); |
|
224 std::stack<ListGraph::OutEdgeIt> dfs_stack; |
|
225 dfs_stack.push(G.first<OutEdgeIt>(s)); |
|
226 DfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G, dfs_stack, reached); |
|
227 do { |
|
228 dfs.next(); |
|
229 if (OutEdgeIt(dfs).valid()) { |
|
230 std::cout << "OutEdgeIt: " << dfs; |
|
231 std::cout << " aNode: " << G.aNode(dfs); |
|
232 std::cout << " bNode: " << G.bNode(dfs) << " "; |
|
233 } else { |
|
234 std::cout << "OutEdgeIt: " << "invalid"; |
|
235 std::cout << " aNode: " << G.aNode(dfs); |
|
236 std::cout << " bNode: " << "invalid" << " "; |
|
237 } |
|
238 if (dfs.bNodeIsNewlyReached()) { |
|
239 std::cout << "bNodeIsNewlyReached "; |
|
240 } else { |
|
241 std::cout << "bNodeIsNotNewlyReached "; |
|
242 } |
|
243 if (dfs.aNodeIsLeaved()) { |
|
244 std::cout << "aNodeIsLeaved "; |
|
245 } else { |
|
246 std::cout << "aNodeIsNotLeaved "; |
|
247 } |
|
248 std::cout<<std::endl; |
|
249 } while (!dfs.finished()); |
|
250 } |
|
251 |
|
252 |
|
253 { |
|
254 std::cout << "iterator bfs demo from node 5 with replacing \n OutEdgeIt by InEdgeIt ..." << std::endl; |
|
255 ListGraph::NodeMap<bool> reached(G, false); |
|
256 reached.set(t, true); |
|
257 std::queue<ListGraph::InEdgeIt> bfs_queue; |
|
258 bfs_queue.push(G.first<InEdgeIt>(t)); |
|
259 BfsIterator1< ListGraph, ListGraph::InEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached); |
|
260 while (!bfs.finished()) { |
|
261 if (InEdgeIt(bfs).valid()) { |
|
262 std::cout << "InEdgeIt: " << bfs; |
|
263 std::cout << " aNode: " << G.aNode(bfs); |
|
264 std::cout << " bNode: " << G.bNode(bfs) << " "; |
|
265 } else { |
|
266 std::cout << "InEdgeIt: " << "invalid"; |
|
267 std::cout << " aNode: " << G.aNode(bfs); |
|
268 std::cout << " bNode: " << "invalid" << " "; |
|
269 } |
|
270 if (bfs.bNodeIsNewlyReached()) { |
|
271 std::cout << "bNodeIsNewlyReached "; |
|
272 } else { |
|
273 std::cout << "bNodeIsNotNewlyReached "; |
|
274 } |
|
275 if (bfs.aNodeIsExamined()) { |
|
276 std::cout << "aNodeIsExamined "; |
|
277 } else { |
|
278 std::cout << "aNodeIsNotExamined "; |
|
279 } |
|
280 std::cout<<std::endl; |
|
281 bfs.next(); |
|
282 } |
|
283 } |
|
284 |
|
285 |
|
286 { |
|
287 std::cout << "the graph is considered as an undirected graph \n by replacing InEdgeIt by SymEdgeIt ..." << std::endl; |
|
288 ListGraph::NodeMap<bool> reached(G, false); |
|
289 reached.set(t, true); |
|
290 std::queue<ListGraph::SymEdgeIt> bfs_queue; |
|
291 bfs_queue.push(G.first<SymEdgeIt>(t)); |
|
292 BfsIterator1< ListGraph, ListGraph::SymEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached); |
|
293 while (!bfs.finished()) { |
|
294 if (SymEdgeIt(bfs).valid()) { |
|
295 std::cout << "SymEdgeIt: " << bfs; |
|
296 std::cout << " aNode: " << G.aNode(bfs); |
|
297 std::cout << " bNode: " << G.bNode(bfs) << " "; |
|
298 } else { |
|
299 std::cout << "SymEdgeIt: " << "invalid"; |
|
300 std::cout << " aNode: " << G.aNode(bfs); |
|
301 std::cout << " bNode: " << "invalid" << " "; |
|
302 } |
|
303 if (bfs.bNodeIsNewlyReached()) { |
|
304 std::cout << "bNodeIsNewlyReached "; |
|
305 } else { |
|
306 std::cout << "bNodeIsNotNewlyReached "; |
|
307 } |
|
308 if (bfs.aNodeIsExamined()) { |
|
309 std::cout << "aNodeIsExamined "; |
|
310 } else { |
|
311 std::cout << "aNodeIsNotExamined "; |
|
312 } |
|
313 std::cout<<std::endl; |
|
314 bfs.next(); |
|
315 } |
|
316 } |
|
317 |
|
318 return 0; |
|
319 } |
|