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