[75] | 1 | #include <iostream> |
---|
| 2 | #include <vector> |
---|
| 3 | #include <string> |
---|
| 4 | |
---|
| 5 | #include <list_graph.hh> |
---|
| 6 | #include <bfs_iterator.hh> |
---|
| 7 | #include <graph_wrapper.h> |
---|
| 8 | |
---|
[107] | 9 | using namespace hugo; |
---|
[158] | 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 | }; |
---|
[75] | 26 | |
---|
| 27 | int main (int, char*[]) |
---|
| 28 | { |
---|
| 29 | typedef ListGraph::NodeIt NodeIt; |
---|
| 30 | typedef ListGraph::EdgeIt EdgeIt; |
---|
[158] | 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; |
---|
[75] | 36 | |
---|
| 37 | ListGraph G; |
---|
| 38 | |
---|
| 39 | NodeIt s=G.addNode(); |
---|
| 40 | NodeIt v1=G.addNode(); |
---|
| 41 | NodeIt v2=G.addNode(); |
---|
| 42 | NodeIt v3=G.addNode(); |
---|
| 43 | NodeIt v4=G.addNode(); |
---|
| 44 | NodeIt t=G.addNode(); |
---|
| 45 | |
---|
[158] | 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 | |
---|
[75] | 54 | G.addEdge(s, v1); |
---|
| 55 | G.addEdge(s, v2); |
---|
| 56 | G.addEdge(v1, v2); |
---|
| 57 | G.addEdge(v2, v1); |
---|
| 58 | G.addEdge(v1, v3); |
---|
| 59 | G.addEdge(v3, v2); |
---|
| 60 | G.addEdge(v2, v4); |
---|
| 61 | G.addEdge(v4, v3); |
---|
| 62 | G.addEdge(v3, t); |
---|
| 63 | G.addEdge(v4, t); |
---|
| 64 | |
---|
[158] | 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; |
---|
| 74 | |
---|
| 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" << " "; |
---|
[75] | 89 | } |
---|
[158] | 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 | |
---|
[75] | 105 | { |
---|
[158] | 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); |
---|
[75] | 171 | bfs.pushAndSetReached(s); |
---|
| 172 | while (!bfs.finished()) { |
---|
[158] | 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."); |
---|
[75] | 181 | } else { |
---|
[158] | 182 | cout << "invalid" << /*endl*/", " << |
---|
| 183 | /*" aNode: " <<*/ node_name.get(bfs.aNode()) << |
---|
| 184 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
| 185 | /*" bNode: " <<*/ |
---|
| 186 | "invalid."; |
---|
[75] | 187 | } |
---|
[158] | 188 | cout << endl; |
---|
| 189 | ++bfs; |
---|
| 190 | } |
---|
| 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); |
---|
| 204 | dfs.pushAndSetReached(s); |
---|
| 205 | while (!dfs.finished()) { |
---|
| 206 | ++dfs; |
---|
| 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."); |
---|
[75] | 215 | } else { |
---|
[158] | 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); |
---|
| 248 | while (!bfs.finished()) { |
---|
| 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."); |
---|
[75] | 257 | } else { |
---|
[158] | 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; |
---|
[75] | 265 | ++bfs; |
---|
| 266 | } |
---|
[158] | 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 | } |
---|
[75] | 300 | } |
---|
| 301 | |
---|
[99] | 302 | { |
---|
[158] | 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); |
---|
[99] | 356 | while (!dfs.finished()) { |
---|
| 357 | ++dfs; |
---|
[158] | 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."); |
---|
[99] | 366 | } else { |
---|
[158] | 367 | cout << "invalid" << /*endl*/", " << |
---|
| 368 | /*" aNode: " <<*/ node_name.get(dfs.aNode()) << |
---|
| 369 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
| 370 | /*" bNode: " <<*/ |
---|
| 371 | "invalid."; |
---|
[99] | 372 | } |
---|
[158] | 373 | cout << endl; |
---|
[99] | 374 | } |
---|
| 375 | } |
---|
| 376 | |
---|
[75] | 377 | return 0; |
---|
| 378 | } |
---|