76 cout << " \\ | --/ / | | / "<< endl; |
76 cout << " \\ | --/ / | | / "<< endl; |
77 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
77 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
78 cout << " \\--> -------------> "<< endl; |
78 cout << " \\--> -------------> "<< endl; |
79 |
79 |
80 // typedef TrivGraphWrapper<const Graph> CGW; |
80 // typedef TrivGraphWrapper<const Graph> CGW; |
81 // CGW wG(G); |
81 // CGW gw(G); |
82 |
82 |
83 // cout << "bfs and dfs demo on the directed graph" << endl; |
83 // cout << "bfs and dfs demo on the directed graph" << endl; |
84 // for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) { |
84 // for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) { |
85 // cout << n << ": "; |
85 // cout << n << ": "; |
86 // cout << "out edges: "; |
86 // cout << "out edges: "; |
87 // for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e) |
87 // for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e) |
88 // cout << e << " "; |
88 // cout << e << " "; |
89 // cout << "in edges: "; |
89 // cout << "in edges: "; |
90 // for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e) |
90 // for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e) |
91 // cout << e << " "; |
91 // cout << e << " "; |
92 // cout << endl; |
92 // cout << endl; |
93 // } |
93 // } |
94 |
94 |
95 { |
95 { |
96 typedef TrivGraphWrapper<const Graph> GW; |
96 typedef TrivGraphWrapper<const Graph> GW; |
97 GW wG(G); |
97 GW gw(G); |
98 |
98 |
99 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name); |
99 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
100 |
100 |
101 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
101 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
102 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { |
102 for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { |
103 cout << node_name.get(n) << ": "; |
103 cout << node_name.get(n) << ": "; |
104 cout << "out edges: "; |
104 cout << "out edges: "; |
105 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) |
105 for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) |
106 cout << edge_name.get(e) << " "; |
106 cout << edge_name.get(e) << " "; |
107 cout << "in edges: "; |
107 cout << "in edges: "; |
108 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) |
108 for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) |
109 cout << edge_name.get(e) << " "; |
109 cout << edge_name.get(e) << " "; |
110 cout << endl; |
110 cout << endl; |
111 } |
111 } |
112 |
112 |
113 cout << "bfs from s ..." << endl; |
113 cout << "bfs from s ..." << endl; |
114 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); |
114 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
115 bfs.pushAndSetReached(s); |
115 bfs.pushAndSetReached(s); |
116 while (!bfs.finished()) { |
116 while (!bfs.finished()) { |
117 //cout << "edge: "; |
117 //cout << "edge: "; |
118 if (wG.valid(bfs)) { |
118 if (gw.valid(bfs)) { |
119 cout << edge_name.get(bfs) << /*endl*/", " << |
119 cout << edge_name.get(bfs) << /*endl*/", " << |
120 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << |
120 node_name.get(gw.aNode(bfs)) << |
121 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
121 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
122 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << |
122 node_name.get(gw.bNode(bfs)) << |
123 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
123 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
124 ": is not newly reached."); |
124 ": is not newly reached."); |
125 } else { |
125 } else { |
126 cout << "invalid" << /*endl*/", " << |
126 cout << "invalid" << /*endl*/", " << |
127 /*" aNode: " <<*/ node_name.get(bfs.aNode()) << |
127 node_name.get(bfs.aNode()) << |
128 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
128 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
129 /*" bNode: " <<*/ |
129 |
130 "invalid."; |
130 "invalid."; |
131 } |
131 } |
132 cout << endl; |
132 cout << endl; |
133 ++bfs; |
133 ++bfs; |
134 } |
134 } |
142 cout << " \\ | --/ / | | / "<< endl; |
142 cout << " \\ | --/ / | | / "<< endl; |
143 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
143 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
144 cout << " \\--> -------------> "<< endl; |
144 cout << " \\--> -------------> "<< endl; |
145 |
145 |
146 cout << "dfs from s ..." << endl; |
146 cout << "dfs from s ..." << endl; |
147 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); |
147 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
148 dfs.pushAndSetReached(s); |
148 dfs.pushAndSetReached(s); |
149 while (!dfs.finished()) { |
149 while (!dfs.finished()) { |
150 ++dfs; |
150 ++dfs; |
151 //cout << "edge: "; |
151 //cout << "edge: "; |
152 if (wG.valid(dfs)) { |
152 if (gw.valid(dfs)) { |
153 cout << edge_name.get(dfs) << /*endl*/", " << |
153 cout << edge_name.get(dfs) << /*endl*/", " << |
154 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << |
154 node_name.get(gw.aNode(dfs)) << |
155 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
155 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
156 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << |
156 node_name.get(gw.bNode(dfs)) << |
157 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
157 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
158 ": is not newly reached."); |
158 ": is not newly reached."); |
159 } else { |
159 } else { |
160 cout << "invalid" << /*endl*/", " << |
160 cout << "invalid" << /*endl*/", " << |
161 /*" aNode: " <<*/ node_name.get(dfs.aNode()) << |
161 node_name.get(dfs.aNode()) << |
162 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
162 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
163 /*" bNode: " <<*/ |
163 |
164 "invalid."; |
164 "invalid."; |
165 } |
165 } |
166 cout << endl; |
166 cout << endl; |
167 } |
167 } |
168 } |
168 } |
169 |
169 |
170 |
170 |
171 { |
171 { |
172 typedef RevGraphWrapper<const Graph> GW; |
172 typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW; |
173 GW wG(G); |
173 GW gw(G); |
174 |
174 |
175 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name); |
175 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
176 |
176 |
177 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; |
177 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; |
178 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { |
178 for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { |
179 cout << node_name.get(n) << ": "; |
179 cout << node_name.get(n) << ": "; |
180 cout << "out edges: "; |
180 cout << "out edges: "; |
181 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) |
181 for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) |
182 cout << edge_name.get(e) << " "; |
182 cout << edge_name.get(e) << " "; |
183 cout << "in edges: "; |
183 cout << "in edges: "; |
184 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) |
184 for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) |
185 cout << edge_name.get(e) << " "; |
185 cout << edge_name.get(e) << " "; |
186 cout << endl; |
186 cout << endl; |
187 } |
187 } |
188 |
188 |
189 cout << "bfs from t ..." << endl; |
189 cout << "bfs from t ..." << endl; |
190 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); |
190 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
191 bfs.pushAndSetReached(t); |
191 bfs.pushAndSetReached(t); |
192 while (!bfs.finished()) { |
192 while (!bfs.finished()) { |
193 //cout << "edge: "; |
193 //cout << "edge: "; |
194 if (wG.valid(bfs)) { |
194 if (gw.valid(bfs)) { |
195 cout << edge_name.get(bfs) << /*endl*/", " << |
195 cout << edge_name.get(bfs) << /*endl*/", " << |
196 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << |
196 node_name.get(gw.aNode(bfs)) << |
197 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
197 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
198 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << |
198 node_name.get(gw.bNode(bfs)) << |
199 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
199 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
200 ": is not newly reached."); |
200 ": is not newly reached."); |
201 } else { |
201 } else { |
202 cout << "invalid" << /*endl*/", " << |
202 cout << "invalid" << /*endl*/", " << |
203 /*" aNode: " <<*/ node_name.get(bfs.aNode()) << |
203 node_name.get(bfs.aNode()) << |
204 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
204 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
205 /*" bNode: " <<*/ |
205 |
206 "invalid."; |
206 "invalid."; |
207 } |
207 } |
208 cout << endl; |
208 cout << endl; |
209 ++bfs; |
209 ++bfs; |
210 } |
210 } |
218 cout << " \\ | --/ / | | / "<< endl; |
218 cout << " \\ | --/ / | | / "<< endl; |
219 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
219 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
220 cout << " \\--> -------------> "<< endl; |
220 cout << " \\--> -------------> "<< endl; |
221 |
221 |
222 cout << "dfs from t ..." << endl; |
222 cout << "dfs from t ..." << endl; |
223 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); |
223 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
224 dfs.pushAndSetReached(t); |
224 dfs.pushAndSetReached(t); |
225 while (!dfs.finished()) { |
225 while (!dfs.finished()) { |
226 ++dfs; |
226 ++dfs; |
227 //cout << "edge: "; |
227 //cout << "edge: "; |
228 if (wG.valid(dfs)) { |
228 if (gw.valid(dfs)) { |
229 cout << edge_name.get(dfs) << /*endl*/", " << |
229 cout << edge_name.get(dfs) << /*endl*/", " << |
230 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << |
230 node_name.get(gw.aNode(dfs)) << |
231 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
231 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
232 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << |
232 node_name.get(gw.bNode(dfs)) << |
233 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
233 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
234 ": is not newly reached."); |
234 ": is not newly reached."); |
235 } else { |
235 } else { |
236 cout << "invalid" << /*endl*/", " << |
236 cout << "invalid" << /*endl*/", " << |
237 /*" aNode: " <<*/ node_name.get(dfs.aNode()) << |
237 node_name.get(dfs.aNode()) << |
238 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
238 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
239 /*" bNode: " <<*/ |
239 |
240 "invalid."; |
240 "invalid."; |
241 } |
241 } |
242 cout << endl; |
242 cout << endl; |
243 } |
243 } |
244 } |
244 } |
245 |
245 |
246 { |
246 { |
247 typedef UndirGraphWrapper<const Graph> GW; |
247 typedef UndirGraphWrapper<const Graph> GW; |
248 GW wG(G); |
248 GW gw(G); |
249 |
249 |
250 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name); |
250 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
251 |
251 |
252 cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
252 cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
253 for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { |
253 for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { |
254 cout << node_name.get(n) << ": "; |
254 cout << node_name.get(n) << ": "; |
255 cout << "out edges: "; |
255 cout << "out edges: "; |
256 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) |
256 for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) |
257 cout << edge_name.get(e) << " "; |
257 cout << edge_name.get(e) << " "; |
258 cout << "in edges: "; |
258 cout << "in edges: "; |
259 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) |
259 for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) |
260 cout << edge_name.get(e) << " "; |
260 cout << edge_name.get(e) << " "; |
261 cout << endl; |
261 cout << endl; |
262 } |
262 } |
263 |
263 |
264 cout << "bfs from t ..." << endl; |
264 cout << "bfs from t ..." << endl; |
265 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); |
265 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
266 bfs.pushAndSetReached(t); |
266 bfs.pushAndSetReached(t); |
267 while (!bfs.finished()) { |
267 while (!bfs.finished()) { |
268 //cout << "edge: "; |
268 //cout << "edge: "; |
269 if (wG.valid(GW::OutEdgeIt(bfs))) { |
269 if (gw.valid(GW::OutEdgeIt(bfs))) { |
270 cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << |
270 cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << |
271 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << |
271 node_name.get(gw.aNode(bfs)) << |
272 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
272 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
273 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << |
273 node_name.get(gw.bNode(bfs)) << |
274 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
274 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
275 ": is not newly reached."); |
275 ": is not newly reached."); |
276 } else { |
276 } else { |
277 cout << "invalid" << /*endl*/", " << |
277 cout << "invalid" << /*endl*/", " << |
278 /*" aNode: " <<*/ node_name.get(bfs.aNode()) << |
278 node_name.get(bfs.aNode()) << |
279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
280 /*" bNode: " <<*/ |
280 |
281 "invalid."; |
281 "invalid."; |
282 } |
282 } |
283 cout << endl; |
283 cout << endl; |
284 ++bfs; |
284 ++bfs; |
285 } |
285 } |
293 cout << " \\ | --/ / | | / "<< endl; |
293 cout << " \\ | --/ / | | / "<< endl; |
294 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
294 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
295 cout << " \\--> -------------> "<< endl; |
295 cout << " \\--> -------------> "<< endl; |
296 |
296 |
297 cout << "dfs from t ..." << endl; |
297 cout << "dfs from t ..." << endl; |
298 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); |
298 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
299 dfs.pushAndSetReached(t); |
299 dfs.pushAndSetReached(t); |
300 while (!dfs.finished()) { |
300 while (!dfs.finished()) { |
301 ++dfs; |
301 ++dfs; |
302 //cout << "edge: "; |
302 //cout << "edge: "; |
303 if (wG.valid(GW::OutEdgeIt(dfs))) { |
303 if (gw.valid(GW::OutEdgeIt(dfs))) { |
304 cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << |
304 cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << |
305 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << |
305 node_name.get(gw.aNode(dfs)) << |
306 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
306 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
307 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << |
307 node_name.get(gw.bNode(dfs)) << |
308 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
308 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
309 ": is not newly reached."); |
309 ": is not newly reached."); |
310 } else { |
310 } else { |
311 cout << "invalid" << /*endl*/", " << |
311 cout << "invalid" << /*endl*/", " << |
312 /*" aNode: " <<*/ node_name.get(dfs.aNode()) << |
312 node_name.get(dfs.aNode()) << |
313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
314 /*" bNode: " <<*/ |
314 |
315 "invalid."; |
315 "invalid."; |
316 } |
316 } |
317 cout << endl; |
317 cout << endl; |
318 } |
318 } |
319 } |
319 } |