1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/experiment/iterator_bfs_demo.cc Sat Apr 03 17:26:46 2004 +0000
1.3 @@ -0,0 +1,322 @@
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_1.h>
1.12 +#include <graph_wrapper_1.h>
1.13 +
1.14 +using namespace hugo;
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.tail(e))+"->"+node_name_map.get(graph.head(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 +}