[174] | 1 | // -*- c++ -*- |
---|
[75] | 2 | #include <iostream> |
---|
| 3 | #include <vector> |
---|
| 4 | #include <string> |
---|
| 5 | |
---|
[174] | 6 | #include <list_graph.h> |
---|
| 7 | #include <smart_graph.h> |
---|
| 8 | #include <bfs_iterator.h> |
---|
[75] | 9 | #include <graph_wrapper.h> |
---|
| 10 | |
---|
[107] | 11 | using namespace hugo; |
---|
[158] | 12 | using std::cout; |
---|
| 13 | using std::endl; |
---|
| 14 | using std::string; |
---|
| 15 | |
---|
| 16 | template <typename Graph, typename NodeNameMap> |
---|
| 17 | class EdgeNameMap { |
---|
| 18 | Graph& graph; |
---|
| 19 | NodeNameMap& node_name_map; |
---|
| 20 | public: |
---|
| 21 | EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : |
---|
| 22 | graph(_graph), node_name_map(_node_name_map) { } |
---|
[174] | 23 | string get(typename Graph::Edge e) const { |
---|
[158] | 24 | return |
---|
| 25 | (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e))); |
---|
| 26 | } |
---|
| 27 | }; |
---|
[75] | 28 | |
---|
| 29 | int main (int, char*[]) |
---|
| 30 | { |
---|
[174] | 31 | //typedef SmartGraph Graph; |
---|
| 32 | typedef ListGraph Graph; |
---|
| 33 | |
---|
| 34 | typedef Graph::Node Node; |
---|
| 35 | typedef Graph::Edge Edge; |
---|
| 36 | //typedef Graph::NodeIt NodeIt; |
---|
| 37 | //typedef Graph::EdgeIt EdgeIt; |
---|
| 38 | //typedef Graph::OutEdgeIt OutEdgeIt; |
---|
| 39 | //typedef Graph::InEdgeIt InEdgeIt; |
---|
| 40 | //typedef Graph::SymEdgeIt SymEdgeIt; |
---|
[75] | 41 | |
---|
[174] | 42 | Graph G; |
---|
[75] | 43 | |
---|
[174] | 44 | Node s=G.addNode(); |
---|
| 45 | Node v1=G.addNode(); |
---|
| 46 | Node v2=G.addNode(); |
---|
| 47 | Node v3=G.addNode(); |
---|
| 48 | Node v4=G.addNode(); |
---|
| 49 | Node t=G.addNode(); |
---|
[75] | 50 | |
---|
[174] | 51 | Graph::NodeMap<string> node_name(G); |
---|
[158] | 52 | node_name.set(s, "s"); |
---|
| 53 | node_name.set(v1, "v1"); |
---|
| 54 | node_name.set(v2, "v2"); |
---|
| 55 | node_name.set(v3, "v3"); |
---|
| 56 | node_name.set(v4, "v4"); |
---|
| 57 | node_name.set(t, "t"); |
---|
| 58 | |
---|
[75] | 59 | G.addEdge(s, v1); |
---|
| 60 | G.addEdge(s, v2); |
---|
| 61 | G.addEdge(v1, v2); |
---|
| 62 | G.addEdge(v2, v1); |
---|
| 63 | G.addEdge(v1, v3); |
---|
| 64 | G.addEdge(v3, v2); |
---|
| 65 | G.addEdge(v2, v4); |
---|
| 66 | G.addEdge(v4, v3); |
---|
| 67 | G.addEdge(v3, t); |
---|
| 68 | G.addEdge(v4, t); |
---|
| 69 | |
---|
[158] | 70 | cout << " /--> -------------> "<< endl; |
---|
| 71 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
| 72 | cout << " / | | / /-> \\ "<< endl; |
---|
| 73 | cout << " / | | / | ^ \\ "<< endl; |
---|
| 74 | cout << "s | | / | | \\-> t "<< endl; |
---|
| 75 | cout << " \\ | | / | | /-> "<< endl; |
---|
| 76 | cout << " \\ | --/ / | | / "<< endl; |
---|
| 77 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
| 78 | cout << " \\--> -------------> "<< endl; |
---|
| 79 | |
---|
[174] | 80 | // typedef TrivGraphWrapper<const Graph> CGW; |
---|
[234] | 81 | // CGW gw(G); |
---|
[158] | 82 | |
---|
| 83 | // cout << "bfs and dfs demo on the directed graph" << endl; |
---|
[234] | 84 | // for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) { |
---|
[158] | 85 | // cout << n << ": "; |
---|
| 86 | // cout << "out edges: "; |
---|
[234] | 87 | // for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e) |
---|
[158] | 88 | // cout << e << " "; |
---|
| 89 | // cout << "in edges: "; |
---|
[234] | 90 | // for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e) |
---|
[158] | 91 | // cout << e << " "; |
---|
| 92 | // cout << endl; |
---|
| 93 | // } |
---|
| 94 | |
---|
| 95 | { |
---|
[174] | 96 | typedef TrivGraphWrapper<const Graph> GW; |
---|
[234] | 97 | GW gw(G); |
---|
[158] | 98 | |
---|
[234] | 99 | EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
---|
[158] | 100 | |
---|
| 101 | cout << "bfs and dfs iterator demo on the directed graph" << endl; |
---|
[265] | 102 | for(GW::NodeIt n=gw.first<GW::NodeIt>(); |
---|
| 103 | gw.valid(n); |
---|
| 104 | gw.next(n)) { |
---|
[158] | 105 | cout << node_name.get(n) << ": "; |
---|
| 106 | cout << "out edges: "; |
---|
[234] | 107 | for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 108 | cout << edge_name.get(e) << " "; |
---|
| 109 | cout << "in edges: "; |
---|
[234] | 110 | for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 111 | cout << edge_name.get(e) << " "; |
---|
| 112 | cout << endl; |
---|
| 113 | } |
---|
| 114 | |
---|
| 115 | cout << "bfs from s ..." << endl; |
---|
[234] | 116 | BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
---|
[75] | 117 | bfs.pushAndSetReached(s); |
---|
| 118 | while (!bfs.finished()) { |
---|
[158] | 119 | //cout << "edge: "; |
---|
[234] | 120 | if (gw.valid(bfs)) { |
---|
[158] | 121 | cout << edge_name.get(bfs) << /*endl*/", " << |
---|
[234] | 122 | node_name.get(gw.aNode(bfs)) << |
---|
[158] | 123 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 124 | node_name.get(gw.bNode(bfs)) << |
---|
[158] | 125 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 126 | ": is not newly reached."); |
---|
[75] | 127 | } else { |
---|
[158] | 128 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 129 | node_name.get(bfs.aNode()) << |
---|
[158] | 130 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 131 | |
---|
[158] | 132 | "invalid."; |
---|
[75] | 133 | } |
---|
[158] | 134 | cout << endl; |
---|
| 135 | ++bfs; |
---|
| 136 | } |
---|
| 137 | |
---|
| 138 | cout << " /--> -------------> "<< endl; |
---|
| 139 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
| 140 | cout << " / | | / /-> \\ "<< endl; |
---|
| 141 | cout << " / | | / | ^ \\ "<< endl; |
---|
| 142 | cout << "s | | / | | \\-> t "<< endl; |
---|
| 143 | cout << " \\ | | / | | /-> "<< endl; |
---|
| 144 | cout << " \\ | --/ / | | / "<< endl; |
---|
| 145 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
| 146 | cout << " \\--> -------------> "<< endl; |
---|
| 147 | |
---|
| 148 | cout << "dfs from s ..." << endl; |
---|
[234] | 149 | DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
---|
[158] | 150 | dfs.pushAndSetReached(s); |
---|
| 151 | while (!dfs.finished()) { |
---|
| 152 | ++dfs; |
---|
| 153 | //cout << "edge: "; |
---|
[234] | 154 | if (gw.valid(dfs)) { |
---|
[158] | 155 | cout << edge_name.get(dfs) << /*endl*/", " << |
---|
[234] | 156 | node_name.get(gw.aNode(dfs)) << |
---|
[158] | 157 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 158 | node_name.get(gw.bNode(dfs)) << |
---|
[158] | 159 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 160 | ": is not newly reached."); |
---|
[75] | 161 | } else { |
---|
[158] | 162 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 163 | node_name.get(dfs.aNode()) << |
---|
[158] | 164 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 165 | |
---|
[158] | 166 | "invalid."; |
---|
| 167 | } |
---|
| 168 | cout << endl; |
---|
| 169 | } |
---|
| 170 | } |
---|
| 171 | |
---|
| 172 | |
---|
| 173 | { |
---|
[234] | 174 | typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW; |
---|
| 175 | GW gw(G); |
---|
[158] | 176 | |
---|
[234] | 177 | EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
---|
[158] | 178 | |
---|
| 179 | cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; |
---|
[234] | 180 | for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { |
---|
[158] | 181 | cout << node_name.get(n) << ": "; |
---|
| 182 | cout << "out edges: "; |
---|
[234] | 183 | for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 184 | cout << edge_name.get(e) << " "; |
---|
| 185 | cout << "in edges: "; |
---|
[234] | 186 | for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 187 | cout << edge_name.get(e) << " "; |
---|
| 188 | cout << endl; |
---|
| 189 | } |
---|
| 190 | |
---|
| 191 | cout << "bfs from t ..." << endl; |
---|
[234] | 192 | BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
---|
[158] | 193 | bfs.pushAndSetReached(t); |
---|
| 194 | while (!bfs.finished()) { |
---|
| 195 | //cout << "edge: "; |
---|
[234] | 196 | if (gw.valid(bfs)) { |
---|
[158] | 197 | cout << edge_name.get(bfs) << /*endl*/", " << |
---|
[234] | 198 | node_name.get(gw.aNode(bfs)) << |
---|
[158] | 199 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 200 | node_name.get(gw.bNode(bfs)) << |
---|
[158] | 201 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 202 | ": is not newly reached."); |
---|
[75] | 203 | } else { |
---|
[158] | 204 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 205 | node_name.get(bfs.aNode()) << |
---|
[158] | 206 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 207 | |
---|
[158] | 208 | "invalid."; |
---|
| 209 | } |
---|
| 210 | cout << endl; |
---|
[75] | 211 | ++bfs; |
---|
| 212 | } |
---|
[158] | 213 | |
---|
| 214 | cout << " /--> -------------> "<< endl; |
---|
| 215 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
| 216 | cout << " / | | / /-> \\ "<< endl; |
---|
| 217 | cout << " / | | / | ^ \\ "<< endl; |
---|
| 218 | cout << "s | | / | | \\-> t "<< endl; |
---|
| 219 | cout << " \\ | | / | | /-> "<< endl; |
---|
| 220 | cout << " \\ | --/ / | | / "<< endl; |
---|
| 221 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
| 222 | cout << " \\--> -------------> "<< endl; |
---|
| 223 | |
---|
| 224 | cout << "dfs from t ..." << endl; |
---|
[234] | 225 | DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
---|
[158] | 226 | dfs.pushAndSetReached(t); |
---|
| 227 | while (!dfs.finished()) { |
---|
| 228 | ++dfs; |
---|
| 229 | //cout << "edge: "; |
---|
[234] | 230 | if (gw.valid(dfs)) { |
---|
[158] | 231 | cout << edge_name.get(dfs) << /*endl*/", " << |
---|
[234] | 232 | node_name.get(gw.aNode(dfs)) << |
---|
[158] | 233 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 234 | node_name.get(gw.bNode(dfs)) << |
---|
[158] | 235 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 236 | ": is not newly reached."); |
---|
| 237 | } else { |
---|
| 238 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 239 | node_name.get(dfs.aNode()) << |
---|
[158] | 240 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 241 | |
---|
[158] | 242 | "invalid."; |
---|
| 243 | } |
---|
| 244 | cout << endl; |
---|
| 245 | } |
---|
[75] | 246 | } |
---|
| 247 | |
---|
[99] | 248 | { |
---|
[236] | 249 | //typedef UndirGraphWrapper<const Graph> GW; |
---|
| 250 | typedef UndirGraphWrapper<const TrivGraphWrapper<const Graph> > GW; |
---|
[234] | 251 | GW gw(G); |
---|
[158] | 252 | |
---|
[234] | 253 | EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
---|
[158] | 254 | |
---|
| 255 | cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
---|
[234] | 256 | for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { |
---|
[158] | 257 | cout << node_name.get(n) << ": "; |
---|
| 258 | cout << "out edges: "; |
---|
[234] | 259 | for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 260 | cout << edge_name.get(e) << " "; |
---|
| 261 | cout << "in edges: "; |
---|
[234] | 262 | for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 263 | cout << edge_name.get(e) << " "; |
---|
| 264 | cout << endl; |
---|
| 265 | } |
---|
[238] | 266 | // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { |
---|
| 267 | // cout << edge_name.get(e) << " "; |
---|
| 268 | // } |
---|
| 269 | // cout << endl; |
---|
[158] | 270 | |
---|
| 271 | cout << "bfs from t ..." << endl; |
---|
[234] | 272 | BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
---|
[158] | 273 | bfs.pushAndSetReached(t); |
---|
| 274 | while (!bfs.finished()) { |
---|
| 275 | //cout << "edge: "; |
---|
[234] | 276 | if (gw.valid(GW::OutEdgeIt(bfs))) { |
---|
[158] | 277 | cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << |
---|
[234] | 278 | node_name.get(gw.aNode(bfs)) << |
---|
[158] | 279 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 280 | node_name.get(gw.bNode(bfs)) << |
---|
[158] | 281 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 282 | ": is not newly reached."); |
---|
| 283 | } else { |
---|
| 284 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 285 | node_name.get(bfs.aNode()) << |
---|
[158] | 286 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 287 | |
---|
[158] | 288 | "invalid."; |
---|
| 289 | } |
---|
| 290 | cout << endl; |
---|
| 291 | ++bfs; |
---|
| 292 | } |
---|
| 293 | |
---|
| 294 | cout << " /--> -------------> "<< endl; |
---|
| 295 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
| 296 | cout << " / | | / /-> \\ "<< endl; |
---|
| 297 | cout << " / | | / | ^ \\ "<< endl; |
---|
| 298 | cout << "s | | / | | \\-> t "<< endl; |
---|
| 299 | cout << " \\ | | / | | /-> "<< endl; |
---|
| 300 | cout << " \\ | --/ / | | / "<< endl; |
---|
| 301 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
| 302 | cout << " \\--> -------------> "<< endl; |
---|
| 303 | |
---|
| 304 | cout << "dfs from t ..." << endl; |
---|
[234] | 305 | DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
---|
[158] | 306 | dfs.pushAndSetReached(t); |
---|
[99] | 307 | while (!dfs.finished()) { |
---|
| 308 | ++dfs; |
---|
[158] | 309 | //cout << "edge: "; |
---|
[234] | 310 | if (gw.valid(GW::OutEdgeIt(dfs))) { |
---|
[158] | 311 | cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << |
---|
[234] | 312 | node_name.get(gw.aNode(dfs)) << |
---|
[158] | 313 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 314 | node_name.get(gw.bNode(dfs)) << |
---|
[158] | 315 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 316 | ": is not newly reached."); |
---|
[99] | 317 | } else { |
---|
[158] | 318 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 319 | node_name.get(dfs.aNode()) << |
---|
[158] | 320 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 321 | |
---|
[158] | 322 | "invalid."; |
---|
[99] | 323 | } |
---|
[158] | 324 | cout << endl; |
---|
[99] | 325 | } |
---|
| 326 | } |
---|
| 327 | |
---|
[75] | 328 | return 0; |
---|
| 329 | } |
---|