1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/iterator_bfs_dfs_demo.cc Fri Jan 30 14:51:01 2004 +0000
1.3 @@ -0,0 +1,284 @@
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 marci;
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 + {
1.189 + std::cout << "iterator dfs demo 1..." << std::endl;
1.190 + ListGraph::NodeMap<bool> reached(G, false);
1.191 + reached.set(s, true);
1.192 + std::stack<ListGraph::OutEdgeIt> dfs_stack;
1.193 + dfs_stack.push(G.first<OutEdgeIt>(s));
1.194 + DfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G, dfs_stack, reached);
1.195 + do {
1.196 + dfs.next();
1.197 + if (OutEdgeIt(dfs).valid()) {
1.198 + std::cout << "OutEdgeIt: " << dfs;
1.199 + std::cout << " aNode: " << G.aNode(dfs);
1.200 + std::cout << " bNode: " << G.bNode(dfs) << " ";
1.201 + } else {
1.202 + std::cout << "OutEdgeIt: " << "invalid";
1.203 + std::cout << " aNode: " << G.aNode(dfs);
1.204 + std::cout << " bNode: " << "invalid" << " ";
1.205 + }
1.206 + if (dfs.bNodeIsNewlyReached()) {
1.207 + std::cout << "bNodeIsNewlyReached ";
1.208 + } else {
1.209 + std::cout << "bNodeIsNotNewlyReached ";
1.210 + }
1.211 + if (dfs.aNodeIsLeaved()) {
1.212 + std::cout << "aNodeIsLeaved ";
1.213 + } else {
1.214 + std::cout << "aNodeIsNotLeaved ";
1.215 + }
1.216 + std::cout<<std::endl;
1.217 + } while (!dfs.finished());
1.218 + }
1.219 +
1.220 +
1.221 + {
1.222 + std::cout << "iterator bfs demo from node 5 with replacing \n OutEdgeIt by InEdgeIt ..." << std::endl;
1.223 + ListGraph::NodeMap<bool> reached(G, false);
1.224 + reached.set(t, true);
1.225 + std::queue<ListGraph::InEdgeIt> bfs_queue;
1.226 + bfs_queue.push(G.first<InEdgeIt>(t));
1.227 + BfsIterator1< ListGraph, ListGraph::InEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
1.228 + while (!bfs.finished()) {
1.229 + if (InEdgeIt(bfs).valid()) {
1.230 + std::cout << "InEdgeIt: " << bfs;
1.231 + std::cout << " aNode: " << G.aNode(bfs);
1.232 + std::cout << " bNode: " << G.bNode(bfs) << " ";
1.233 + } else {
1.234 + std::cout << "InEdgeIt: " << "invalid";
1.235 + std::cout << " aNode: " << G.aNode(bfs);
1.236 + std::cout << " bNode: " << "invalid" << " ";
1.237 + }
1.238 + if (bfs.bNodeIsNewlyReached()) {
1.239 + std::cout << "bNodeIsNewlyReached ";
1.240 + } else {
1.241 + std::cout << "bNodeIsNotNewlyReached ";
1.242 + }
1.243 + if (bfs.aNodeIsExamined()) {
1.244 + std::cout << "aNodeIsExamined ";
1.245 + } else {
1.246 + std::cout << "aNodeIsNotExamined ";
1.247 + }
1.248 + std::cout<<std::endl;
1.249 + bfs.next();
1.250 + }
1.251 + }
1.252 +
1.253 +
1.254 + {
1.255 + std::cout << "the graph is considered as an undirected graph \n by replacing InEdgeIt by SymEdgeIt ..." << std::endl;
1.256 + ListGraph::NodeMap<bool> reached(G, false);
1.257 + reached.set(t, true);
1.258 + std::queue<ListGraph::SymEdgeIt> bfs_queue;
1.259 + bfs_queue.push(G.first<SymEdgeIt>(t));
1.260 + BfsIterator1< ListGraph, ListGraph::SymEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
1.261 + while (!bfs.finished()) {
1.262 + if (SymEdgeIt(bfs).valid()) {
1.263 + std::cout << "SymEdgeIt: " << bfs;
1.264 + std::cout << " aNode: " << G.aNode(bfs);
1.265 + std::cout << " bNode: " << G.bNode(bfs) << " ";
1.266 + } else {
1.267 + std::cout << "SymEdgeIt: " << "invalid";
1.268 + std::cout << " aNode: " << G.aNode(bfs);
1.269 + std::cout << " bNode: " << "invalid" << " ";
1.270 + }
1.271 + if (bfs.bNodeIsNewlyReached()) {
1.272 + std::cout << "bNodeIsNewlyReached ";
1.273 + } else {
1.274 + std::cout << "bNodeIsNotNewlyReached ";
1.275 + }
1.276 + if (bfs.aNodeIsExamined()) {
1.277 + std::cout << "aNodeIsExamined ";
1.278 + } else {
1.279 + std::cout << "aNodeIsNotExamined ";
1.280 + }
1.281 + std::cout<<std::endl;
1.282 + bfs.next();
1.283 + }
1.284 + }
1.285 +
1.286 + return 0;
1.287 +}