1.1 --- a/src/work/marci/iterator_bfs_demo.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,388 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#include <iostream>
1.6 -#include <vector>
1.7 -#include <string>
1.8 -
1.9 -#include <sage_graph.h>
1.10 -#include <lemon/smart_graph.h>
1.11 -#include <bfs_dfs.h>
1.12 -#include <lemon/graph_wrapper.h>
1.13 -
1.14 -using namespace lemon;
1.15 -
1.16 -using std::cout;
1.17 -using std::endl;
1.18 -using std::string;
1.19 -
1.20 -template <typename Graph, typename NodeNameMap>
1.21 -class EdgeNameMap {
1.22 - Graph& graph;
1.23 - NodeNameMap& node_name_map;
1.24 -public:
1.25 - EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
1.26 - graph(_graph), node_name_map(_node_name_map) { }
1.27 - string operator[](typename Graph::Edge e) const {
1.28 - return
1.29 - (node_name_map[graph.source(e)]+"->"+node_name_map[graph.target(e)]);
1.30 - }
1.31 -};
1.32 -
1.33 -int main (int, char*[])
1.34 -{
1.35 - typedef SmartGraph Graph;
1.36 - //typedef SageGraph Graph;
1.37 -
1.38 - typedef Graph::Node Node;
1.39 - typedef Graph::Edge Edge;
1.40 -
1.41 - Graph G;
1.42 -
1.43 - Node s=G.addNode();
1.44 - Node v1=G.addNode();
1.45 - Node v2=G.addNode();
1.46 - Node v3=G.addNode();
1.47 - Node v4=G.addNode();
1.48 - Node t=G.addNode();
1.49 -
1.50 - Graph::NodeMap<string> node_name(G);
1.51 - node_name.set(s, "s");
1.52 - node_name.set(v1, "v1");
1.53 - node_name.set(v2, "v2");
1.54 - node_name.set(v3, "v3");
1.55 - node_name.set(v4, "v4");
1.56 - node_name.set(t, "t");
1.57 -
1.58 - G.addEdge(s, v1);
1.59 - G.addEdge(s, v2);
1.60 - G.addEdge(v1, v2);
1.61 - G.addEdge(v2, v1);
1.62 - G.addEdge(v1, v3);
1.63 - G.addEdge(v3, v2);
1.64 - G.addEdge(v2, v4);
1.65 - G.addEdge(v4, v3);
1.66 - G.addEdge(v3, t);
1.67 - G.addEdge(v4, t);
1.68 -
1.69 - cout << " /--> -------------> "<< endl;
1.70 - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
1.71 - cout << " / | | / /-> \\ "<< endl;
1.72 - cout << " / | | / | ^ \\ "<< endl;
1.73 - cout << "s | | / | | \\-> t "<< endl;
1.74 - cout << " \\ | | / | | /-> "<< endl;
1.75 - cout << " \\ | --/ / | | / "<< endl;
1.76 - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
1.77 - cout << " \\--> -------------> "<< endl;
1.78 -
1.79 - {
1.80 - EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);
1.81 -
1.82 - cout << "bfs and dfs iterator demo on the directed graph" << endl;
1.83 - for(Graph::NodeIt n(G); n!=INVALID; ++n) {
1.84 - cout << node_name[n] << ": ";
1.85 - cout << "out edges: ";
1.86 - for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e)
1.87 - cout << edge_name[e] << " ";
1.88 - cout << "in edges: ";
1.89 - for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e)
1.90 - cout << edge_name[e] << " ";
1.91 - cout << endl;
1.92 - }
1.93 -
1.94 - cout << "bfs from s ..." << endl;
1.95 - BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
1.96 - bfs.pushAndSetReached(s);
1.97 - while (!bfs.finished()) {
1.98 - //cout << "edge: ";
1.99 - if (Graph::Edge(bfs)!=INVALID) {
1.100 - cout << edge_name[bfs] << /*endl*/", " <<
1.101 - node_name[G.source(bfs)] <<
1.102 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.103 - node_name[G.target(bfs)] <<
1.104 - (bfs.isBNodeNewlyReached() ? ": is newly reached." :
1.105 - ": is not newly reached.");
1.106 - } else {
1.107 - cout << "invalid" << /*endl*/", " <<
1.108 - node_name[bfs.source()] <<
1.109 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.110 -
1.111 - "invalid.";
1.112 - }
1.113 - cout << endl;
1.114 - ++bfs;
1.115 - }
1.116 -
1.117 - cout << " /--> -------------> "<< endl;
1.118 - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
1.119 - cout << " / | | / /-> \\ "<< endl;
1.120 - cout << " / | | / | ^ \\ "<< endl;
1.121 - cout << "s | | / | | \\-> t "<< endl;
1.122 - cout << " \\ | | / | | /-> "<< endl;
1.123 - cout << " \\ | --/ / | | / "<< endl;
1.124 - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
1.125 - cout << " \\--> -------------> "<< endl;
1.126 -
1.127 - cout << "dfs from s ..." << endl;
1.128 - DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);
1.129 - dfs.pushAndSetReached(s);
1.130 - while (!dfs.finished()) {
1.131 - ++dfs;
1.132 - //cout << "edge: ";
1.133 - if (Graph::Edge(dfs)!=INVALID) {
1.134 - cout << edge_name[dfs] << /*endl*/", " <<
1.135 - node_name[G.source(dfs)] <<
1.136 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.137 - node_name[G.target(dfs)] <<
1.138 - (dfs.isBNodeNewlyReached() ? ": is newly reached." :
1.139 - ": is not newly reached.");
1.140 - } else {
1.141 - cout << "invalid" << /*endl*/", " <<
1.142 - node_name[dfs.source()] <<
1.143 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.144 -
1.145 - "invalid.";
1.146 - }
1.147 - cout << endl;
1.148 - }
1.149 - }
1.150 -
1.151 -
1.152 - {
1.153 - typedef RevGraphWrapper<const Graph> GW;
1.154 - GW gw(G);
1.155 -
1.156 - EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
1.157 -
1.158 - cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
1.159 - for(GW::NodeIt n(gw); n!=INVALID; ++n) {
1.160 - cout << node_name[GW::Node(n)] << ": ";
1.161 - cout << "out edges: ";
1.162 - for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
1.163 - cout << edge_name[e] << " ";
1.164 - cout << "in edges: ";
1.165 - for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
1.166 - cout << edge_name[e] << " ";
1.167 - cout << endl;
1.168 - }
1.169 -
1.170 - cout << "bfs from t ..." << endl;
1.171 - BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
1.172 - bfs.pushAndSetReached(t);
1.173 - while (!bfs.finished()) {
1.174 - //cout << "edge: ";
1.175 - if (GW::Edge(bfs)!=INVALID) {
1.176 - cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
1.177 - node_name[gw.source(bfs)] <<
1.178 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.179 - node_name[gw.target(bfs)] <<
1.180 - (bfs.isBNodeNewlyReached() ? ": is newly reached." :
1.181 - ": is not newly reached.");
1.182 - } else {
1.183 - cout << "invalid" << /*endl*/", " <<
1.184 - node_name[bfs.source()] <<
1.185 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.186 -
1.187 - "invalid.";
1.188 - }
1.189 - cout << endl;
1.190 - ++bfs;
1.191 - }
1.192 -
1.193 - cout << " /--> -------------> "<< endl;
1.194 - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
1.195 - cout << " / | | / /-> \\ "<< endl;
1.196 - cout << " / | | / | ^ \\ "<< endl;
1.197 - cout << "s | | / | | \\-> t "<< endl;
1.198 - cout << " \\ | | / | | /-> "<< endl;
1.199 - cout << " \\ | --/ / | | / "<< endl;
1.200 - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
1.201 - cout << " \\--> -------------> "<< endl;
1.202 -
1.203 - cout << "dfs from t ..." << endl;
1.204 - DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
1.205 - dfs.pushAndSetReached(t);
1.206 - while (!dfs.finished()) {
1.207 - ++dfs;
1.208 - //cout << "edge: ";
1.209 - if (GW::Edge(dfs)!=INVALID) {
1.210 - cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
1.211 - node_name[gw.source(dfs)] <<
1.212 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.213 - node_name[gw.target(dfs)] <<
1.214 - (dfs.isBNodeNewlyReached() ? ": is newly reached." :
1.215 - ": is not newly reached.");
1.216 - } else {
1.217 - cout << "invalid" << /*endl*/", " <<
1.218 - node_name[dfs.source()] <<
1.219 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.220 -
1.221 - "invalid.";
1.222 - }
1.223 - cout << endl;
1.224 - }
1.225 - }
1.226 -
1.227 -// {
1.228 -// typedef UndirGraphWrapper<const Graph> GW;
1.229 -// GW gw(G);
1.230 -
1.231 -// EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
1.232 -
1.233 -// cout << "bfs and dfs iterator demo on the undirected graph" << endl;
1.234 -// for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
1.235 -// cout << node_name[GW::Node(n)] << ": ";
1.236 -// cout << "out edges: ";
1.237 -// for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
1.238 -// cout << edge_name[e] << " ";
1.239 -// cout << "in edges: ";
1.240 -// for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
1.241 -// cout << edge_name[e] << " ";
1.242 -// cout << endl;
1.243 -// }
1.244 -// // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
1.245 -// // cout << edge_name.get(e) << " ";
1.246 -// // }
1.247 -// // cout << endl;
1.248 -
1.249 -// cout << "bfs from t ..." << endl;
1.250 -// BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
1.251 -// bfs.pushAndSetReached(t);
1.252 -// while (!bfs.finished()) {
1.253 -// //cout << "edge: ";
1.254 -// if (gw.valid(GW::OutEdgeIt(bfs))) {
1.255 -// cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
1.256 -// node_name[gw.aNode(bfs)] <<
1.257 -// (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.258 -// node_name[gw.bNode(bfs)] <<
1.259 -// (bfs.isBNodeNewlyReached() ? ": is newly reached." :
1.260 -// ": is not newly reached.");
1.261 -// } else {
1.262 -// cout << "invalid" << /*endl*/", " <<
1.263 -// node_name[bfs.aNode()] <<
1.264 -// (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.265 -
1.266 -// "invalid.";
1.267 -// }
1.268 -// cout << endl;
1.269 -// ++bfs;
1.270 -// }
1.271 -
1.272 -// cout << " /--> -------------> "<< endl;
1.273 -// cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
1.274 -// cout << " / | | / /-> \\ "<< endl;
1.275 -// cout << " / | | / | ^ \\ "<< endl;
1.276 -// cout << "s | | / | | \\-> t "<< endl;
1.277 -// cout << " \\ | | / | | /-> "<< endl;
1.278 -// cout << " \\ | --/ / | | / "<< endl;
1.279 -// cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
1.280 -// cout << " \\--> -------------> "<< endl;
1.281 -
1.282 -// cout << "dfs from t ..." << endl;
1.283 -// DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
1.284 -// dfs.pushAndSetReached(t);
1.285 -// while (!dfs.finished()) {
1.286 -// ++dfs;
1.287 -// //cout << "edge: ";
1.288 -// if (gw.valid(GW::OutEdgeIt(dfs))) {
1.289 -// cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
1.290 -// node_name[gw.aNode(dfs)] <<
1.291 -// (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.292 -// node_name[gw.bNode(dfs)] <<
1.293 -// (dfs.isBNodeNewlyReached() ? ": is newly reached." :
1.294 -// ": is not newly reached.");
1.295 -// } else {
1.296 -// cout << "invalid" << /*endl*/", " <<
1.297 -// node_name[dfs.aNode()] <<
1.298 -// (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.299 -
1.300 -// "invalid.";
1.301 -// }
1.302 -// cout << endl;
1.303 -// }
1.304 -// }
1.305 -
1.306 -
1.307 -
1.308 - {
1.309 - typedef BidirGraphWrapper<const Graph> GW;
1.310 - GW gw(G);
1.311 -
1.312 - EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
1.313 -
1.314 - cout << "bfs and dfs iterator demo on the bidirected graph" << endl;
1.315 -// for(GW::EdgeIt e(gw); e!=INVALID; ++e) {
1.316 -// cout << node_name[gw.source(e)] << "->" << node_name[gw.target(e)] << " ";
1.317 -// }
1.318 - for(GW::NodeIt n(gw); n!=INVALID; ++n) {
1.319 - cout << node_name[GW::Node(n)] << ": ";
1.320 - cout << "out edges: ";
1.321 - for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)
1.322 - cout << edge_name[e] << " ";
1.323 - cout << "in edges: ";
1.324 - for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)
1.325 - cout << edge_name[e] << " ";
1.326 - cout << endl;
1.327 - }
1.328 -// for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
1.329 -// cout << edge_name.get(e) << " ";
1.330 -// }
1.331 -// cout << endl;
1.332 -
1.333 - cout << "bfs from t ..." << endl;
1.334 - BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
1.335 - bfs.pushAndSetReached(t);
1.336 - while (!bfs.finished()) {
1.337 - //cout << "edge: ";
1.338 - if (GW::Edge(bfs)!=INVALID) {
1.339 - cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<
1.340 - node_name[gw.source(bfs)] <<
1.341 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.342 - node_name[gw.target(bfs)] <<
1.343 - (bfs.isBNodeNewlyReached() ? ": is newly reached." :
1.344 - ": is not newly reached.");
1.345 - } else {
1.346 - cout << "invalid" << /*endl*/", " <<
1.347 - node_name[bfs.source()] <<
1.348 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.349 -
1.350 - "invalid.";
1.351 - }
1.352 - cout << endl;
1.353 - ++bfs;
1.354 - }
1.355 -
1.356 - cout << " /--> -------------> "<< endl;
1.357 - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
1.358 - cout << " / | | / /-> \\ "<< endl;
1.359 - cout << " / | | / | ^ \\ "<< endl;
1.360 - cout << "s | | / | | \\-> t "<< endl;
1.361 - cout << " \\ | | / | | /-> "<< endl;
1.362 - cout << " \\ | --/ / | | / "<< endl;
1.363 - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
1.364 - cout << " \\--> -------------> "<< endl;
1.365 -
1.366 - cout << "dfs from t ..." << endl;
1.367 - DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
1.368 - dfs.pushAndSetReached(t);
1.369 - while (!dfs.finished()) {
1.370 - ++dfs;
1.371 - //cout << "edge: ";
1.372 - if (GW::Edge(dfs)!=INVALID) {
1.373 - cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<
1.374 - node_name[gw.source(dfs)] <<
1.375 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.376 - node_name[gw.target(dfs)] <<
1.377 - (dfs.isBNodeNewlyReached() ? ": is newly reached." :
1.378 - ": is not newly reached.");
1.379 - } else {
1.380 - cout << "invalid" << /*endl*/", " <<
1.381 - node_name[dfs.source()] <<
1.382 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
1.383 -
1.384 - "invalid.";
1.385 - }
1.386 - cout << endl;
1.387 - }
1.388 - }
1.389 -
1.390 - return 0;
1.391 -}