Changeset 234:348f8fd374ee in lemon0.x for src/work/iterator_bfs_demo.cc
 Timestamp:
 03/22/04 17:37:10 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@331
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/iterator_bfs_demo.cc
r174 r234 79 79 80 80 // typedef TrivGraphWrapper<const Graph> CGW; 81 // CGW wG(G);81 // CGW gw(G); 82 82 83 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 85 // cout << n << ": "; 86 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 88 // cout << e << " "; 89 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 91 // cout << e << " "; 92 92 // cout << endl; … … 95 95 { 96 96 typedef TrivGraphWrapper<const Graph> GW; 97 GW wG(G);98 99 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name( wG, node_name);97 GW gw(G); 98 99 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); 100 100 101 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 103 cout << node_name.get(n) << ": "; 104 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 106 cout << edge_name.get(e) << " "; 107 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 109 cout << edge_name.get(e) << " "; 110 110 cout << endl; … … 112 112 113 113 cout << "bfs from s ..." << endl; 114 BfsIterator5< GW, GW::NodeMap<bool> > bfs( wG);114 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); 115 115 bfs.pushAndSetReached(s); 116 116 while (!bfs.finished()) { 117 117 //cout << "edge: "; 118 if ( wG.valid(bfs)) {118 if (gw.valid(bfs)) { 119 119 cout << edge_name.get(bfs) << /*endl*/", " << 120 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<121 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 122 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<120 node_name.get(gw.aNode(bfs)) << 121 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 122 node_name.get(gw.bNode(bfs)) << 123 123 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 124 124 ": is not newly reached."); 125 125 } else { 126 126 cout << "invalid" << /*endl*/", " << 127 /*" aNode: " <<*/node_name.get(bfs.aNode()) <<128 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 129 /*" bNode: " <<*/127 node_name.get(bfs.aNode()) << 128 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 129 130 130 "invalid."; 131 131 } … … 145 145 146 146 cout << "dfs from s ..." << endl; 147 DfsIterator5< GW, GW::NodeMap<bool> > dfs( wG);147 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); 148 148 dfs.pushAndSetReached(s); 149 149 while (!dfs.finished()) { 150 150 ++dfs; 151 151 //cout << "edge: "; 152 if ( wG.valid(dfs)) {152 if (gw.valid(dfs)) { 153 153 cout << edge_name.get(dfs) << /*endl*/", " << 154 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<155 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 156 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<154 node_name.get(gw.aNode(dfs)) << 155 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 156 node_name.get(gw.bNode(dfs)) << 157 157 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 158 158 ": is not newly reached."); 159 159 } else { 160 160 cout << "invalid" << /*endl*/", " << 161 /*" aNode: " <<*/node_name.get(dfs.aNode()) <<162 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 163 /*" bNode: " <<*/161 node_name.get(dfs.aNode()) << 162 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 163 164 164 "invalid."; 165 165 } … … 170 170 171 171 { 172 typedef RevGraphWrapper<const Graph> GW;173 GW wG(G);174 175 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name( wG, node_name);172 typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW; 173 GW gw(G); 174 175 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); 176 176 177 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 179 cout << node_name.get(n) << ": "; 180 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 182 cout << edge_name.get(e) << " "; 183 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 185 cout << edge_name.get(e) << " "; 186 186 cout << endl; … … 188 188 189 189 cout << "bfs from t ..." << endl; 190 BfsIterator5< GW, GW::NodeMap<bool> > bfs( wG);190 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); 191 191 bfs.pushAndSetReached(t); 192 192 while (!bfs.finished()) { 193 193 //cout << "edge: "; 194 if ( wG.valid(bfs)) {194 if (gw.valid(bfs)) { 195 195 cout << edge_name.get(bfs) << /*endl*/", " << 196 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<197 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 198 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<196 node_name.get(gw.aNode(bfs)) << 197 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 198 node_name.get(gw.bNode(bfs)) << 199 199 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 200 200 ": is not newly reached."); 201 201 } else { 202 202 cout << "invalid" << /*endl*/", " << 203 /*" aNode: " <<*/node_name.get(bfs.aNode()) <<204 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 205 /*" bNode: " <<*/203 node_name.get(bfs.aNode()) << 204 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 205 206 206 "invalid."; 207 207 } … … 221 221 222 222 cout << "dfs from t ..." << endl; 223 DfsIterator5< GW, GW::NodeMap<bool> > dfs( wG);223 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); 224 224 dfs.pushAndSetReached(t); 225 225 while (!dfs.finished()) { 226 226 ++dfs; 227 227 //cout << "edge: "; 228 if ( wG.valid(dfs)) {228 if (gw.valid(dfs)) { 229 229 cout << edge_name.get(dfs) << /*endl*/", " << 230 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<231 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 232 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<230 node_name.get(gw.aNode(dfs)) << 231 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 232 node_name.get(gw.bNode(dfs)) << 233 233 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 234 234 ": is not newly reached."); 235 235 } else { 236 236 cout << "invalid" << /*endl*/", " << 237 /*" aNode: " <<*/node_name.get(dfs.aNode()) <<238 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 239 /*" bNode: " <<*/237 node_name.get(dfs.aNode()) << 238 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 239 240 240 "invalid."; 241 241 } … … 246 246 { 247 247 typedef UndirGraphWrapper<const Graph> GW; 248 GW wG(G);249 250 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name( wG, node_name);248 GW gw(G); 249 250 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); 251 251 252 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 254 cout << node_name.get(n) << ": "; 255 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 257 cout << edge_name.get(e) << " "; 258 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 260 cout << edge_name.get(e) << " "; 261 261 cout << endl; … … 263 263 264 264 cout << "bfs from t ..." << endl; 265 BfsIterator5< GW, GW::NodeMap<bool> > bfs( wG);265 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); 266 266 bfs.pushAndSetReached(t); 267 267 while (!bfs.finished()) { 268 268 //cout << "edge: "; 269 if ( wG.valid(GW::OutEdgeIt(bfs))) {269 if (gw.valid(GW::OutEdgeIt(bfs))) { 270 270 cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << 271 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<272 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 273 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<271 node_name.get(gw.aNode(bfs)) << 272 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 273 node_name.get(gw.bNode(bfs)) << 274 274 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 275 275 ": is not newly reached."); 276 276 } else { 277 277 cout << "invalid" << /*endl*/", " << 278 /*" aNode: " <<*/node_name.get(bfs.aNode()) <<279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 280 /*" bNode: " <<*/278 node_name.get(bfs.aNode()) << 279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 280 281 281 "invalid."; 282 282 } … … 296 296 297 297 cout << "dfs from t ..." << endl; 298 DfsIterator5< GW, GW::NodeMap<bool> > dfs( wG);298 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); 299 299 dfs.pushAndSetReached(t); 300 300 while (!dfs.finished()) { 301 301 ++dfs; 302 302 //cout << "edge: "; 303 if ( wG.valid(GW::OutEdgeIt(dfs))) {303 if (gw.valid(GW::OutEdgeIt(dfs))) { 304 304 cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << 305 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<306 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 307 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<305 node_name.get(gw.aNode(dfs)) << 306 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 307 node_name.get(gw.bNode(dfs)) << 308 308 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 309 309 ": is not newly reached."); 310 310 } else { 311 311 cout << "invalid" << /*endl*/", " << 312 /*" aNode: " <<*/node_name.get(dfs.aNode()) <<313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 314 /*" bNode: " <<*/312 node_name.get(dfs.aNode()) << 313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 314 315 315 "invalid."; 316 316 }
Note: See TracChangeset
for help on using the changeset viewer.