[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; |
---|
[234] | 102 | for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { |
---|
[158] | 103 | cout << node_name.get(n) << ": "; |
---|
| 104 | cout << "out edges: "; |
---|
[234] | 105 | for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 106 | cout << edge_name.get(e) << " "; |
---|
| 107 | cout << "in edges: "; |
---|
[234] | 108 | for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 109 | cout << edge_name.get(e) << " "; |
---|
| 110 | cout << endl; |
---|
| 111 | } |
---|
| 112 | |
---|
| 113 | cout << "bfs from s ..." << endl; |
---|
[234] | 114 | BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
---|
[75] | 115 | bfs.pushAndSetReached(s); |
---|
| 116 | while (!bfs.finished()) { |
---|
[158] | 117 | //cout << "edge: "; |
---|
[234] | 118 | if (gw.valid(bfs)) { |
---|
[158] | 119 | cout << edge_name.get(bfs) << /*endl*/", " << |
---|
[234] | 120 | node_name.get(gw.aNode(bfs)) << |
---|
[158] | 121 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 122 | node_name.get(gw.bNode(bfs)) << |
---|
[158] | 123 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 124 | ": is not newly reached."); |
---|
[75] | 125 | } else { |
---|
[158] | 126 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 127 | node_name.get(bfs.aNode()) << |
---|
[158] | 128 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 129 | |
---|
[158] | 130 | "invalid."; |
---|
[75] | 131 | } |
---|
[158] | 132 | cout << endl; |
---|
| 133 | ++bfs; |
---|
| 134 | } |
---|
| 135 | |
---|
| 136 | cout << " /--> -------------> "<< endl; |
---|
| 137 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
| 138 | cout << " / | | / /-> \\ "<< endl; |
---|
| 139 | cout << " / | | / | ^ \\ "<< endl; |
---|
| 140 | cout << "s | | / | | \\-> t "<< endl; |
---|
| 141 | cout << " \\ | | / | | /-> "<< endl; |
---|
| 142 | cout << " \\ | --/ / | | / "<< endl; |
---|
| 143 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
| 144 | cout << " \\--> -------------> "<< endl; |
---|
| 145 | |
---|
| 146 | cout << "dfs from s ..." << endl; |
---|
[234] | 147 | DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
---|
[158] | 148 | dfs.pushAndSetReached(s); |
---|
| 149 | while (!dfs.finished()) { |
---|
| 150 | ++dfs; |
---|
| 151 | //cout << "edge: "; |
---|
[234] | 152 | if (gw.valid(dfs)) { |
---|
[158] | 153 | cout << edge_name.get(dfs) << /*endl*/", " << |
---|
[234] | 154 | node_name.get(gw.aNode(dfs)) << |
---|
[158] | 155 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 156 | node_name.get(gw.bNode(dfs)) << |
---|
[158] | 157 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 158 | ": is not newly reached."); |
---|
[75] | 159 | } else { |
---|
[158] | 160 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 161 | node_name.get(dfs.aNode()) << |
---|
[158] | 162 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 163 | |
---|
[158] | 164 | "invalid."; |
---|
| 165 | } |
---|
| 166 | cout << endl; |
---|
| 167 | } |
---|
| 168 | } |
---|
| 169 | |
---|
| 170 | |
---|
| 171 | { |
---|
[234] | 172 | typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW; |
---|
| 173 | GW gw(G); |
---|
[158] | 174 | |
---|
[234] | 175 | EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
---|
[158] | 176 | |
---|
| 177 | cout << "bfs and dfs iterator demo on the reversed directed graph" << endl; |
---|
[234] | 178 | for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { |
---|
[158] | 179 | cout << node_name.get(n) << ": "; |
---|
| 180 | cout << "out edges: "; |
---|
[234] | 181 | for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 182 | cout << edge_name.get(e) << " "; |
---|
| 183 | cout << "in edges: "; |
---|
[234] | 184 | for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 185 | cout << edge_name.get(e) << " "; |
---|
| 186 | cout << endl; |
---|
| 187 | } |
---|
| 188 | |
---|
| 189 | cout << "bfs from t ..." << endl; |
---|
[234] | 190 | BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
---|
[158] | 191 | bfs.pushAndSetReached(t); |
---|
| 192 | while (!bfs.finished()) { |
---|
| 193 | //cout << "edge: "; |
---|
[234] | 194 | if (gw.valid(bfs)) { |
---|
[158] | 195 | cout << edge_name.get(bfs) << /*endl*/", " << |
---|
[234] | 196 | node_name.get(gw.aNode(bfs)) << |
---|
[158] | 197 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 198 | node_name.get(gw.bNode(bfs)) << |
---|
[158] | 199 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 200 | ": is not newly reached."); |
---|
[75] | 201 | } else { |
---|
[158] | 202 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 203 | node_name.get(bfs.aNode()) << |
---|
[158] | 204 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 205 | |
---|
[158] | 206 | "invalid."; |
---|
| 207 | } |
---|
| 208 | cout << endl; |
---|
[75] | 209 | ++bfs; |
---|
| 210 | } |
---|
[158] | 211 | |
---|
| 212 | cout << " /--> -------------> "<< endl; |
---|
| 213 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
| 214 | cout << " / | | / /-> \\ "<< endl; |
---|
| 215 | cout << " / | | / | ^ \\ "<< endl; |
---|
| 216 | cout << "s | | / | | \\-> t "<< endl; |
---|
| 217 | cout << " \\ | | / | | /-> "<< endl; |
---|
| 218 | cout << " \\ | --/ / | | / "<< endl; |
---|
| 219 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
| 220 | cout << " \\--> -------------> "<< endl; |
---|
| 221 | |
---|
| 222 | cout << "dfs from t ..." << endl; |
---|
[234] | 223 | DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
---|
[158] | 224 | dfs.pushAndSetReached(t); |
---|
| 225 | while (!dfs.finished()) { |
---|
| 226 | ++dfs; |
---|
| 227 | //cout << "edge: "; |
---|
[234] | 228 | if (gw.valid(dfs)) { |
---|
[158] | 229 | cout << edge_name.get(dfs) << /*endl*/", " << |
---|
[234] | 230 | node_name.get(gw.aNode(dfs)) << |
---|
[158] | 231 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 232 | node_name.get(gw.bNode(dfs)) << |
---|
[158] | 233 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 234 | ": is not newly reached."); |
---|
| 235 | } else { |
---|
| 236 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 237 | node_name.get(dfs.aNode()) << |
---|
[158] | 238 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 239 | |
---|
[158] | 240 | "invalid."; |
---|
| 241 | } |
---|
| 242 | cout << endl; |
---|
| 243 | } |
---|
[75] | 244 | } |
---|
| 245 | |
---|
[99] | 246 | { |
---|
[236] | 247 | //typedef UndirGraphWrapper<const Graph> GW; |
---|
| 248 | typedef UndirGraphWrapper<const TrivGraphWrapper<const Graph> > GW; |
---|
[234] | 249 | GW gw(G); |
---|
[158] | 250 | |
---|
[234] | 251 | EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name); |
---|
[158] | 252 | |
---|
| 253 | cout << "bfs and dfs iterator demo on the undirected graph" << endl; |
---|
[234] | 254 | for(GW::NodeIt n=gw.first<GW::NodeIt>(); gw.valid(n); gw.next(n)) { |
---|
[158] | 255 | cout << node_name.get(n) << ": "; |
---|
| 256 | cout << "out edges: "; |
---|
[234] | 257 | for(GW::OutEdgeIt e=gw.first<GW::OutEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 258 | cout << edge_name.get(e) << " "; |
---|
| 259 | cout << "in edges: "; |
---|
[234] | 260 | for(GW::InEdgeIt e=gw.first<GW::InEdgeIt>(n); gw.valid(e); gw.next(e)) |
---|
[158] | 261 | cout << edge_name.get(e) << " "; |
---|
| 262 | cout << endl; |
---|
| 263 | } |
---|
[238] | 264 | // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { |
---|
| 265 | // cout << edge_name.get(e) << " "; |
---|
| 266 | // } |
---|
| 267 | // cout << endl; |
---|
[158] | 268 | |
---|
| 269 | cout << "bfs from t ..." << endl; |
---|
[234] | 270 | BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw); |
---|
[158] | 271 | bfs.pushAndSetReached(t); |
---|
| 272 | while (!bfs.finished()) { |
---|
| 273 | //cout << "edge: "; |
---|
[234] | 274 | if (gw.valid(GW::OutEdgeIt(bfs))) { |
---|
[158] | 275 | cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " << |
---|
[234] | 276 | node_name.get(gw.aNode(bfs)) << |
---|
[158] | 277 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 278 | node_name.get(gw.bNode(bfs)) << |
---|
[158] | 279 | (bfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 280 | ": is not newly reached."); |
---|
| 281 | } else { |
---|
| 282 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 283 | node_name.get(bfs.aNode()) << |
---|
[158] | 284 | (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 285 | |
---|
[158] | 286 | "invalid."; |
---|
| 287 | } |
---|
| 288 | cout << endl; |
---|
| 289 | ++bfs; |
---|
| 290 | } |
---|
| 291 | |
---|
| 292 | cout << " /--> -------------> "<< endl; |
---|
| 293 | cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl; |
---|
| 294 | cout << " / | | / /-> \\ "<< endl; |
---|
| 295 | cout << " / | | / | ^ \\ "<< endl; |
---|
| 296 | cout << "s | | / | | \\-> t "<< endl; |
---|
| 297 | cout << " \\ | | / | | /-> "<< endl; |
---|
| 298 | cout << " \\ | --/ / | | / "<< endl; |
---|
| 299 | cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl; |
---|
| 300 | cout << " \\--> -------------> "<< endl; |
---|
| 301 | |
---|
| 302 | cout << "dfs from t ..." << endl; |
---|
[234] | 303 | DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw); |
---|
[158] | 304 | dfs.pushAndSetReached(t); |
---|
[99] | 305 | while (!dfs.finished()) { |
---|
| 306 | ++dfs; |
---|
[158] | 307 | //cout << "edge: "; |
---|
[234] | 308 | if (gw.valid(GW::OutEdgeIt(dfs))) { |
---|
[158] | 309 | cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " << |
---|
[234] | 310 | node_name.get(gw.aNode(dfs)) << |
---|
[158] | 311 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 312 | node_name.get(gw.bNode(dfs)) << |
---|
[158] | 313 | (dfs.isBNodeNewlyReached() ? ": is newly reached." : |
---|
| 314 | ": is not newly reached."); |
---|
[99] | 315 | } else { |
---|
[158] | 316 | cout << "invalid" << /*endl*/", " << |
---|
[234] | 317 | node_name.get(dfs.aNode()) << |
---|
[158] | 318 | (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << |
---|
[234] | 319 | |
---|
[158] | 320 | "invalid."; |
---|
[99] | 321 | } |
---|
[158] | 322 | cout << endl; |
---|
[99] | 323 | } |
---|
| 324 | } |
---|
| 325 | |
---|
[75] | 326 | return 0; |
---|
| 327 | } |
---|