70 cout << " \\ | | / | | /-> "<< endl; |
71 cout << " \\ | | / | | /-> "<< endl; |
71 cout << " \\ | --/ / | | / "<< endl; |
72 cout << " \\ | --/ / | | / "<< endl; |
72 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
73 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
73 cout << " \\--> -------------> "<< endl; |
74 cout << " \\--> -------------> "<< endl; |
74 |
75 |
75 // typedef TrivGraphWrapper<const Graph> CGW; |
|
76 // CGW gw(G); |
|
77 |
|
78 // cout << "bfs and dfs demo on the directed graph" << endl; |
|
79 // for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) { |
|
80 // cout << n << ": "; |
|
81 // cout << "out edges: "; |
|
82 // for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e) |
|
83 // cout << e << " "; |
|
84 // cout << "in edges: "; |
|
85 // for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e) |
|
86 // cout << e << " "; |
|
87 // cout << endl; |
|
88 // } |
|
89 |
|
90 { |
76 { |
91 EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name); |
77 EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name); |
92 |
78 |
93 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
79 cout << "bfs and dfs iterator demo on the directed graph" << endl; |
94 for(Graph::NodeIt n(G); n!=INVALID; ++n) { |
80 for(Graph::NodeIt n(G); n!=INVALID; ++n) { |
105 cout << "bfs from s ..." << endl; |
91 cout << "bfs from s ..." << endl; |
106 BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G); |
92 BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G); |
107 bfs.pushAndSetReached(s); |
93 bfs.pushAndSetReached(s); |
108 while (!bfs.finished()) { |
94 while (!bfs.finished()) { |
109 //cout << "edge: "; |
95 //cout << "edge: "; |
110 if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) { |
96 if (Graph::Edge(bfs)!=INVALID) { |
111 cout << edge_name[bfs] << /*endl*/", " << |
97 cout << edge_name[bfs] << /*endl*/", " << |
112 node_name[G.tail(bfs)] << |
98 node_name[G.tail(bfs)] << |
113 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
99 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
114 node_name[G.head(bfs)] << |
100 node_name[G.head(bfs)] << |
115 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
101 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
116 ": is not newly reached."); |
102 ": is not newly reached."); |
117 } else { |
103 } else { |
118 cout << "invalid" << /*endl*/", " << |
104 cout << "invalid" << /*endl*/", " << |
119 node_name[bfs.aNode()] << |
105 node_name[bfs.tail()] << |
120 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
106 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
121 |
107 |
122 "invalid."; |
108 "invalid."; |
123 } |
109 } |
124 cout << endl; |
110 cout << endl; |
139 DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G); |
125 DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G); |
140 dfs.pushAndSetReached(s); |
126 dfs.pushAndSetReached(s); |
141 while (!dfs.finished()) { |
127 while (!dfs.finished()) { |
142 ++dfs; |
128 ++dfs; |
143 //cout << "edge: "; |
129 //cout << "edge: "; |
144 if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) { |
130 if (Graph::Edge(dfs)!=INVALID) { |
145 cout << edge_name[dfs] << /*endl*/", " << |
131 cout << edge_name[dfs] << /*endl*/", " << |
146 node_name[G.tail(dfs)] << |
132 node_name[G.tail(dfs)] << |
147 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
133 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
148 node_name[G.head(dfs)] << |
134 node_name[G.head(dfs)] << |
149 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
135 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
150 ": is not newly reached."); |
136 ": is not newly reached."); |
151 } else { |
137 } else { |
152 cout << "invalid" << /*endl*/", " << |
138 cout << "invalid" << /*endl*/", " << |
153 node_name[dfs.aNode()] << |
139 node_name[dfs.tail()] << |
154 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
140 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
155 |
141 |
156 "invalid."; |
142 "invalid."; |
157 } |
143 } |
158 cout << endl; |
144 cout << endl; |
181 cout << "bfs from t ..." << endl; |
167 cout << "bfs from t ..." << endl; |
182 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
168 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
183 bfs.pushAndSetReached(t); |
169 bfs.pushAndSetReached(t); |
184 while (!bfs.finished()) { |
170 while (!bfs.finished()) { |
185 //cout << "edge: "; |
171 //cout << "edge: "; |
186 if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) { |
172 if (GW::Edge(bfs)!=INVALID) { |
187 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << |
173 cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << |
188 node_name[gw.tail(bfs)] << |
174 node_name[gw.tail(bfs)] << |
189 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
175 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
190 node_name[gw.head(bfs)] << |
176 node_name[gw.head(bfs)] << |
191 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
177 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
192 ": is not newly reached."); |
178 ": is not newly reached."); |
193 } else { |
179 } else { |
194 cout << "invalid" << /*endl*/", " << |
180 cout << "invalid" << /*endl*/", " << |
195 node_name[bfs.aNode()] << |
181 node_name[bfs.tail()] << |
196 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
182 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
197 |
183 |
198 "invalid."; |
184 "invalid."; |
199 } |
185 } |
200 cout << endl; |
186 cout << endl; |
215 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
201 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
216 dfs.pushAndSetReached(t); |
202 dfs.pushAndSetReached(t); |
217 while (!dfs.finished()) { |
203 while (!dfs.finished()) { |
218 ++dfs; |
204 ++dfs; |
219 //cout << "edge: "; |
205 //cout << "edge: "; |
220 if (GW::OutEdgeIt(dfs)!=INVALID) { |
206 if (GW::Edge(dfs)!=INVALID) { |
221 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << |
207 cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << |
222 node_name[gw.tail(dfs)] << |
208 node_name[gw.tail(dfs)] << |
223 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
209 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
224 node_name[gw.head(dfs)] << |
210 node_name[gw.head(dfs)] << |
225 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
211 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
226 ": is not newly reached."); |
212 ": is not newly reached."); |
227 } else { |
213 } else { |
228 cout << "invalid" << /*endl*/", " << |
214 cout << "invalid" << /*endl*/", " << |
229 node_name[dfs.aNode()] << |
215 node_name[dfs.tail()] << |
230 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
216 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
231 |
217 |
232 "invalid."; |
218 "invalid."; |
233 } |
219 } |
234 cout << endl; |
220 cout << endl; |
344 cout << "bfs from t ..." << endl; |
330 cout << "bfs from t ..." << endl; |
345 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
331 BfsIterator< GW, GW::NodeMap<bool> > bfs(gw); |
346 bfs.pushAndSetReached(t); |
332 bfs.pushAndSetReached(t); |
347 while (!bfs.finished()) { |
333 while (!bfs.finished()) { |
348 //cout << "edge: "; |
334 //cout << "edge: "; |
349 if (GW::OutEdgeIt(bfs)!=INVALID) { |
335 if (GW::Edge(bfs)!=INVALID) { |
350 cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << |
336 cout << edge_name[GW::Edge(bfs)] << /*endl*/", " << |
351 node_name[gw.tail(bfs)] << |
337 node_name[gw.tail(bfs)] << |
352 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
338 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
353 node_name[gw.head(bfs)] << |
339 node_name[gw.head(bfs)] << |
354 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
340 (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
355 ": is not newly reached."); |
341 ": is not newly reached."); |
356 } else { |
342 } else { |
357 cout << "invalid" << /*endl*/", " << |
343 cout << "invalid" << /*endl*/", " << |
358 node_name[bfs.aNode()] << |
344 node_name[bfs.tail()] << |
359 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
345 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
360 |
346 |
361 "invalid."; |
347 "invalid."; |
362 } |
348 } |
363 cout << endl; |
349 cout << endl; |
378 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
364 DfsIterator< GW, GW::NodeMap<bool> > dfs(gw); |
379 dfs.pushAndSetReached(t); |
365 dfs.pushAndSetReached(t); |
380 while (!dfs.finished()) { |
366 while (!dfs.finished()) { |
381 ++dfs; |
367 ++dfs; |
382 //cout << "edge: "; |
368 //cout << "edge: "; |
383 if (GW::OutEdgeIt(dfs)!=INVALID) { |
369 if (GW::Edge(dfs)!=INVALID) { |
384 cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << |
370 cout << edge_name[GW::Edge(dfs)] << /*endl*/", " << |
385 node_name[gw.tail(dfs)] << |
371 node_name[gw.tail(dfs)] << |
386 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
372 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
387 node_name[gw.head(dfs)] << |
373 node_name[gw.head(dfs)] << |
388 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
374 (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
389 ": is not newly reached."); |
375 ": is not newly reached."); |
390 } else { |
376 } else { |
391 cout << "invalid" << /*endl*/", " << |
377 cout << "invalid" << /*endl*/", " << |
392 node_name[dfs.aNode()] << |
378 node_name[dfs.tail()] << |
393 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
379 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
394 |
380 |
395 "invalid."; |
381 "invalid."; |
396 } |
382 } |
397 cout << endl; |
383 cout << endl; |