Changeset 158:4f54d89fa9d2 in lemon-0.x for src/work/iterator_bfs_demo.cc
- Timestamp:
- 03/08/04 13:29:07 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@223
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/iterator_bfs_demo.cc
r107 r158 8 8 9 9 using namespace hugo; 10 using std::cout; 11 using std::endl; 12 using std::string; 13 14 template <typename Graph, typename NodeNameMap> 15 class EdgeNameMap { 16 Graph& graph; 17 NodeNameMap& node_name_map; 18 public: 19 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : 20 graph(_graph), node_name_map(_node_name_map) { } 21 string get(typename Graph::EdgeIt e) const { 22 return 23 (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); 24 } 25 }; 10 26 11 27 int main (int, char*[]) … … 13 29 typedef ListGraph::NodeIt NodeIt; 14 30 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;31 //typedef ListGraph::EachNodeIt EachNodeIt; 32 //typedef ListGraph::EachEdgeIt EachEdgeIt; 33 //typedef ListGraph::OutEdgeIt OutEdgeIt; 34 //typedef ListGraph::InEdgeIt InEdgeIt; 35 //typedef ListGraph::SymEdgeIt SymEdgeIt; 20 36 21 37 ListGraph G; … … 28 44 NodeIt t=G.addNode(); 29 45 46 ListGraph::NodeMap<string> node_name(G); 47 node_name.set(s, "s"); 48 node_name.set(v1, "v1"); 49 node_name.set(v2, "v2"); 50 node_name.set(v3, "v3"); 51 node_name.set(v4, "v4"); 52 node_name.set(t, "t"); 53 30 54 G.addEdge(s, v1); 31 55 G.addEdge(s, v2); … … 39 63 G.addEdge(v4, t); 40 64 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 } 65 cout << " /--> -------------> "<< endl; 66 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; 67 cout << " / | | / /-> \\ "<< endl; 68 cout << " / | | / | ^ \\ "<< endl; 69 cout << "s | | / | | \\-> t "<< endl; 70 cout << " \\ | | / | | /-> "<< endl; 71 cout << " \\ | --/ / | | / "<< endl; 72 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; 73 cout << " \\--> -------------> "<< endl; 52 74 53 { 54 std::cout << "iterator bfs demo 4 ..." << std::endl; 55 BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G); 75 /* 76 { 77 cout << "iterator bfs demo 4 ..." << endl; 78 BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G); 79 bfs.pushAndSetReached(s); 80 while (!bfs.finished()) { 81 if (OutEdgeIt(bfs).valid()) { 82 cout << "OutEdgeIt: " << bfs; 83 cout << " aNode: " << G.aNode(bfs); 84 cout << " bNode: " << G.bNode(bfs) << " "; 85 } else { 86 cout << "OutEdgeIt: " << "invalid"; 87 cout << " aNode: " << bfs.aNode(); 88 cout << " bNode: " << "invalid" << " "; 89 } 90 if (bfs.isBNodeNewlyReached()) { 91 cout << "bNodeIsNewlyReached "; 92 } else { 93 cout << "bNodeIsNotNewlyReached "; 94 } 95 if (bfs.isANodeExamined()) { 96 cout << "aNodeIsExamined "; 97 } else { 98 cout << "aNodeIsNotExamined "; 99 } 100 cout << endl; 101 ++bfs; 102 } 103 } 104 105 { 106 cout << "iterator dfs demo 4 ..." << endl; 107 DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G); 108 dfs.pushAndSetReached(s); 109 while (!dfs.finished()) { 110 ++dfs; 111 if (OutEdgeIt(dfs).valid()) { 112 cout << "OutEdgeIt: " << dfs; 113 cout << " aNode: " << G.aNode(dfs); 114 cout << " bNode: " << G.bNode(dfs) << " "; 115 } else { 116 cout << "OutEdgeIt: " << "invalid"; 117 cout << " aNode: " << dfs.aNode(); 118 cout << " bNode: " << "invalid" << " "; 119 } 120 if (dfs.isBNodeNewlyReached()) { 121 cout << "bNodeIsNewlyReached "; 122 } else { 123 cout << "bNodeIsNotNewlyReached "; 124 } 125 if (dfs.isANodeExamined()) { 126 cout << "aNodeIsExamined "; 127 } else { 128 cout << "aNodeIsNotExamined "; 129 } 130 cout << endl; 131 //++dfs; 132 } 133 } 134 */ 135 136 // typedef TrivGraphWrapper<const ListGraph> CGW; 137 // CGW wG(G); 138 139 // cout << "bfs and dfs demo on the directed graph" << endl; 140 // for(CGW::EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) { 141 // cout << n << ": "; 142 // cout << "out edges: "; 143 // for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e) 144 // cout << e << " "; 145 // cout << "in edges: "; 146 // for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e) 147 // cout << e << " "; 148 // cout << endl; 149 // } 150 151 { 152 typedef TrivGraphWrapper<const ListGraph> GW; 153 GW wG(G); 154 155 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name); 156 157 cout << "bfs and dfs iterator demo on the directed graph" << endl; 158 for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 159 cout << node_name.get(n) << ": "; 160 cout << "out edges: "; 161 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 162 cout << edge_name.get(e) << " "; 163 cout << "in edges: "; 164 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 165 cout << edge_name.get(e) << " "; 166 cout << endl; 167 } 168 169 cout << "bfs from s ..." << endl; 170 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); 56 171 bfs.pushAndSetReached(s); 57 172 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; 173 //cout << "edge: "; 174 if (wG.valid(bfs)) { 175 cout << edge_name.get(bfs) << /*endl*/", " << 176 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 177 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 178 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 179 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 180 ": is not newly reached."); 181 } else { 182 cout << "invalid" << /*endl*/", " << 183 /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 184 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 185 /*" bNode: " <<*/ 186 "invalid."; 187 } 188 cout << endl; 78 189 ++bfs; 79 190 } 80 } 81 82 { 83 std::cout << "iterator dfs demo 4 ..." << std::endl; 84 DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G); 191 192 cout << " /--> -------------> "<< endl; 193 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; 194 cout << " / | | / /-> \\ "<< endl; 195 cout << " / | | / | ^ \\ "<< endl; 196 cout << "s | | / | | \\-> t "<< endl; 197 cout << " \\ | | / | | /-> "<< endl; 198 cout << " \\ | --/ / | | / "<< endl; 199 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; 200 cout << " \\--> -------------> "<< endl; 201 202 cout << "dfs from s ..." << endl; 203 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); 85 204 dfs.pushAndSetReached(s); 86 205 while (!dfs.finished()) { 87 206 ++dfs; 88 if (OutEdgeIt(dfs).valid()) { 89 std::cout << "OutEdgeIt: " << dfs; 90 std::cout << " aNode: " << G.aNode(dfs); 91 std::cout << " bNode: " << G.bNode(dfs) << " "; 92 } else { 93 std::cout << "OutEdgeIt: " << "invalid"; 94 std::cout << " aNode: " << dfs.aNode(); 95 std::cout << " bNode: " << "invalid" << " "; 96 } 97 if (dfs.isBNodeNewlyReached()) { 98 std::cout << "bNodeIsNewlyReached "; 99 } else { 100 std::cout << "bNodeIsNotNewlyReached "; 101 } 102 if (dfs.isANodeExamined()) { 103 std::cout << "aNodeIsExamined "; 104 } else { 105 std::cout << "aNodeIsNotExamined "; 106 } 107 std::cout<<std::endl; 108 //++dfs; 109 } 110 } 111 112 113 typedef ConstTrivGraphWrapper<ListGraph> CTGW; 114 CTGW wG(G); 115 116 std::cout << "bfs and dfs demo on the directed graph" << std::endl; 117 for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) { 118 std::cout << i << ": "; 119 std::cout << "out edges: "; 120 for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j) 121 std::cout << j << " "; 122 std::cout << "in edges: "; 123 for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j) 124 std::cout << j << " "; 125 std::cout << std::endl; 126 } 127 128 129 { 130 std::cout << "iterator bfs demo 5 ..." << std::endl; 131 BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG); 132 bfs.pushAndSetReached(s); 207 //cout << "edge: "; 208 if (wG.valid(dfs)) { 209 cout << edge_name.get(dfs) << /*endl*/", " << 210 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 211 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 212 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 213 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 214 ": is not newly reached."); 215 } else { 216 cout << "invalid" << /*endl*/", " << 217 /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 218 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 219 /*" bNode: " <<*/ 220 "invalid."; 221 } 222 cout << endl; 223 } 224 } 225 226 227 { 228 typedef RevGraphWrapper<const ListGraph> GW; 229 GW wG(G); 230 231 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name); 232 233 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; 234 for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 235 cout << node_name.get(n) << ": "; 236 cout << "out edges: "; 237 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 238 cout << edge_name.get(e) << " "; 239 cout << "in edges: "; 240 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 241 cout << edge_name.get(e) << " "; 242 cout << endl; 243 } 244 245 cout << "bfs from t ..." << endl; 246 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); 247 bfs.pushAndSetReached(t); 133 248 while (!bfs.finished()) { 134 if (OutEdgeIt(bfs).valid()) { 135 std::cout << "OutEdgeIt: " << bfs; 136 std::cout << " aNode: " << wG.aNode(bfs); 137 std::cout << " bNode: " << wG.bNode(bfs) << " "; 138 } else { 139 std::cout << "OutEdgeIt: " << "invalid"; 140 std::cout << " aNode: " << bfs.aNode(); 141 std::cout << " bNode: " << "invalid" << " "; 142 } 143 if (bfs.isBNodeNewlyReached()) { 144 std::cout << "bNodeIsNewlyReached "; 145 } else { 146 std::cout << "bNodeIsNotNewlyReached "; 147 } 148 if (bfs.isANodeExamined()) { 149 std::cout << "aNodeIsExamined "; 150 } else { 151 std::cout << "aNodeIsNotExamined "; 152 } 153 std::cout<<std::endl; 249 //cout << "edge: "; 250 if (wG.valid(bfs)) { 251 cout << edge_name.get(bfs) << /*endl*/", " << 252 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 253 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 254 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 255 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 256 ": is not newly reached."); 257 } else { 258 cout << "invalid" << /*endl*/", " << 259 /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 260 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 261 /*" bNode: " <<*/ 262 "invalid."; 263 } 264 cout << endl; 154 265 ++bfs; 155 266 } 156 } 157 267 268 cout << " /--> -------------> "<< endl; 269 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; 270 cout << " / | | / /-> \\ "<< endl; 271 cout << " / | | / | ^ \\ "<< endl; 272 cout << "s | | / | | \\-> t "<< endl; 273 cout << " \\ | | / | | /-> "<< endl; 274 cout << " \\ | --/ / | | / "<< endl; 275 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; 276 cout << " \\--> -------------> "<< endl; 277 278 cout << "dfs from t ..." << endl; 279 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); 280 dfs.pushAndSetReached(t); 281 while (!dfs.finished()) { 282 ++dfs; 283 //cout << "edge: "; 284 if (wG.valid(dfs)) { 285 cout << edge_name.get(dfs) << /*endl*/", " << 286 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 287 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 288 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 289 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 290 ": is not newly reached."); 291 } else { 292 cout << "invalid" << /*endl*/", " << 293 /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 294 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 295 /*" bNode: " <<*/ 296 "invalid."; 297 } 298 cout << endl; 299 } 300 } 301 302 { 303 typedef UndirGraphWrapper<const ListGraph> GW; 304 GW wG(G); 305 306 EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name); 307 308 cout << "bfs and dfs iterator demo on the undirected graph" << endl; 309 for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 310 cout << node_name.get(n) << ": "; 311 cout << "out edges: "; 312 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 313 cout << edge_name.get(e) << " "; 314 cout << "in edges: "; 315 for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e)) 316 cout << edge_name.get(e) << " "; 317 cout << endl; 318 } 319 320 cout << "bfs from t ..." << endl; 321 BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG); 322 bfs.pushAndSetReached(t); 323 while (!bfs.finished()) { 324 //cout << "edge: "; 325 if (wG.valid(GW::OutEdgeIt(bfs))) { 326 cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << 327 /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) << 328 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 329 /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) << 330 (bfs.isBNodeNewlyReached() ? ": is newly reached." : 331 ": is not newly reached."); 332 } else { 333 cout << "invalid" << /*endl*/", " << 334 /*" aNode: " <<*/ node_name.get(bfs.aNode()) << 335 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 336 /*" bNode: " <<*/ 337 "invalid."; 338 } 339 cout << endl; 340 ++bfs; 341 } 342 343 cout << " /--> -------------> "<< endl; 344 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; 345 cout << " / | | / /-> \\ "<< endl; 346 cout << " / | | / | ^ \\ "<< endl; 347 cout << "s | | / | | \\-> t "<< endl; 348 cout << " \\ | | / | | /-> "<< endl; 349 cout << " \\ | --/ / | | / "<< endl; 350 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; 351 cout << " \\--> -------------> "<< endl; 352 353 cout << "dfs from t ..." << endl; 354 DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG); 355 dfs.pushAndSetReached(t); 356 while (!dfs.finished()) { 357 ++dfs; 358 //cout << "edge: "; 359 if (wG.valid(GW::OutEdgeIt(dfs))) { 360 cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << 361 /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) << 362 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 363 /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) << 364 (dfs.isBNodeNewlyReached() ? ": is newly reached." : 365 ": is not newly reached."); 366 } else { 367 cout << "invalid" << /*endl*/", " << 368 /*" aNode: " <<*/ node_name.get(dfs.aNode()) << 369 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 370 /*" bNode: " <<*/ 371 "invalid."; 372 } 373 cout << endl; 374 } 375 } 158 376 159 377 return 0;
Note: See TracChangeset
for help on using the changeset viewer.