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