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