1.1 --- a/src/work/bfs_iterator.h Mon Apr 05 14:56:41 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,841 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef HUGO_BFS_ITERATOR_H
1.6 -#define HUGO_BFS_ITERATOR_H
1.7 -
1.8 -#include <queue>
1.9 -#include <stack>
1.10 -#include <utility>
1.11 -#include <graph_wrapper.h>
1.12 -
1.13 -namespace hugo {
1.14 -
1.15 -// template <typename Graph>
1.16 -// struct bfs {
1.17 -// typedef typename Graph::Node Node;
1.18 -// typedef typename Graph::Edge Edge;
1.19 -// typedef typename Graph::NodeIt NodeIt;
1.20 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.21 -// Graph& G;
1.22 -// Node s;
1.23 -// typename Graph::NodeMap<bool> reached;
1.24 -// typename Graph::NodeMap<Edge> pred;
1.25 -// typename Graph::NodeMap<int> dist;
1.26 -// std::queue<Node> bfs_queue;
1.27 -// bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
1.28 -// bfs_queue.push(s);
1.29 -// for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)
1.30 -// reached.set(i, false);
1.31 -// reached.set(s, true);
1.32 -// dist.set(s, 0);
1.33 -// }
1.34 -
1.35 -// void run() {
1.36 -// while (!bfs_queue.empty()) {
1.37 -// Node v=bfs_queue.front();
1.38 -// OutEdgeIt e=G.template first<OutEdgeIt>(v);
1.39 -// bfs_queue.pop();
1.40 -// for( ; e.valid(); ++e) {
1.41 -// Node w=G.bNode(e);
1.42 -// std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
1.43 -// if (!reached.get(w)) {
1.44 -// std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.45 -// bfs_queue.push(w);
1.46 -// dist.set(w, dist.get(v)+1);
1.47 -// pred.set(w, e);
1.48 -// reached.set(w, true);
1.49 -// } else {
1.50 -// std::cout << G.id(w) << " is already reached" << std::endl;
1.51 -// }
1.52 -// }
1.53 -// }
1.54 -// }
1.55 -// };
1.56 -
1.57 -// template <typename Graph>
1.58 -// struct bfs_visitor {
1.59 -// typedef typename Graph::Node Node;
1.60 -// typedef typename Graph::Edge Edge;
1.61 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.62 -// Graph& G;
1.63 -// bfs_visitor(Graph& _G) : G(_G) { }
1.64 -// void at_previously_reached(OutEdgeIt& e) {
1.65 -// //Node v=G.aNode(e);
1.66 -// Node w=G.bNode(e);
1.67 -// std::cout << G.id(w) << " is already reached" << std::endl;
1.68 -// }
1.69 -// void at_newly_reached(OutEdgeIt& e) {
1.70 -// //Node v=G.aNode(e);
1.71 -// Node w=G.bNode(e);
1.72 -// std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.73 -// }
1.74 -// };
1.75 -
1.76 -// template <typename Graph, typename ReachedMap, typename visitor_type>
1.77 -// struct bfs_iterator {
1.78 -// typedef typename Graph::Node Node;
1.79 -// typedef typename Graph::Edge Edge;
1.80 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.81 -// Graph& G;
1.82 -// std::queue<OutEdgeIt>& bfs_queue;
1.83 -// ReachedMap& reached;
1.84 -// visitor_type& visitor;
1.85 -// void process() {
1.86 -// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.87 -// if (bfs_queue.empty()) return;
1.88 -// OutEdgeIt e=bfs_queue.front();
1.89 -// //Node v=G.aNode(e);
1.90 -// Node w=G.bNode(e);
1.91 -// if (!reached.get(w)) {
1.92 -// visitor.at_newly_reached(e);
1.93 -// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.94 -// reached.set(w, true);
1.95 -// } else {
1.96 -// visitor.at_previously_reached(e);
1.97 -// }
1.98 -// }
1.99 -// bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
1.100 -// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.101 -// valid();
1.102 -// }
1.103 -// bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
1.104 -// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.105 -// //if (bfs_queue.empty()) return *this;
1.106 -// if (!valid()) return *this;
1.107 -// ++(bfs_queue.front());
1.108 -// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.109 -// valid();
1.110 -// return *this;
1.111 -// }
1.112 -// //void next() {
1.113 -// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.114 -// // if (bfs_queue.empty()) return;
1.115 -// // ++(bfs_queue.front());
1.116 -// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.117 -// //}
1.118 -// bool valid() {
1.119 -// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.120 -// if (bfs_queue.empty()) return false; else return true;
1.121 -// }
1.122 -// //bool finished() {
1.123 -// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.124 -// // if (bfs_queue.empty()) return true; else return false;
1.125 -// //}
1.126 -// operator Edge () { return bfs_queue.front(); }
1.127 -
1.128 -// };
1.129 -
1.130 -// template <typename Graph, typename ReachedMap>
1.131 -// struct bfs_iterator1 {
1.132 -// typedef typename Graph::Node Node;
1.133 -// typedef typename Graph::Edge Edge;
1.134 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.135 -// Graph& G;
1.136 -// std::queue<OutEdgeIt>& bfs_queue;
1.137 -// ReachedMap& reached;
1.138 -// bool _newly_reached;
1.139 -// bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.140 -// valid();
1.141 -// if (!bfs_queue.empty() && bfs_queue.front().valid()) {
1.142 -// OutEdgeIt e=bfs_queue.front();
1.143 -// Node w=G.bNode(e);
1.144 -// if (!reached.get(w)) {
1.145 -// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.146 -// reached.set(w, true);
1.147 -// _newly_reached=true;
1.148 -// } else {
1.149 -// _newly_reached=false;
1.150 -// }
1.151 -// }
1.152 -// }
1.153 -// bfs_iterator1<Graph, ReachedMap>& operator++() {
1.154 -// if (!valid()) return *this;
1.155 -// ++(bfs_queue.front());
1.156 -// valid();
1.157 -// if (!bfs_queue.empty() && bfs_queue.front().valid()) {
1.158 -// OutEdgeIt e=bfs_queue.front();
1.159 -// Node w=G.bNode(e);
1.160 -// if (!reached.get(w)) {
1.161 -// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.162 -// reached.set(w, true);
1.163 -// _newly_reached=true;
1.164 -// } else {
1.165 -// _newly_reached=false;
1.166 -// }
1.167 -// }
1.168 -// return *this;
1.169 -// }
1.170 -// bool valid() {
1.171 -// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.172 -// if (bfs_queue.empty()) return false; else return true;
1.173 -// }
1.174 -// operator OutEdgeIt() { return bfs_queue.front(); }
1.175 -// //ize
1.176 -// bool newly_reached() { return _newly_reached; }
1.177 -
1.178 -// };
1.179 -
1.180 -// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.181 -// struct BfsIterator {
1.182 -// typedef typename Graph::Node Node;
1.183 -// Graph& G;
1.184 -// std::queue<OutEdgeIt>& bfs_queue;
1.185 -// ReachedMap& reached;
1.186 -// bool b_node_newly_reached;
1.187 -// OutEdgeIt actual_edge;
1.188 -// BfsIterator(Graph& _G,
1.189 -// std::queue<OutEdgeIt>& _bfs_queue,
1.190 -// ReachedMap& _reached) :
1.191 -// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.192 -// actual_edge=bfs_queue.front();
1.193 -// if (actual_edge.valid()) {
1.194 -// Node w=G.bNode(actual_edge);
1.195 -// if (!reached.get(w)) {
1.196 -// bfs_queue.push(G.firstOutEdge(w));
1.197 -// reached.set(w, true);
1.198 -// b_node_newly_reached=true;
1.199 -// } else {
1.200 -// b_node_newly_reached=false;
1.201 -// }
1.202 -// }
1.203 -// }
1.204 -// BfsIterator<Graph, OutEdgeIt, ReachedMap>&
1.205 -// operator++() {
1.206 -// if (bfs_queue.front().valid()) {
1.207 -// ++(bfs_queue.front());
1.208 -// actual_edge=bfs_queue.front();
1.209 -// if (actual_edge.valid()) {
1.210 -// Node w=G.bNode(actual_edge);
1.211 -// if (!reached.get(w)) {
1.212 -// bfs_queue.push(G.firstOutEdge(w));
1.213 -// reached.set(w, true);
1.214 -// b_node_newly_reached=true;
1.215 -// } else {
1.216 -// b_node_newly_reached=false;
1.217 -// }
1.218 -// }
1.219 -// } else {
1.220 -// bfs_queue.pop();
1.221 -// actual_edge=bfs_queue.front();
1.222 -// if (actual_edge.valid()) {
1.223 -// Node w=G.bNode(actual_edge);
1.224 -// if (!reached.get(w)) {
1.225 -// bfs_queue.push(G.firstOutEdge(w));
1.226 -// reached.set(w, true);
1.227 -// b_node_newly_reached=true;
1.228 -// } else {
1.229 -// b_node_newly_reached=false;
1.230 -// }
1.231 -// }
1.232 -// }
1.233 -// return *this;
1.234 -// }
1.235 -// bool finished() { return bfs_queue.empty(); }
1.236 -// operator OutEdgeIt () { return actual_edge; }
1.237 -// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.238 -// bool aNodeIsExamined() { return !(actual_edge.valid()); }
1.239 -// };
1.240 -
1.241 -
1.242 -// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.243 -// struct DfsIterator {
1.244 -// typedef typename Graph::Node Node;
1.245 -// Graph& G;
1.246 -// std::stack<OutEdgeIt>& bfs_queue;
1.247 -// ReachedMap& reached;
1.248 -// bool b_node_newly_reached;
1.249 -// OutEdgeIt actual_edge;
1.250 -// DfsIterator(Graph& _G,
1.251 -// std::stack<OutEdgeIt>& _bfs_queue,
1.252 -// ReachedMap& _reached) :
1.253 -// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.254 -// actual_edge=bfs_queue.top();
1.255 -// if (actual_edge.valid()) {
1.256 -// Node w=G.bNode(actual_edge);
1.257 -// if (!reached.get(w)) {
1.258 -// bfs_queue.push(G.firstOutEdge(w));
1.259 -// reached.set(w, true);
1.260 -// b_node_newly_reached=true;
1.261 -// } else {
1.262 -// ++(bfs_queue.top());
1.263 -// b_node_newly_reached=false;
1.264 -// }
1.265 -// } else {
1.266 -// bfs_queue.pop();
1.267 -// }
1.268 -// }
1.269 -// DfsIterator<Graph, OutEdgeIt, ReachedMap>&
1.270 -// operator++() {
1.271 -// actual_edge=bfs_queue.top();
1.272 -// if (actual_edge.valid()) {
1.273 -// Node w=G.bNode(actual_edge);
1.274 -// if (!reached.get(w)) {
1.275 -// bfs_queue.push(G.firstOutEdge(w));
1.276 -// reached.set(w, true);
1.277 -// b_node_newly_reached=true;
1.278 -// } else {
1.279 -// ++(bfs_queue.top());
1.280 -// b_node_newly_reached=false;
1.281 -// }
1.282 -// } else {
1.283 -// bfs_queue.pop();
1.284 -// }
1.285 -// return *this;
1.286 -// }
1.287 -// bool finished() { return bfs_queue.empty(); }
1.288 -// operator OutEdgeIt () { return actual_edge; }
1.289 -// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.290 -// bool aNodeIsExamined() { return !(actual_edge.valid()); }
1.291 -// };
1.292 -
1.293 -// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.294 -// struct BfsIterator1 {
1.295 -// typedef typename Graph::Node Node;
1.296 -// Graph& G;
1.297 -// std::queue<OutEdgeIt>& bfs_queue;
1.298 -// ReachedMap& reached;
1.299 -// bool b_node_newly_reached;
1.300 -// OutEdgeIt actual_edge;
1.301 -// BfsIterator1(Graph& _G,
1.302 -// std::queue<OutEdgeIt>& _bfs_queue,
1.303 -// ReachedMap& _reached) :
1.304 -// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.305 -// actual_edge=bfs_queue.front();
1.306 -// if (actual_edge.valid()) {
1.307 -// Node w=G.bNode(actual_edge);
1.308 -// if (!reached.get(w)) {
1.309 -// bfs_queue.push(OutEdgeIt(G, w));
1.310 -// reached.set(w, true);
1.311 -// b_node_newly_reached=true;
1.312 -// } else {
1.313 -// b_node_newly_reached=false;
1.314 -// }
1.315 -// }
1.316 -// }
1.317 -// void next() {
1.318 -// if (bfs_queue.front().valid()) {
1.319 -// ++(bfs_queue.front());
1.320 -// actual_edge=bfs_queue.front();
1.321 -// if (actual_edge.valid()) {
1.322 -// Node w=G.bNode(actual_edge);
1.323 -// if (!reached.get(w)) {
1.324 -// bfs_queue.push(OutEdgeIt(G, w));
1.325 -// reached.set(w, true);
1.326 -// b_node_newly_reached=true;
1.327 -// } else {
1.328 -// b_node_newly_reached=false;
1.329 -// }
1.330 -// }
1.331 -// } else {
1.332 -// bfs_queue.pop();
1.333 -// actual_edge=bfs_queue.front();
1.334 -// if (actual_edge.valid()) {
1.335 -// Node w=G.bNode(actual_edge);
1.336 -// if (!reached.get(w)) {
1.337 -// bfs_queue.push(OutEdgeIt(G, w));
1.338 -// reached.set(w, true);
1.339 -// b_node_newly_reached=true;
1.340 -// } else {
1.341 -// b_node_newly_reached=false;
1.342 -// }
1.343 -// }
1.344 -// }
1.345 -// //return *this;
1.346 -// }
1.347 -// bool finished() { return bfs_queue.empty(); }
1.348 -// operator OutEdgeIt () { return actual_edge; }
1.349 -// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.350 -// bool aNodeIsExamined() { return !(actual_edge.valid()); }
1.351 -// };
1.352 -
1.353 -
1.354 -// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.355 -// struct DfsIterator1 {
1.356 -// typedef typename Graph::Node Node;
1.357 -// Graph& G;
1.358 -// std::stack<OutEdgeIt>& bfs_queue;
1.359 -// ReachedMap& reached;
1.360 -// bool b_node_newly_reached;
1.361 -// OutEdgeIt actual_edge;
1.362 -// DfsIterator1(Graph& _G,
1.363 -// std::stack<OutEdgeIt>& _bfs_queue,
1.364 -// ReachedMap& _reached) :
1.365 -// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.366 -// //actual_edge=bfs_queue.top();
1.367 -// //if (actual_edge.valid()) {
1.368 -// // Node w=G.bNode(actual_edge);
1.369 -// //if (!reached.get(w)) {
1.370 -// // bfs_queue.push(OutEdgeIt(G, w));
1.371 -// // reached.set(w, true);
1.372 -// // b_node_newly_reached=true;
1.373 -// //} else {
1.374 -// // ++(bfs_queue.top());
1.375 -// // b_node_newly_reached=false;
1.376 -// //}
1.377 -// //} else {
1.378 -// // bfs_queue.pop();
1.379 -// //}
1.380 -// }
1.381 -// void next() {
1.382 -// actual_edge=bfs_queue.top();
1.383 -// if (actual_edge.valid()) {
1.384 -// Node w=G.bNode(actual_edge);
1.385 -// if (!reached.get(w)) {
1.386 -// bfs_queue.push(OutEdgeIt(G, w));
1.387 -// reached.set(w, true);
1.388 -// b_node_newly_reached=true;
1.389 -// } else {
1.390 -// ++(bfs_queue.top());
1.391 -// b_node_newly_reached=false;
1.392 -// }
1.393 -// } else {
1.394 -// bfs_queue.pop();
1.395 -// }
1.396 -// //return *this;
1.397 -// }
1.398 -// bool finished() { return bfs_queue.empty(); }
1.399 -// operator OutEdgeIt () { return actual_edge; }
1.400 -// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.401 -// bool aNodeIsLeaved() { return !(actual_edge.valid()); }
1.402 -// };
1.403 -
1.404 -// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.405 -// class BfsIterator2 {
1.406 -// typedef typename Graph::Node Node;
1.407 -// const Graph& G;
1.408 -// std::queue<OutEdgeIt> bfs_queue;
1.409 -// ReachedMap reached;
1.410 -// bool b_node_newly_reached;
1.411 -// OutEdgeIt actual_edge;
1.412 -// public:
1.413 -// BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
1.414 -// void pushAndSetReached(Node s) {
1.415 -// reached.set(s, true);
1.416 -// if (bfs_queue.empty()) {
1.417 -// bfs_queue.push(G.template first<OutEdgeIt>(s));
1.418 -// actual_edge=bfs_queue.front();
1.419 -// if (actual_edge.valid()) {
1.420 -// Node w=G.bNode(actual_edge);
1.421 -// if (!reached.get(w)) {
1.422 -// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.423 -// reached.set(w, true);
1.424 -// b_node_newly_reached=true;
1.425 -// } else {
1.426 -// b_node_newly_reached=false;
1.427 -// }
1.428 -// } //else {
1.429 -// //}
1.430 -// } else {
1.431 -// bfs_queue.push(G.template first<OutEdgeIt>(s));
1.432 -// }
1.433 -// }
1.434 -// BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
1.435 -// operator++() {
1.436 -// if (bfs_queue.front().valid()) {
1.437 -// ++(bfs_queue.front());
1.438 -// actual_edge=bfs_queue.front();
1.439 -// if (actual_edge.valid()) {
1.440 -// Node w=G.bNode(actual_edge);
1.441 -// if (!reached.get(w)) {
1.442 -// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.443 -// reached.set(w, true);
1.444 -// b_node_newly_reached=true;
1.445 -// } else {
1.446 -// b_node_newly_reached=false;
1.447 -// }
1.448 -// }
1.449 -// } else {
1.450 -// bfs_queue.pop();
1.451 -// if (!bfs_queue.empty()) {
1.452 -// actual_edge=bfs_queue.front();
1.453 -// if (actual_edge.valid()) {
1.454 -// Node w=G.bNode(actual_edge);
1.455 -// if (!reached.get(w)) {
1.456 -// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.457 -// reached.set(w, true);
1.458 -// b_node_newly_reached=true;
1.459 -// } else {
1.460 -// b_node_newly_reached=false;
1.461 -// }
1.462 -// }
1.463 -// }
1.464 -// }
1.465 -// return *this;
1.466 -// }
1.467 -// bool finished() const { return bfs_queue.empty(); }
1.468 -// operator OutEdgeIt () const { return actual_edge; }
1.469 -// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.470 -// bool isANodeExamined() const { return !(actual_edge.valid()); }
1.471 -// const ReachedMap& getReachedMap() const { return reached; }
1.472 -// const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
1.473 -// };
1.474 -
1.475 -
1.476 -// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.477 -// class BfsIterator3 {
1.478 -// typedef typename Graph::Node Node;
1.479 -// const Graph& G;
1.480 -// std::queue< std::pair<Node, OutEdgeIt> > bfs_queue;
1.481 -// ReachedMap reached;
1.482 -// bool b_node_newly_reached;
1.483 -// OutEdgeIt actual_edge;
1.484 -// public:
1.485 -// BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
1.486 -// void pushAndSetReached(Node s) {
1.487 -// reached.set(s, true);
1.488 -// if (bfs_queue.empty()) {
1.489 -// bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
1.490 -// actual_edge=bfs_queue.front().second;
1.491 -// if (actual_edge.valid()) {
1.492 -// Node w=G.bNode(actual_edge);
1.493 -// if (!reached.get(w)) {
1.494 -// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
1.495 -// reached.set(w, true);
1.496 -// b_node_newly_reached=true;
1.497 -// } else {
1.498 -// b_node_newly_reached=false;
1.499 -// }
1.500 -// } //else {
1.501 -// //}
1.502 -// } else {
1.503 -// bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
1.504 -// }
1.505 -// }
1.506 -// BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
1.507 -// operator++() {
1.508 -// if (bfs_queue.front().second.valid()) {
1.509 -// ++(bfs_queue.front().second);
1.510 -// actual_edge=bfs_queue.front().second;
1.511 -// if (actual_edge.valid()) {
1.512 -// Node w=G.bNode(actual_edge);
1.513 -// if (!reached.get(w)) {
1.514 -// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
1.515 -// reached.set(w, true);
1.516 -// b_node_newly_reached=true;
1.517 -// } else {
1.518 -// b_node_newly_reached=false;
1.519 -// }
1.520 -// }
1.521 -// } else {
1.522 -// bfs_queue.pop();
1.523 -// if (!bfs_queue.empty()) {
1.524 -// actual_edge=bfs_queue.front().second;
1.525 -// if (actual_edge.valid()) {
1.526 -// Node w=G.bNode(actual_edge);
1.527 -// if (!reached.get(w)) {
1.528 -// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
1.529 -// reached.set(w, true);
1.530 -// b_node_newly_reached=true;
1.531 -// } else {
1.532 -// b_node_newly_reached=false;
1.533 -// }
1.534 -// }
1.535 -// }
1.536 -// }
1.537 -// return *this;
1.538 -// }
1.539 -// bool finished() const { return bfs_queue.empty(); }
1.540 -// operator OutEdgeIt () const { return actual_edge; }
1.541 -// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.542 -// bool isANodeExamined() const { return !(actual_edge.valid()); }
1.543 -// Node aNode() const { return bfs_queue.front().first; }
1.544 -// Node bNode() const { return G.bNode(actual_edge); }
1.545 -// const ReachedMap& getReachedMap() const { return reached; }
1.546 -// //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
1.547 -// };
1.548 -
1.549 -
1.550 -// template <typename Graph, typename OutEdgeIt,
1.551 -// typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.552 -// class BfsIterator4 {
1.553 -// typedef typename Graph::Node Node;
1.554 -// const Graph& G;
1.555 -// std::queue<Node> bfs_queue;
1.556 -// ReachedMap& reached;
1.557 -// bool b_node_newly_reached;
1.558 -// OutEdgeIt actual_edge;
1.559 -// bool own_reached_map;
1.560 -// public:
1.561 -// BfsIterator4(const Graph& _G, ReachedMap& _reached) :
1.562 -// G(_G), reached(_reached),
1.563 -// own_reached_map(false) { }
1.564 -// BfsIterator4(const Graph& _G) :
1.565 -// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.566 -// own_reached_map(true) { }
1.567 -// ~BfsIterator4() { if (own_reached_map) delete &reached; }
1.568 -// void pushAndSetReached(Node s) {
1.569 -// //std::cout << "mimi" << &reached << std::endl;
1.570 -// reached.set(s, true);
1.571 -// //std::cout << "mumus" << std::endl;
1.572 -// if (bfs_queue.empty()) {
1.573 -// //std::cout << "bibi1" << std::endl;
1.574 -// bfs_queue.push(s);
1.575 -// //std::cout << "zizi" << std::endl;
1.576 -// G./*getF*/first(actual_edge, s);
1.577 -// //std::cout << "kiki" << std::endl;
1.578 -// if (G.valid(actual_edge)/*.valid()*/) {
1.579 -// Node w=G.bNode(actual_edge);
1.580 -// if (!reached.get(w)) {
1.581 -// bfs_queue.push(w);
1.582 -// reached.set(w, true);
1.583 -// b_node_newly_reached=true;
1.584 -// } else {
1.585 -// b_node_newly_reached=false;
1.586 -// }
1.587 -// }
1.588 -// } else {
1.589 -// //std::cout << "bibi2" << std::endl;
1.590 -// bfs_queue.push(s);
1.591 -// }
1.592 -// }
1.593 -// BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.594 -// operator++() {
1.595 -// if (G.valid(actual_edge)/*.valid()*/) {
1.596 -// /*++*/G.next(actual_edge);
1.597 -// if (G.valid(actual_edge)/*.valid()*/) {
1.598 -// Node w=G.bNode(actual_edge);
1.599 -// if (!reached.get(w)) {
1.600 -// bfs_queue.push(w);
1.601 -// reached.set(w, true);
1.602 -// b_node_newly_reached=true;
1.603 -// } else {
1.604 -// b_node_newly_reached=false;
1.605 -// }
1.606 -// }
1.607 -// } else {
1.608 -// bfs_queue.pop();
1.609 -// if (!bfs_queue.empty()) {
1.610 -// G./*getF*/first(actual_edge, bfs_queue.front());
1.611 -// if (G.valid(actual_edge)/*.valid()*/) {
1.612 -// Node w=G.bNode(actual_edge);
1.613 -// if (!reached.get(w)) {
1.614 -// bfs_queue.push(w);
1.615 -// reached.set(w, true);
1.616 -// b_node_newly_reached=true;
1.617 -// } else {
1.618 -// b_node_newly_reached=false;
1.619 -// }
1.620 -// }
1.621 -// }
1.622 -// }
1.623 -// return *this;
1.624 -// }
1.625 -// bool finished() const { return bfs_queue.empty(); }
1.626 -// operator OutEdgeIt () const { return actual_edge; }
1.627 -// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.628 -// bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.629 -// Node aNode() const { return bfs_queue.front(); }
1.630 -// Node bNode() const { return G.bNode(actual_edge); }
1.631 -// const ReachedMap& getReachedMap() const { return reached; }
1.632 -// const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.633 -// };
1.634 -
1.635 -
1.636 - template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.637 - typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.638 - class BfsIterator5 {
1.639 - typedef typename GraphWrapper::Node Node;
1.640 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.641 - GraphWrapper G;
1.642 - std::queue<Node> bfs_queue;
1.643 - ReachedMap& reached;
1.644 - bool b_node_newly_reached;
1.645 - OutEdgeIt actual_edge;
1.646 - bool own_reached_map;
1.647 - public:
1.648 - BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.649 - G(_G), reached(_reached),
1.650 - own_reached_map(false) { }
1.651 - BfsIterator5(const GraphWrapper& _G) :
1.652 - G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.653 - own_reached_map(true) { }
1.654 -// BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
1.655 -// ReachedMap& _reached) :
1.656 -// G(_G), reached(_reached),
1.657 -// own_reached_map(false) { }
1.658 -// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
1.659 -// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.660 -// own_reached_map(true) { }
1.661 - ~BfsIterator5() { if (own_reached_map) delete &reached; }
1.662 - void pushAndSetReached(Node s) {
1.663 - reached.set(s, true);
1.664 - if (bfs_queue.empty()) {
1.665 - bfs_queue.push(s);
1.666 - G./*getF*/first(actual_edge, s);
1.667 - if (G.valid(actual_edge)/*.valid()*/) {
1.668 - Node w=G.bNode(actual_edge);
1.669 - if (!reached.get(w)) {
1.670 - bfs_queue.push(w);
1.671 - reached.set(w, true);
1.672 - b_node_newly_reached=true;
1.673 - } else {
1.674 - b_node_newly_reached=false;
1.675 - }
1.676 - }
1.677 - } else {
1.678 - bfs_queue.push(s);
1.679 - }
1.680 - }
1.681 - BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
1.682 - operator++() {
1.683 - if (G.valid(actual_edge)/*.valid()*/) {
1.684 - /*++*/G.next(actual_edge);
1.685 - if (G.valid(actual_edge)/*.valid()*/) {
1.686 - Node w=G.bNode(actual_edge);
1.687 - if (!reached.get(w)) {
1.688 - bfs_queue.push(w);
1.689 - reached.set(w, true);
1.690 - b_node_newly_reached=true;
1.691 - } else {
1.692 - b_node_newly_reached=false;
1.693 - }
1.694 - }
1.695 - } else {
1.696 - bfs_queue.pop();
1.697 - if (!bfs_queue.empty()) {
1.698 - G./*getF*/first(actual_edge, bfs_queue.front());
1.699 - if (G.valid(actual_edge)/*.valid()*/) {
1.700 - Node w=G.bNode(actual_edge);
1.701 - if (!reached.get(w)) {
1.702 - bfs_queue.push(w);
1.703 - reached.set(w, true);
1.704 - b_node_newly_reached=true;
1.705 - } else {
1.706 - b_node_newly_reached=false;
1.707 - }
1.708 - }
1.709 - }
1.710 - }
1.711 - return *this;
1.712 - }
1.713 - bool finished() const { return bfs_queue.empty(); }
1.714 - operator OutEdgeIt () const { return actual_edge; }
1.715 - bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.716 - bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.717 - Node aNode() const { return bfs_queue.front(); }
1.718 - Node bNode() const { return G.bNode(actual_edge); }
1.719 - const ReachedMap& getReachedMap() const { return reached; }
1.720 - const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.721 - };
1.722 -
1.723 -// template <typename Graph, typename OutEdgeIt,
1.724 -// typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.725 -// class DfsIterator4 {
1.726 -// typedef typename Graph::Node Node;
1.727 -// const Graph& G;
1.728 -// std::stack<OutEdgeIt> dfs_stack;
1.729 -// bool b_node_newly_reached;
1.730 -// OutEdgeIt actual_edge;
1.731 -// Node actual_node;
1.732 -// ReachedMap& reached;
1.733 -// bool own_reached_map;
1.734 -// public:
1.735 -// DfsIterator4(const Graph& _G, ReachedMap& _reached) :
1.736 -// G(_G), reached(_reached),
1.737 -// own_reached_map(false) { }
1.738 -// DfsIterator4(const Graph& _G) :
1.739 -// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.740 -// own_reached_map(true) { }
1.741 -// ~DfsIterator4() { if (own_reached_map) delete &reached; }
1.742 -// void pushAndSetReached(Node s) {
1.743 -// actual_node=s;
1.744 -// reached.set(s, true);
1.745 -// dfs_stack.push(G.template first<OutEdgeIt>(s));
1.746 -// }
1.747 -// DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.748 -// operator++() {
1.749 -// actual_edge=dfs_stack.top();
1.750 -// //actual_node=G.aNode(actual_edge);
1.751 -// if (G.valid(actual_edge)/*.valid()*/) {
1.752 -// Node w=G.bNode(actual_edge);
1.753 -// actual_node=w;
1.754 -// if (!reached.get(w)) {
1.755 -// dfs_stack.push(G.template first<OutEdgeIt>(w));
1.756 -// reached.set(w, true);
1.757 -// b_node_newly_reached=true;
1.758 -// } else {
1.759 -// actual_node=G.aNode(actual_edge);
1.760 -// /*++*/G.next(dfs_stack.top());
1.761 -// b_node_newly_reached=false;
1.762 -// }
1.763 -// } else {
1.764 -// //actual_node=G.aNode(dfs_stack.top());
1.765 -// dfs_stack.pop();
1.766 -// }
1.767 -// return *this;
1.768 -// }
1.769 -// bool finished() const { return dfs_stack.empty(); }
1.770 -// operator OutEdgeIt () const { return actual_edge; }
1.771 -// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.772 -// bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.773 -// Node aNode() const { return actual_node; /*FIXME*/}
1.774 -// Node bNode() const { return G.bNode(actual_edge); }
1.775 -// const ReachedMap& getReachedMap() const { return reached; }
1.776 -// const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.777 -// };
1.778 -
1.779 - template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.780 - typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.781 - class DfsIterator5 {
1.782 - typedef typename GraphWrapper::Node Node;
1.783 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.784 - GraphWrapper G;
1.785 - std::stack<OutEdgeIt> dfs_stack;
1.786 - bool b_node_newly_reached;
1.787 - OutEdgeIt actual_edge;
1.788 - Node actual_node;
1.789 - ReachedMap& reached;
1.790 - bool own_reached_map;
1.791 - public:
1.792 - DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.793 - G(_G), reached(_reached),
1.794 - own_reached_map(false) { }
1.795 - DfsIterator5(const GraphWrapper& _G) :
1.796 - G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.797 - own_reached_map(true) { }
1.798 - ~DfsIterator5() { if (own_reached_map) delete &reached; }
1.799 - void pushAndSetReached(Node s) {
1.800 - actual_node=s;
1.801 - reached.set(s, true);
1.802 - OutEdgeIt e;
1.803 - G.first(e, s);
1.804 - dfs_stack.push(e);
1.805 - }
1.806 - DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
1.807 - operator++() {
1.808 - actual_edge=dfs_stack.top();
1.809 - //actual_node=G.aNode(actual_edge);
1.810 - if (G.valid(actual_edge)/*.valid()*/) {
1.811 - Node w=G.bNode(actual_edge);
1.812 - actual_node=w;
1.813 - if (!reached.get(w)) {
1.814 - OutEdgeIt e;
1.815 - G.first(e, w);
1.816 - dfs_stack.push(e);
1.817 - reached.set(w, true);
1.818 - b_node_newly_reached=true;
1.819 - } else {
1.820 - actual_node=G.aNode(actual_edge);
1.821 - /*++*/G.next(dfs_stack.top());
1.822 - b_node_newly_reached=false;
1.823 - }
1.824 - } else {
1.825 - //actual_node=G.aNode(dfs_stack.top());
1.826 - dfs_stack.pop();
1.827 - }
1.828 - return *this;
1.829 - }
1.830 - bool finished() const { return dfs_stack.empty(); }
1.831 - operator OutEdgeIt () const { return actual_edge; }
1.832 - bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.833 - bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.834 - Node aNode() const { return actual_node; /*FIXME*/}
1.835 - Node bNode() const { return G.bNode(actual_edge); }
1.836 - const ReachedMap& getReachedMap() const { return reached; }
1.837 - const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.838 - };
1.839 -
1.840 -
1.841 -
1.842 -} // namespace hugo
1.843 -
1.844 -#endif //HUGO_BFS_ITERATOR_H
2.1 --- a/src/work/edmonds_karp.h Mon Apr 05 14:56:41 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,1238 +0,0 @@
2.4 -// -*- c++ -*-
2.5 -#ifndef HUGO_EDMONDS_KARP_H
2.6 -#define HUGO_EDMONDS_KARP_H
2.7 -
2.8 -#include <algorithm>
2.9 -#include <list>
2.10 -#include <iterator>
2.11 -
2.12 -#include <bfs_iterator.h>
2.13 -#include <invalid.h>
2.14 -
2.15 -namespace hugo {
2.16 -
2.17 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.18 - class ResGraph {
2.19 - public:
2.20 - typedef typename Graph::Node Node;
2.21 - typedef typename Graph::NodeIt NodeIt;
2.22 - private:
2.23 - typedef typename Graph::SymEdgeIt OldSymEdgeIt;
2.24 - const Graph& G;
2.25 - FlowMap& flow;
2.26 - const CapacityMap& capacity;
2.27 - public:
2.28 - ResGraph(const Graph& _G, FlowMap& _flow,
2.29 - const CapacityMap& _capacity) :
2.30 - G(_G), flow(_flow), capacity(_capacity) { }
2.31 -
2.32 - class Edge;
2.33 - class OutEdgeIt;
2.34 - friend class Edge;
2.35 - friend class OutEdgeIt;
2.36 -
2.37 - class Edge {
2.38 - friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
2.39 - protected:
2.40 - const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
2.41 - OldSymEdgeIt sym;
2.42 - public:
2.43 - Edge() { }
2.44 - //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
2.45 - Number free() const {
2.46 - if (resG->G.aNode(sym)==resG->G.tail(sym)) {
2.47 - return (resG->capacity.get(sym)-resG->flow.get(sym));
2.48 - } else {
2.49 - return (resG->flow.get(sym));
2.50 - }
2.51 - }
2.52 - bool valid() const { return sym.valid(); }
2.53 - void augment(Number a) const {
2.54 - if (resG->G.aNode(sym)==resG->G.tail(sym)) {
2.55 - resG->flow.set(sym, resG->flow.get(sym)+a);
2.56 - //resG->flow[sym]+=a;
2.57 - } else {
2.58 - resG->flow.set(sym, resG->flow.get(sym)-a);
2.59 - //resG->flow[sym]-=a;
2.60 - }
2.61 - }
2.62 - };
2.63 -
2.64 - class OutEdgeIt : public Edge {
2.65 - friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
2.66 - public:
2.67 - OutEdgeIt() { }
2.68 - //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
2.69 - private:
2.70 - OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
2.71 - resG=&_resG;
2.72 - sym=resG->G.template first<OldSymEdgeIt>(v);
2.73 - while( sym.valid() && !(free()>0) ) { ++sym; }
2.74 - }
2.75 - public:
2.76 - OutEdgeIt& operator++() {
2.77 - ++sym;
2.78 - while( sym.valid() && !(free()>0) ) { ++sym; }
2.79 - return *this;
2.80 - }
2.81 - };
2.82 -
2.83 - void /*getF*/first(OutEdgeIt& e, Node v) const {
2.84 - e=OutEdgeIt(*this, v);
2.85 - }
2.86 - void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
2.87 -
2.88 - template< typename It >
2.89 - It first() const {
2.90 - It e;
2.91 - /*getF*/first(e);
2.92 - return e;
2.93 - }
2.94 -
2.95 - template< typename It >
2.96 - It first(Node v) const {
2.97 - It e;
2.98 - /*getF*/first(e, v);
2.99 - return e;
2.100 - }
2.101 -
2.102 - Node tail(Edge e) const { return G.aNode(e.sym); }
2.103 - Node head(Edge e) const { return G.bNode(e.sym); }
2.104 -
2.105 - Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
2.106 - Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
2.107 -
2.108 - int id(Node v) const { return G.id(v); }
2.109 -
2.110 - template <typename S>
2.111 - class NodeMap {
2.112 - typename Graph::NodeMap<S> node_map;
2.113 - public:
2.114 - NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
2.115 - NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
2.116 - void set(Node nit, S a) { node_map.set(nit, a); }
2.117 - S get(Node nit) const { return node_map.get(nit); }
2.118 - S& operator[](Node nit) { return node_map[nit]; }
2.119 - const S& operator[](Node nit) const { return node_map[nit]; }
2.120 - };
2.121 -
2.122 - };
2.123 -
2.124 -
2.125 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.126 - class ResGraph2 {
2.127 - public:
2.128 - typedef typename Graph::Node Node;
2.129 - typedef typename Graph::NodeIt NodeIt;
2.130 - private:
2.131 - //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
2.132 - typedef typename Graph::OutEdgeIt OldOutEdgeIt;
2.133 - typedef typename Graph::InEdgeIt OldInEdgeIt;
2.134 -
2.135 - const Graph& G;
2.136 - FlowMap& flow;
2.137 - const CapacityMap& capacity;
2.138 - public:
2.139 - ResGraph2(const Graph& _G, FlowMap& _flow,
2.140 - const CapacityMap& _capacity) :
2.141 - G(_G), flow(_flow), capacity(_capacity) { }
2.142 -
2.143 - class Edge;
2.144 - class OutEdgeIt;
2.145 - friend class Edge;
2.146 - friend class OutEdgeIt;
2.147 -
2.148 - class Edge {
2.149 - friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
2.150 - protected:
2.151 - const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
2.152 - //OldSymEdgeIt sym;
2.153 - OldOutEdgeIt out;
2.154 - OldInEdgeIt in;
2.155 - bool out_or_in; //true, iff out
2.156 - public:
2.157 - Edge() : out_or_in(true) { }
2.158 - Number free() const {
2.159 - if (out_or_in) {
2.160 - return (resG->capacity.get(out)-resG->flow.get(out));
2.161 - } else {
2.162 - return (resG->flow.get(in));
2.163 - }
2.164 - }
2.165 - bool valid() const {
2.166 - return out_or_in && out.valid() || in.valid(); }
2.167 - void augment(Number a) const {
2.168 - if (out_or_in) {
2.169 - resG->flow.set(out, resG->flow.get(out)+a);
2.170 - } else {
2.171 - resG->flow.set(in, resG->flow.get(in)-a);
2.172 - }
2.173 - }
2.174 - };
2.175 -
2.176 - class OutEdgeIt : public Edge {
2.177 - friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
2.178 - public:
2.179 - OutEdgeIt() { }
2.180 - private:
2.181 - OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
2.182 - resG=&_resG;
2.183 - out=resG->G.template first<OldOutEdgeIt>(v);
2.184 - while( out.valid() && !(free()>0) ) { ++out; }
2.185 - if (!out.valid()) {
2.186 - out_or_in=0;
2.187 - in=resG->G.template first<OldInEdgeIt>(v);
2.188 - while( in.valid() && !(free()>0) ) { ++in; }
2.189 - }
2.190 - }
2.191 - public:
2.192 - OutEdgeIt& operator++() {
2.193 - if (out_or_in) {
2.194 - Node v=resG->G.aNode(out);
2.195 - ++out;
2.196 - while( out.valid() && !(free()>0) ) { ++out; }
2.197 - if (!out.valid()) {
2.198 - out_or_in=0;
2.199 - in=resG->G.template first<OldInEdgeIt>(v);
2.200 - while( in.valid() && !(free()>0) ) { ++in; }
2.201 - }
2.202 - } else {
2.203 - ++in;
2.204 - while( in.valid() && !(free()>0) ) { ++in; }
2.205 - }
2.206 - return *this;
2.207 - }
2.208 - };
2.209 -
2.210 - void /*getF*/first(OutEdgeIt& e, Node v) const {
2.211 - e=OutEdgeIt(*this, v);
2.212 - }
2.213 - void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
2.214 -
2.215 - template< typename It >
2.216 - It first() const {
2.217 - It e;
2.218 - /*getF*/first(e);
2.219 - return e;
2.220 - }
2.221 -
2.222 - template< typename It >
2.223 - It first(Node v) const {
2.224 - It e;
2.225 - /*getF*/first(e, v);
2.226 - return e;
2.227 - }
2.228 -
2.229 - Node tail(Edge e) const {
2.230 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
2.231 - Node head(Edge e) const {
2.232 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
2.233 -
2.234 - Node aNode(OutEdgeIt e) const {
2.235 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
2.236 - Node bNode(OutEdgeIt e) const {
2.237 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
2.238 -
2.239 - int id(Node v) const { return G.id(v); }
2.240 -
2.241 - template <typename S>
2.242 - class NodeMap {
2.243 - typename Graph::NodeMap<S> node_map;
2.244 - public:
2.245 - NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
2.246 - NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
2.247 - void set(Node nit, S a) { node_map.set(nit, a); }
2.248 - S get(Node nit) const { return node_map.get(nit); }
2.249 - };
2.250 - };
2.251 -
2.252 -
2.253 - template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
2.254 - class MaxFlow {
2.255 - protected:
2.256 - typedef GraphWrapper GW;
2.257 - typedef typename GW::Node Node;
2.258 - typedef typename GW::Edge Edge;
2.259 - typedef typename GW::EdgeIt EdgeIt;
2.260 - typedef typename GW::OutEdgeIt OutEdgeIt;
2.261 - typedef typename GW::InEdgeIt InEdgeIt;
2.262 - //const Graph* G;
2.263 - GW gw;
2.264 - Node s;
2.265 - Node t;
2.266 - FlowMap* flow;
2.267 - const CapacityMap* capacity;
2.268 - typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW;
2.269 - typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
2.270 - typedef typename ResGW::Edge ResGWEdge;
2.271 - public:
2.272 -
2.273 - MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
2.274 - gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
2.275 -
2.276 - bool augmentOnShortestPath() {
2.277 - ResGW res_graph(gw, *flow, *capacity);
2.278 - bool _augment=false;
2.279 -
2.280 - typedef typename ResGW::NodeMap<bool> ReachedMap;
2.281 - BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
2.282 - bfs.pushAndSetReached(s);
2.283 -
2.284 - typename ResGW::NodeMap<ResGWEdge> pred(res_graph);
2.285 - pred.set(s, INVALID);
2.286 -
2.287 - typename ResGW::NodeMap<Number> free(res_graph);
2.288 -
2.289 - //searching for augmenting path
2.290 - while ( !bfs.finished() ) {
2.291 - ResGWOutEdgeIt e=bfs;
2.292 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.293 - Node v=res_graph.tail(e);
2.294 - Node w=res_graph.head(e);
2.295 - pred.set(w, e);
2.296 - if (res_graph.valid(pred.get(v))) {
2.297 - free.set(w, std::min(free.get(v), res_graph.resCap(e)));
2.298 - } else {
2.299 - free.set(w, res_graph.resCap(e));
2.300 - }
2.301 - if (res_graph.head(e)==t) { _augment=true; break; }
2.302 - }
2.303 -
2.304 - ++bfs;
2.305 - } //end of searching augmenting path
2.306 -
2.307 - if (_augment) {
2.308 - Node n=t;
2.309 - Number augment_value=free.get(t);
2.310 - while (res_graph.valid(pred.get(n))) {
2.311 - ResGWEdge e=pred.get(n);
2.312 - res_graph.augment(e, augment_value);
2.313 - n=res_graph.tail(e);
2.314 - }
2.315 - }
2.316 -
2.317 - return _augment;
2.318 - }
2.319 -
2.320 - template<typename MapGraphWrapper>
2.321 - class DistanceMap {
2.322 - protected:
2.323 - MapGraphWrapper gw;
2.324 - typename MapGraphWrapper::NodeMap<int> dist;
2.325 - public:
2.326 - DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
2.327 - void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
2.328 - int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
2.329 - bool get(const typename MapGraphWrapper::Edge& e) const {
2.330 - return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
2.331 - }
2.332 - };
2.333 -
2.334 - template<typename MutableGraph> bool augmentOnBlockingFlow() {
2.335 - typedef MutableGraph MG;
2.336 - bool _augment=false;
2.337 -
2.338 - ResGW res_graph(gw, *flow, *capacity);
2.339 -
2.340 - typedef typename ResGW::NodeMap<bool> ReachedMap;
2.341 - BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
2.342 -
2.343 - bfs.pushAndSetReached(s);
2.344 - //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
2.345 - DistanceMap<ResGW> dist(res_graph);
2.346 - while ( !bfs.finished() ) {
2.347 - ResGWOutEdgeIt e=bfs;
2.348 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.349 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.350 - }
2.351 - ++bfs;
2.352 - } //computing distances from s in the residual graph
2.353 -
2.354 - MG F;
2.355 - typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
2.356 - FilterResGW filter_res_graph(res_graph, dist);
2.357 - typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
2.358 - {
2.359 - typename ResGW::NodeIt n;
2.360 - for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
2.361 - res_graph_to_F.set(n, F.addNode());
2.362 - }
2.363 - }
2.364 -
2.365 - typename MG::Node sF=res_graph_to_F.get(s);
2.366 - typename MG::Node tF=res_graph_to_F.get(t);
2.367 - typename MG::EdgeMap<ResGWEdge> original_edge(F);
2.368 - typename MG::EdgeMap<Number> residual_capacity(F);
2.369 -
2.370 - //Making F to the graph containing the edges of the residual graph
2.371 - //which are in some shortest paths
2.372 - {
2.373 - typename FilterResGW::EdgeIt e;
2.374 - for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
2.375 - //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
2.376 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
2.377 - original_edge.update();
2.378 - original_edge.set(f, e);
2.379 - residual_capacity.update();
2.380 - residual_capacity.set(f, res_graph.resCap(e));
2.381 - //}
2.382 - }
2.383 - }
2.384 -
2.385 - bool __augment=true;
2.386 -
2.387 - while (__augment) {
2.388 - __augment=false;
2.389 - //computing blocking flow with dfs
2.390 - typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
2.391 - DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
2.392 - typename MG::NodeMap<typename MG::Edge> pred(F);
2.393 - pred.set(sF, INVALID);
2.394 - //invalid iterators for sources
2.395 -
2.396 - typename MG::NodeMap<Number> free(F);
2.397 -
2.398 - dfs.pushAndSetReached(sF);
2.399 - while (!dfs.finished()) {
2.400 - ++dfs;
2.401 - if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
2.402 - if (dfs.isBNodeNewlyReached()) {
2.403 - typename MG::Node v=F.aNode(dfs);
2.404 - typename MG::Node w=F.bNode(dfs);
2.405 - pred.set(w, dfs);
2.406 - if (F.valid(pred.get(v))) {
2.407 - free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
2.408 - } else {
2.409 - free.set(w, residual_capacity.get(dfs));
2.410 - }
2.411 - if (w==tF) {
2.412 - __augment=true;
2.413 - _augment=true;
2.414 - break;
2.415 - }
2.416 -
2.417 - } else {
2.418 - F.erase(/*typename MG::OutEdgeIt*/(dfs));
2.419 - }
2.420 - }
2.421 - }
2.422 -
2.423 - if (__augment) {
2.424 - typename MG::Node n=tF;
2.425 - Number augment_value=free.get(tF);
2.426 - while (F.valid(pred.get(n))) {
2.427 - typename MG::Edge e=pred.get(n);
2.428 - res_graph.augment(original_edge.get(e), augment_value);
2.429 - n=F.tail(e);
2.430 - if (residual_capacity.get(e)==augment_value)
2.431 - F.erase(e);
2.432 - else
2.433 - residual_capacity.set(e, residual_capacity.get(e)-augment_value);
2.434 - }
2.435 - }
2.436 -
2.437 - }
2.438 -
2.439 - return _augment;
2.440 - }
2.441 -
2.442 - template<typename MutableGraph> bool augmentOnBlockingFlow1() {
2.443 - typedef MutableGraph MG;
2.444 - bool _augment=false;
2.445 -
2.446 - ResGW res_graph(gw, *flow, *capacity);
2.447 -
2.448 - //bfs for distances on the residual graph
2.449 - typedef typename ResGW::NodeMap<bool> ReachedMap;
2.450 - BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
2.451 - bfs.pushAndSetReached(s);
2.452 - typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
2.453 -
2.454 - //F will contain the physical copy of the residual graph
2.455 - //with the set of edges which are on shortest paths
2.456 - MG F;
2.457 - typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
2.458 - {
2.459 - typename ResGW::NodeIt n;
2.460 - for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
2.461 - res_graph_to_F.set(n, F.addNode());
2.462 - }
2.463 - }
2.464 -
2.465 - typename MG::Node sF=res_graph_to_F.get(s);
2.466 - typename MG::Node tF=res_graph_to_F.get(t);
2.467 - typename MG::EdgeMap<ResGWEdge> original_edge(F);
2.468 - typename MG::EdgeMap<Number> residual_capacity(F);
2.469 -
2.470 - while ( !bfs.finished() ) {
2.471 - ResGWOutEdgeIt e=bfs;
2.472 - if (res_graph.valid(e)) {
2.473 - if (bfs.isBNodeNewlyReached()) {
2.474 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.475 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
2.476 - original_edge.update();
2.477 - original_edge.set(f, e);
2.478 - residual_capacity.update();
2.479 - residual_capacity.set(f, res_graph.resCap(e));
2.480 - } else {
2.481 - if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
2.482 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
2.483 - original_edge.update();
2.484 - original_edge.set(f, e);
2.485 - residual_capacity.update();
2.486 - residual_capacity.set(f, res_graph.resCap(e));
2.487 - }
2.488 - }
2.489 - }
2.490 - ++bfs;
2.491 - } //computing distances from s in the residual graph
2.492 -
2.493 - bool __augment=true;
2.494 -
2.495 - while (__augment) {
2.496 - __augment=false;
2.497 - //computing blocking flow with dfs
2.498 - typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
2.499 - DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
2.500 - typename MG::NodeMap<typename MG::Edge> pred(F);
2.501 - pred.set(sF, INVALID);
2.502 - //invalid iterators for sources
2.503 -
2.504 - typename MG::NodeMap<Number> free(F);
2.505 -
2.506 - dfs.pushAndSetReached(sF);
2.507 - while (!dfs.finished()) {
2.508 - ++dfs;
2.509 - if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
2.510 - if (dfs.isBNodeNewlyReached()) {
2.511 - typename MG::Node v=F.aNode(dfs);
2.512 - typename MG::Node w=F.bNode(dfs);
2.513 - pred.set(w, dfs);
2.514 - if (F.valid(pred.get(v))) {
2.515 - free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
2.516 - } else {
2.517 - free.set(w, residual_capacity.get(dfs));
2.518 - }
2.519 - if (w==tF) {
2.520 - __augment=true;
2.521 - _augment=true;
2.522 - break;
2.523 - }
2.524 -
2.525 - } else {
2.526 - F.erase(/*typename MG::OutEdgeIt*/(dfs));
2.527 - }
2.528 - }
2.529 - }
2.530 -
2.531 - if (__augment) {
2.532 - typename MG::Node n=tF;
2.533 - Number augment_value=free.get(tF);
2.534 - while (F.valid(pred.get(n))) {
2.535 - typename MG::Edge e=pred.get(n);
2.536 - res_graph.augment(original_edge.get(e), augment_value);
2.537 - n=F.tail(e);
2.538 - if (residual_capacity.get(e)==augment_value)
2.539 - F.erase(e);
2.540 - else
2.541 - residual_capacity.set(e, residual_capacity.get(e)-augment_value);
2.542 - }
2.543 - }
2.544 -
2.545 - }
2.546 -
2.547 - return _augment;
2.548 - }
2.549 -
2.550 - bool augmentOnBlockingFlow2() {
2.551 - bool _augment=false;
2.552 -
2.553 - ResGW res_graph(gw, *flow, *capacity);
2.554 -
2.555 - typedef typename ResGW::NodeMap<bool> ReachedMap;
2.556 - BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
2.557 -
2.558 - bfs.pushAndSetReached(s);
2.559 - DistanceMap<ResGW> dist(res_graph);
2.560 - while ( !bfs.finished() ) {
2.561 - ResGWOutEdgeIt e=bfs;
2.562 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.563 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.564 - }
2.565 - ++bfs;
2.566 - } //computing distances from s in the residual graph
2.567 -
2.568 - //Subgraph containing the edges on some shortest paths
2.569 - typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
2.570 - FilterResGW filter_res_graph(res_graph, dist);
2.571 -
2.572 - //Subgraph, which is able to delete edges which are already
2.573 - //met by the dfs
2.574 - typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>
2.575 - first_out_edges(filter_res_graph);
2.576 - typename FilterResGW::NodeIt v;
2.577 - for(filter_res_graph.first(v); filter_res_graph.valid(v);
2.578 - filter_res_graph.next(v))
2.579 - {
2.580 - typename FilterResGW::OutEdgeIt e;
2.581 - filter_res_graph.first(e, v);
2.582 - first_out_edges.set(v, e);
2.583 - }
2.584 - typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
2.585 - NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
2.586 - ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
2.587 -
2.588 - bool __augment=true;
2.589 -
2.590 - while (__augment) {
2.591 -
2.592 - __augment=false;
2.593 - //computing blocking flow with dfs
2.594 - typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;
2.595 - DfsIterator5< ErasingResGW, BlockingReachedMap >
2.596 - dfs(erasing_res_graph);
2.597 - typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
2.598 - pred(erasing_res_graph);
2.599 - pred.set(s, INVALID);
2.600 - //invalid iterators for sources
2.601 -
2.602 - typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
2.603 -
2.604 - dfs.pushAndSetReached(s);
2.605 - while (!dfs.finished()) {
2.606 - ++dfs;
2.607 - if (erasing_res_graph.valid(
2.608 - /*typename ErasingResGW::OutEdgeIt*/(dfs)))
2.609 - {
2.610 - if (dfs.isBNodeNewlyReached()) {
2.611 -
2.612 - typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
2.613 - typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
2.614 -
2.615 - pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
2.616 - if (erasing_res_graph.valid(pred.get(v))) {
2.617 - free.set(w, std::min(free.get(v), res_graph.resCap(dfs)));
2.618 - } else {
2.619 - free.set(w, res_graph.resCap(dfs));
2.620 - }
2.621 -
2.622 - if (w==t) {
2.623 - __augment=true;
2.624 - _augment=true;
2.625 - break;
2.626 - }
2.627 - } else {
2.628 - erasing_res_graph.erase(dfs);
2.629 - }
2.630 - }
2.631 - }
2.632 -
2.633 - if (__augment) {
2.634 - typename ErasingResGW::Node n=t;
2.635 - Number augment_value=free.get(n);
2.636 - while (erasing_res_graph.valid(pred.get(n))) {
2.637 - typename ErasingResGW::OutEdgeIt e=pred.get(n);
2.638 - res_graph.augment(e, augment_value);
2.639 - n=erasing_res_graph.tail(e);
2.640 - if (res_graph.resCap(e)==0)
2.641 - erasing_res_graph.erase(e);
2.642 - }
2.643 - }
2.644 -
2.645 - } //while (__augment)
2.646 -
2.647 - return _augment;
2.648 - }
2.649 -
2.650 -// bool augmentOnBlockingFlow2() {
2.651 -// bool _augment=false;
2.652 -
2.653 -// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
2.654 -// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
2.655 -// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
2.656 -// typedef typename EAugGraph::Edge EAugEdge;
2.657 -
2.658 -// EAugGraph res_graph(*G, *flow, *capacity);
2.659 -
2.660 -// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
2.661 -// BfsIterator5<
2.662 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
2.663 -// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
2.664 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
2.665 -
2.666 -// bfs.pushAndSetReached(s);
2.667 -
2.668 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
2.669 -// NodeMap<int>& dist=res_graph.dist;
2.670 -
2.671 -// while ( !bfs.finished() ) {
2.672 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
2.673 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.674 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.675 -// }
2.676 -// ++bfs;
2.677 -// } //computing distances from s in the residual graph
2.678 -
2.679 -// bool __augment=true;
2.680 -
2.681 -// while (__augment) {
2.682 -
2.683 -// __augment=false;
2.684 -// //computing blocking flow with dfs
2.685 -// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
2.686 -// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
2.687 -// dfs(res_graph);
2.688 -// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
2.689 -// pred.set(s, EAugEdge(INVALID));
2.690 -// //invalid iterators for sources
2.691 -
2.692 -// typename EAugGraph::NodeMap<Number> free(res_graph);
2.693 -
2.694 -// dfs.pushAndSetReached(s);
2.695 -// while (!dfs.finished()) {
2.696 -// ++dfs;
2.697 -// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
2.698 -// if (dfs.isBNodeNewlyReached()) {
2.699 -
2.700 -// typename EAugGraph::Node v=res_graph.aNode(dfs);
2.701 -// typename EAugGraph::Node w=res_graph.bNode(dfs);
2.702 -
2.703 -// pred.set(w, EAugOutEdgeIt(dfs));
2.704 -// if (res_graph.valid(pred.get(v))) {
2.705 -// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
2.706 -// } else {
2.707 -// free.set(w, res_graph.free(dfs));
2.708 -// }
2.709 -
2.710 -// if (w==t) {
2.711 -// __augment=true;
2.712 -// _augment=true;
2.713 -// break;
2.714 -// }
2.715 -// } else {
2.716 -// res_graph.erase(dfs);
2.717 -// }
2.718 -// }
2.719 -
2.720 -// }
2.721 -
2.722 -// if (__augment) {
2.723 -// typename EAugGraph::Node n=t;
2.724 -// Number augment_value=free.get(t);
2.725 -// while (res_graph.valid(pred.get(n))) {
2.726 -// EAugEdge e=pred.get(n);
2.727 -// res_graph.augment(e, augment_value);
2.728 -// n=res_graph.tail(e);
2.729 -// if (res_graph.free(e)==0)
2.730 -// res_graph.erase(e);
2.731 -// }
2.732 -// }
2.733 -
2.734 -// }
2.735 -
2.736 -// return _augment;
2.737 -// }
2.738 -
2.739 - void run() {
2.740 - //int num_of_augmentations=0;
2.741 - while (augmentOnShortestPath()) {
2.742 - //while (augmentOnBlockingFlow<MutableGraph>()) {
2.743 - //std::cout << ++num_of_augmentations << " ";
2.744 - //std::cout<<std::endl;
2.745 - }
2.746 - }
2.747 -
2.748 - template<typename MutableGraph> void run() {
2.749 - //int num_of_augmentations=0;
2.750 - //while (augmentOnShortestPath()) {
2.751 - while (augmentOnBlockingFlow<MutableGraph>()) {
2.752 - //std::cout << ++num_of_augmentations << " ";
2.753 - //std::cout<<std::endl;
2.754 - }
2.755 - }
2.756 -
2.757 - Number flowValue() {
2.758 - Number a=0;
2.759 - OutEdgeIt e;
2.760 - for(gw.first(e, s); gw.valid(e); gw.next(e)) {
2.761 - a+=flow->get(e);
2.762 - }
2.763 - return a;
2.764 - }
2.765 -
2.766 - };
2.767 -
2.768 -
2.769 -// template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.770 -// class MaxMatching {
2.771 -// public:
2.772 -// typedef typename Graph::Node Node;
2.773 -// typedef typename Graph::NodeIt NodeIt;
2.774 -// typedef typename Graph::Edge Edge;
2.775 -// typedef typename Graph::EdgeIt EdgeIt;
2.776 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
2.777 -// typedef typename Graph::InEdgeIt InEdgeIt;
2.778 -
2.779 -// typedef typename Graph::NodeMap<bool> SMap;
2.780 -// typedef typename Graph::NodeMap<bool> TMap;
2.781 -// private:
2.782 -// const Graph* G;
2.783 -// SMap* S;
2.784 -// TMap* T;
2.785 -// //Node s;
2.786 -// //Node t;
2.787 -// FlowMap* flow;
2.788 -// const CapacityMap* capacity;
2.789 -// typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
2.790 -// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
2.791 -// typedef typename AugGraph::Edge AugEdge;
2.792 -// typename Graph::NodeMap<int> used; //0
2.793 -
2.794 -// public:
2.795 -// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
2.796 -// G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
2.797 -// bool augmentOnShortestPath() {
2.798 -// AugGraph res_graph(*G, *flow, *capacity);
2.799 -// bool _augment=false;
2.800 -
2.801 -// typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.802 -// BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
2.803 -// typename AugGraph::NodeMap<AugEdge> pred(res_graph);
2.804 -// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
2.805 -// if ((S->get(s)) && (used.get(s)<1) ) {
2.806 -// //Number u=0;
2.807 -// //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
2.808 -// //u+=flow->get(e);
2.809 -// //if (u<1) {
2.810 -// bfs.pushAndSetReached(s);
2.811 -// pred.set(s, AugEdge(INVALID));
2.812 -// //}
2.813 -// }
2.814 -// }
2.815 -
2.816 -// typename AugGraph::NodeMap<Number> free(res_graph);
2.817 -
2.818 -// Node n;
2.819 -// //searching for augmenting path
2.820 -// while ( !bfs.finished() ) {
2.821 -// AugOutEdgeIt e=bfs;
2.822 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.823 -// Node v=res_graph.tail(e);
2.824 -// Node w=res_graph.head(e);
2.825 -// pred.set(w, e);
2.826 -// if (res_graph.valid(pred.get(v))) {
2.827 -// free.set(w, std::min(free.get(v), res_graph.free(e)));
2.828 -// } else {
2.829 -// free.set(w, res_graph.free(e));
2.830 -// }
2.831 -// n=res_graph.head(e);
2.832 -// if (T->get(n) && (used.get(n)<1) ) {
2.833 -// //Number u=0;
2.834 -// //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
2.835 -// //u+=flow->get(f);
2.836 -// //if (u<1) {
2.837 -// _augment=true;
2.838 -// break;
2.839 -// //}
2.840 -// }
2.841 -// }
2.842 -
2.843 -// ++bfs;
2.844 -// } //end of searching augmenting path
2.845 -
2.846 -// if (_augment) {
2.847 -// //Node n=t;
2.848 -// used.set(n, 1); //mind2 vegen jav
2.849 -// Number augment_value=free.get(n);
2.850 -// while (res_graph.valid(pred.get(n))) {
2.851 -// AugEdge e=pred.get(n);
2.852 -// res_graph.augment(e, augment_value);
2.853 -// n=res_graph.tail(e);
2.854 -// }
2.855 -// used.set(n, 1); //mind2 vegen jav
2.856 -// }
2.857 -
2.858 -// return _augment;
2.859 -// }
2.860 -
2.861 -// // template<typename MutableGraph> bool augmentOnBlockingFlow() {
2.862 -// // bool _augment=false;
2.863 -
2.864 -// // AugGraph res_graph(*G, *flow, *capacity);
2.865 -
2.866 -// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.867 -// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
2.868 -
2.869 -
2.870 -
2.871 -
2.872 -
2.873 -// // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
2.874 -// // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
2.875 -// // if (S->get(s)) {
2.876 -// // Number u=0;
2.877 -// // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
2.878 -// // u+=flow->get(e);
2.879 -// // if (u<1) {
2.880 -// // bfs.pushAndSetReached(s);
2.881 -// // //pred.set(s, AugEdge(INVALID));
2.882 -// // }
2.883 -// // }
2.884 -// // }
2.885 -
2.886 -
2.887 -
2.888 -
2.889 -// // //bfs.pushAndSetReached(s);
2.890 -// // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
2.891 -// // while ( !bfs.finished() ) {
2.892 -// // AugOutEdgeIt e=bfs;
2.893 -// // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.894 -// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.895 -// // }
2.896 -
2.897 -// // ++bfs;
2.898 -// // } //computing distances from s in the residual graph
2.899 -
2.900 -// // MutableGraph F;
2.901 -// // typename AugGraph::NodeMap<typename MutableGraph::Node>
2.902 -// // res_graph_to_F(res_graph);
2.903 -// // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
2.904 -// // res_graph_to_F.set(n, F.addNode());
2.905 -// // }
2.906 -
2.907 -// // typename MutableGraph::Node sF=res_graph_to_F.get(s);
2.908 -// // typename MutableGraph::Node tF=res_graph_to_F.get(t);
2.909 -
2.910 -// // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
2.911 -// // typename MutableGraph::EdgeMap<Number> residual_capacity(F);
2.912 -
2.913 -// // //Making F to the graph containing the edges of the residual graph
2.914 -// // //which are in some shortest paths
2.915 -// // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
2.916 -// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
2.917 -// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
2.918 -// // original_edge.update();
2.919 -// // original_edge.set(f, e);
2.920 -// // residual_capacity.update();
2.921 -// // residual_capacity.set(f, res_graph.free(e));
2.922 -// // }
2.923 -// // }
2.924 -
2.925 -// // bool __augment=true;
2.926 -
2.927 -// // while (__augment) {
2.928 -// // __augment=false;
2.929 -// // //computing blocking flow with dfs
2.930 -// // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
2.931 -// // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
2.932 -// // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
2.933 -// // pred.set(sF, typename MutableGraph::Edge(INVALID));
2.934 -// // //invalid iterators for sources
2.935 -
2.936 -// // typename MutableGraph::NodeMap<Number> free(F);
2.937 -
2.938 -// // dfs.pushAndSetReached(sF);
2.939 -// // while (!dfs.finished()) {
2.940 -// // ++dfs;
2.941 -// // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
2.942 -// // if (dfs.isBNodeNewlyReached()) {
2.943 -// // typename MutableGraph::Node v=F.aNode(dfs);
2.944 -// // typename MutableGraph::Node w=F.bNode(dfs);
2.945 -// // pred.set(w, dfs);
2.946 -// // if (F.valid(pred.get(v))) {
2.947 -// // free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
2.948 -// // } else {
2.949 -// // free.set(w, residual_capacity.get(dfs));
2.950 -// // }
2.951 -// // if (w==tF) {
2.952 -// // __augment=true;
2.953 -// // _augment=true;
2.954 -// // break;
2.955 -// // }
2.956 -
2.957 -// // } else {
2.958 -// // F.erase(typename MutableGraph::OutEdgeIt(dfs));
2.959 -// // }
2.960 -// // }
2.961 -// // }
2.962 -
2.963 -// // if (__augment) {
2.964 -// // typename MutableGraph::Node n=tF;
2.965 -// // Number augment_value=free.get(tF);
2.966 -// // while (F.valid(pred.get(n))) {
2.967 -// // typename MutableGraph::Edge e=pred.get(n);
2.968 -// // res_graph.augment(original_edge.get(e), augment_value);
2.969 -// // n=F.tail(e);
2.970 -// // if (residual_capacity.get(e)==augment_value)
2.971 -// // F.erase(e);
2.972 -// // else
2.973 -// // residual_capacity.set(e, residual_capacity.get(e)-augment_value);
2.974 -// // }
2.975 -// // }
2.976 -
2.977 -// // }
2.978 -
2.979 -// // return _augment;
2.980 -// // }
2.981 -// bool augmentOnBlockingFlow2() {
2.982 -// bool _augment=false;
2.983 -
2.984 -// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
2.985 -// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
2.986 -// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
2.987 -// typedef typename EAugGraph::Edge EAugEdge;
2.988 -
2.989 -// EAugGraph res_graph(*G, *flow, *capacity);
2.990 -
2.991 -// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
2.992 -// BfsIterator5<
2.993 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
2.994 -// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
2.995 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
2.996 -
2.997 -
2.998 -// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
2.999 -// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
2.1000 -// if (S->get(s)) {
2.1001 -// Number u=0;
2.1002 -// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
2.1003 -// u+=flow->get(e);
2.1004 -// if (u<1) {
2.1005 -// bfs.pushAndSetReached(s);
2.1006 -// //pred.set(s, AugEdge(INVALID));
2.1007 -// }
2.1008 -// }
2.1009 -// }
2.1010 -
2.1011 -
2.1012 -// //bfs.pushAndSetReached(s);
2.1013 -
2.1014 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
2.1015 -// NodeMap<int>& dist=res_graph.dist;
2.1016 -
2.1017 -// while ( !bfs.finished() ) {
2.1018 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
2.1019 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.1020 -// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.1021 -// }
2.1022 -// ++bfs;
2.1023 -// } //computing distances from s in the residual graph
2.1024 -
2.1025 -// bool __augment=true;
2.1026 -
2.1027 -// while (__augment) {
2.1028 -
2.1029 -// __augment=false;
2.1030 -// //computing blocking flow with dfs
2.1031 -// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
2.1032 -// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
2.1033 -// dfs(res_graph);
2.1034 -// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
2.1035 -// //pred.set(s, EAugEdge(INVALID));
2.1036 -// //invalid iterators for sources
2.1037 -
2.1038 -// typename EAugGraph::NodeMap<Number> free(res_graph);
2.1039 -
2.1040 -
2.1041 -// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
2.1042 -// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
2.1043 -// if (S->get(s)) {
2.1044 -// Number u=0;
2.1045 -// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
2.1046 -// u+=flow->get(e);
2.1047 -// if (u<1) {
2.1048 -// dfs.pushAndSetReached(s);
2.1049 -// //pred.set(s, AugEdge(INVALID));
2.1050 -// }
2.1051 -// }
2.1052 -// }
2.1053 -
2.1054 -
2.1055 -
2.1056 -// //dfs.pushAndSetReached(s);
2.1057 -// typename EAugGraph::Node n;
2.1058 -// while (!dfs.finished()) {
2.1059 -// ++dfs;
2.1060 -// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
2.1061 -// if (dfs.isBNodeNewlyReached()) {
2.1062 -
2.1063 -// typename EAugGraph::Node v=res_graph.aNode(dfs);
2.1064 -// typename EAugGraph::Node w=res_graph.bNode(dfs);
2.1065 -
2.1066 -// pred.set(w, EAugOutEdgeIt(dfs));
2.1067 -// if (res_graph.valid(pred.get(v))) {
2.1068 -// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
2.1069 -// } else {
2.1070 -// free.set(w, res_graph.free(dfs));
2.1071 -// }
2.1072 -
2.1073 -// n=w;
2.1074 -// if (T->get(w)) {
2.1075 -// Number u=0;
2.1076 -// for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
2.1077 -// u+=flow->get(f);
2.1078 -// if (u<1) {
2.1079 -// __augment=true;
2.1080 -// _augment=true;
2.1081 -// break;
2.1082 -// }
2.1083 -// }
2.1084 -// } else {
2.1085 -// res_graph.erase(dfs);
2.1086 -// }
2.1087 -// }
2.1088 -
2.1089 -// }
2.1090 -
2.1091 -// if (__augment) {
2.1092 -// // typename EAugGraph::Node n=t;
2.1093 -// Number augment_value=free.get(n);
2.1094 -// while (res_graph.valid(pred.get(n))) {
2.1095 -// EAugEdge e=pred.get(n);
2.1096 -// res_graph.augment(e, augment_value);
2.1097 -// n=res_graph.tail(e);
2.1098 -// if (res_graph.free(e)==0)
2.1099 -// res_graph.erase(e);
2.1100 -// }
2.1101 -// }
2.1102 -
2.1103 -// }
2.1104 -
2.1105 -// return _augment;
2.1106 -// }
2.1107 -// void run() {
2.1108 -// //int num_of_augmentations=0;
2.1109 -// while (augmentOnShortestPath()) {
2.1110 -// //while (augmentOnBlockingFlow<MutableGraph>()) {
2.1111 -// //std::cout << ++num_of_augmentations << " ";
2.1112 -// //std::cout<<std::endl;
2.1113 -// }
2.1114 -// }
2.1115 -// // template<typename MutableGraph> void run() {
2.1116 -// // //int num_of_augmentations=0;
2.1117 -// // //while (augmentOnShortestPath()) {
2.1118 -// // while (augmentOnBlockingFlow<MutableGraph>()) {
2.1119 -// // //std::cout << ++num_of_augmentations << " ";
2.1120 -// // //std::cout<<std::endl;
2.1121 -// // }
2.1122 -// // }
2.1123 -// Number flowValue() {
2.1124 -// Number a=0;
2.1125 -// EdgeIt e;
2.1126 -// for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
2.1127 -// a+=flow->get(e);
2.1128 -// }
2.1129 -// return a;
2.1130 -// }
2.1131 -// };
2.1132 -
2.1133 -
2.1134 -
2.1135 -
2.1136 -
2.1137 -
2.1138 -// // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.1139 -// // class MaxFlow2 {
2.1140 -// // public:
2.1141 -// // typedef typename Graph::Node Node;
2.1142 -// // typedef typename Graph::Edge Edge;
2.1143 -// // typedef typename Graph::EdgeIt EdgeIt;
2.1144 -// // typedef typename Graph::OutEdgeIt OutEdgeIt;
2.1145 -// // typedef typename Graph::InEdgeIt InEdgeIt;
2.1146 -// // private:
2.1147 -// // const Graph& G;
2.1148 -// // std::list<Node>& S;
2.1149 -// // std::list<Node>& T;
2.1150 -// // FlowMap& flow;
2.1151 -// // const CapacityMap& capacity;
2.1152 -// // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
2.1153 -// // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
2.1154 -// // typedef typename AugGraph::Edge AugEdge;
2.1155 -// // typename Graph::NodeMap<bool> SMap;
2.1156 -// // typename Graph::NodeMap<bool> TMap;
2.1157 -// // public:
2.1158 -// // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
2.1159 -// // for(typename std::list<Node>::const_iterator i=S.begin();
2.1160 -// // i!=S.end(); ++i) {
2.1161 -// // SMap.set(*i, true);
2.1162 -// // }
2.1163 -// // for (typename std::list<Node>::const_iterator i=T.begin();
2.1164 -// // i!=T.end(); ++i) {
2.1165 -// // TMap.set(*i, true);
2.1166 -// // }
2.1167 -// // }
2.1168 -// // bool augment() {
2.1169 -// // AugGraph res_graph(G, flow, capacity);
2.1170 -// // bool _augment=false;
2.1171 -// // Node reached_t_node;
2.1172 -
2.1173 -// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.1174 -// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
2.1175 -// // for(typename std::list<Node>::const_iterator i=S.begin();
2.1176 -// // i!=S.end(); ++i) {
2.1177 -// // bfs.pushAndSetReached(*i);
2.1178 -// // }
2.1179 -// // //bfs.pushAndSetReached(s);
2.1180 -
2.1181 -// // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
2.1182 -// // //filled up with invalid iterators
2.1183 -
2.1184 -// // typename AugGraph::NodeMap<Number> free(res_graph);
2.1185 -
2.1186 -// // //searching for augmenting path
2.1187 -// // while ( !bfs.finished() ) {
2.1188 -// // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
2.1189 -// // if (e.valid() && bfs.isBNodeNewlyReached()) {
2.1190 -// // Node v=res_graph.tail(e);
2.1191 -// // Node w=res_graph.head(e);
2.1192 -// // pred.set(w, e);
2.1193 -// // if (pred.get(v).valid()) {
2.1194 -// // free.set(w, std::min(free.get(v), e.free()));
2.1195 -// // } else {
2.1196 -// // free.set(w, e.free());
2.1197 -// // }
2.1198 -// // if (TMap.get(res_graph.head(e))) {
2.1199 -// // _augment=true;
2.1200 -// // reached_t_node=res_graph.head(e);
2.1201 -// // break;
2.1202 -// // }
2.1203 -// // }
2.1204 -
2.1205 -// // ++bfs;
2.1206 -// // } //end of searching augmenting path
2.1207 -
2.1208 -// // if (_augment) {
2.1209 -// // Node n=reached_t_node;
2.1210 -// // Number augment_value=free.get(reached_t_node);
2.1211 -// // while (pred.get(n).valid()) {
2.1212 -// // AugEdge e=pred.get(n);
2.1213 -// // e.augment(augment_value);
2.1214 -// // n=res_graph.tail(e);
2.1215 -// // }
2.1216 -// // }
2.1217 -
2.1218 -// // return _augment;
2.1219 -// // }
2.1220 -// // void run() {
2.1221 -// // while (augment()) { }
2.1222 -// // }
2.1223 -// // Number flowValue() {
2.1224 -// // Number a=0;
2.1225 -// // for(typename std::list<Node>::const_iterator i=S.begin();
2.1226 -// // i!=S.end(); ++i) {
2.1227 -// // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
2.1228 -// // a+=flow.get(e);
2.1229 -// // }
2.1230 -// // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
2.1231 -// // a-=flow.get(e);
2.1232 -// // }
2.1233 -// // }
2.1234 -// // return a;
2.1235 -// // }
2.1236 -// // };
2.1237 -
2.1238 -
2.1239 -} // namespace hugo
2.1240 -
2.1241 -#endif //HUGO_EDMONDS_KARP_H
3.1 --- a/src/work/iterator_bfs_demo.cc Mon Apr 05 14:56:41 2004 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,322 +0,0 @@
3.4 -// -*- c++ -*-
3.5 -#include <iostream>
3.6 -#include <vector>
3.7 -#include <string>
3.8 -
3.9 -#include <list_graph.h>
3.10 -#include <smart_graph.h>
3.11 -#include <bfs_iterator.h>
3.12 -#include <graph_wrapper.h>
3.13 -
3.14 -using namespace hugo;
3.15 -using std::cout;
3.16 -using std::endl;
3.17 -using std::string;
3.18 -
3.19 -template <typename Graph, typename NodeNameMap>
3.20 -class EdgeNameMap {
3.21 - Graph& graph;
3.22 - NodeNameMap& node_name_map;
3.23 -public:
3.24 - EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
3.25 - graph(_graph), node_name_map(_node_name_map) { }
3.26 - string get(typename Graph::Edge e) const {
3.27 - return
3.28 - (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
3.29 - }
3.30 -};
3.31 -
3.32 -int main (int, char*[])
3.33 -{
3.34 - //typedef SmartGraph Graph;
3.35 - typedef ListGraph Graph;
3.36 -
3.37 - typedef Graph::Node Node;
3.38 - typedef Graph::Edge Edge;
3.39 -
3.40 - Graph G;
3.41 -
3.42 - Node s=G.addNode();
3.43 - Node v1=G.addNode();
3.44 - Node v2=G.addNode();
3.45 - Node v3=G.addNode();
3.46 - Node v4=G.addNode();
3.47 - Node t=G.addNode();
3.48 -
3.49 - Graph::NodeMap<string> node_name(G);
3.50 - node_name.set(s, "s");
3.51 - node_name.set(v1, "v1");
3.52 - node_name.set(v2, "v2");
3.53 - node_name.set(v3, "v3");
3.54 - node_name.set(v4, "v4");
3.55 - node_name.set(t, "t");
3.56 -
3.57 - G.addEdge(s, v1);
3.58 - G.addEdge(s, v2);
3.59 - G.addEdge(v1, v2);
3.60 - G.addEdge(v2, v1);
3.61 - G.addEdge(v1, v3);
3.62 - G.addEdge(v3, v2);
3.63 - G.addEdge(v2, v4);
3.64 - G.addEdge(v4, v3);
3.65 - G.addEdge(v3, t);
3.66 - G.addEdge(v4, t);
3.67 -
3.68 - cout << " /--> -------------> "<< endl;
3.69 - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
3.70 - cout << " / | | / /-> \\ "<< endl;
3.71 - cout << " / | | / | ^ \\ "<< endl;
3.72 - cout << "s | | / | | \\-> t "<< endl;
3.73 - cout << " \\ | | / | | /-> "<< endl;
3.74 - cout << " \\ | --/ / | | / "<< endl;
3.75 - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
3.76 - cout << " \\--> -------------> "<< endl;
3.77 -
3.78 -// typedef TrivGraphWrapper<const Graph> CGW;
3.79 -// CGW gw(G);
3.80 -
3.81 -// cout << "bfs and dfs demo on the directed graph" << endl;
3.82 -// for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) {
3.83 -// cout << n << ": ";
3.84 -// cout << "out edges: ";
3.85 -// for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
3.86 -// cout << e << " ";
3.87 -// cout << "in edges: ";
3.88 -// for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e)
3.89 -// cout << e << " ";
3.90 -// cout << endl;
3.91 -// }
3.92 -
3.93 - {
3.94 - typedef TrivGraphWrapper<const Graph> GW;
3.95 - GW gw(G);
3.96 -
3.97 - EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
3.98 -
3.99 - cout << "bfs and dfs iterator demo on the directed graph" << endl;
3.100 - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
3.101 - cout << node_name.get(n) << ": ";
3.102 - cout << "out edges: ";
3.103 - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
3.104 - cout << edge_name.get(e) << " ";
3.105 - cout << "in edges: ";
3.106 - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
3.107 - cout << edge_name.get(e) << " ";
3.108 - cout << endl;
3.109 - }
3.110 -
3.111 - cout << "bfs from s ..." << endl;
3.112 - BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
3.113 - bfs.pushAndSetReached(s);
3.114 - while (!bfs.finished()) {
3.115 - //cout << "edge: ";
3.116 - if (gw.valid(bfs)) {
3.117 - cout << edge_name.get(bfs) << /*endl*/", " <<
3.118 - node_name.get(gw.aNode(bfs)) <<
3.119 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.120 - node_name.get(gw.bNode(bfs)) <<
3.121 - (bfs.isBNodeNewlyReached() ? ": is newly reached." :
3.122 - ": is not newly reached.");
3.123 - } else {
3.124 - cout << "invalid" << /*endl*/", " <<
3.125 - node_name.get(bfs.aNode()) <<
3.126 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.127 -
3.128 - "invalid.";
3.129 - }
3.130 - cout << endl;
3.131 - ++bfs;
3.132 - }
3.133 -
3.134 - cout << " /--> -------------> "<< endl;
3.135 - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
3.136 - cout << " / | | / /-> \\ "<< endl;
3.137 - cout << " / | | / | ^ \\ "<< endl;
3.138 - cout << "s | | / | | \\-> t "<< endl;
3.139 - cout << " \\ | | / | | /-> "<< endl;
3.140 - cout << " \\ | --/ / | | / "<< endl;
3.141 - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
3.142 - cout << " \\--> -------------> "<< endl;
3.143 -
3.144 - cout << "dfs from s ..." << endl;
3.145 - DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
3.146 - dfs.pushAndSetReached(s);
3.147 - while (!dfs.finished()) {
3.148 - ++dfs;
3.149 - //cout << "edge: ";
3.150 - if (gw.valid(dfs)) {
3.151 - cout << edge_name.get(dfs) << /*endl*/", " <<
3.152 - node_name.get(gw.aNode(dfs)) <<
3.153 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.154 - node_name.get(gw.bNode(dfs)) <<
3.155 - (dfs.isBNodeNewlyReached() ? ": is newly reached." :
3.156 - ": is not newly reached.");
3.157 - } else {
3.158 - cout << "invalid" << /*endl*/", " <<
3.159 - node_name.get(dfs.aNode()) <<
3.160 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.161 -
3.162 - "invalid.";
3.163 - }
3.164 - cout << endl;
3.165 - }
3.166 - }
3.167 -
3.168 -
3.169 - {
3.170 - typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW;
3.171 - GW gw(G);
3.172 -
3.173 - EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
3.174 -
3.175 - cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
3.176 - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
3.177 - cout << node_name.get(n) << ": ";
3.178 - cout << "out edges: ";
3.179 - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
3.180 - cout << edge_name.get(e) << " ";
3.181 - cout << "in edges: ";
3.182 - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
3.183 - cout << edge_name.get(e) << " ";
3.184 - cout << endl;
3.185 - }
3.186 -
3.187 - cout << "bfs from t ..." << endl;
3.188 - BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
3.189 - bfs.pushAndSetReached(t);
3.190 - while (!bfs.finished()) {
3.191 - //cout << "edge: ";
3.192 - if (gw.valid(bfs)) {
3.193 - cout << edge_name.get(bfs) << /*endl*/", " <<
3.194 - node_name.get(gw.aNode(bfs)) <<
3.195 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.196 - node_name.get(gw.bNode(bfs)) <<
3.197 - (bfs.isBNodeNewlyReached() ? ": is newly reached." :
3.198 - ": is not newly reached.");
3.199 - } else {
3.200 - cout << "invalid" << /*endl*/", " <<
3.201 - node_name.get(bfs.aNode()) <<
3.202 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.203 -
3.204 - "invalid.";
3.205 - }
3.206 - cout << endl;
3.207 - ++bfs;
3.208 - }
3.209 -
3.210 - cout << " /--> -------------> "<< endl;
3.211 - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
3.212 - cout << " / | | / /-> \\ "<< endl;
3.213 - cout << " / | | / | ^ \\ "<< endl;
3.214 - cout << "s | | / | | \\-> t "<< endl;
3.215 - cout << " \\ | | / | | /-> "<< endl;
3.216 - cout << " \\ | --/ / | | / "<< endl;
3.217 - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
3.218 - cout << " \\--> -------------> "<< endl;
3.219 -
3.220 - cout << "dfs from t ..." << endl;
3.221 - DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
3.222 - dfs.pushAndSetReached(t);
3.223 - while (!dfs.finished()) {
3.224 - ++dfs;
3.225 - //cout << "edge: ";
3.226 - if (gw.valid(dfs)) {
3.227 - cout << edge_name.get(dfs) << /*endl*/", " <<
3.228 - node_name.get(gw.aNode(dfs)) <<
3.229 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.230 - node_name.get(gw.bNode(dfs)) <<
3.231 - (dfs.isBNodeNewlyReached() ? ": is newly reached." :
3.232 - ": is not newly reached.");
3.233 - } else {
3.234 - cout << "invalid" << /*endl*/", " <<
3.235 - node_name.get(dfs.aNode()) <<
3.236 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.237 -
3.238 - "invalid.";
3.239 - }
3.240 - cout << endl;
3.241 - }
3.242 - }
3.243 -
3.244 - {
3.245 - //typedef UndirGraphWrapper<const Graph> GW;
3.246 - typedef UndirGraphWrapper<const TrivGraphWrapper<const Graph> > GW;
3.247 - GW gw(G);
3.248 -
3.249 - EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
3.250 -
3.251 - cout << "bfs and dfs iterator demo on the undirected graph" << endl;
3.252 - for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
3.253 - cout << node_name.get(n) << ": ";
3.254 - cout << "out edges: ";
3.255 - for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
3.256 - cout << edge_name.get(e) << " ";
3.257 - cout << "in edges: ";
3.258 - for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
3.259 - cout << edge_name.get(e) << " ";
3.260 - cout << endl;
3.261 - }
3.262 -// for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
3.263 -// cout << edge_name.get(e) << " ";
3.264 -// }
3.265 -// cout << endl;
3.266 -
3.267 - cout << "bfs from t ..." << endl;
3.268 - BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
3.269 - bfs.pushAndSetReached(t);
3.270 - while (!bfs.finished()) {
3.271 - //cout << "edge: ";
3.272 - if (gw.valid(GW::OutEdgeIt(bfs))) {
3.273 - cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<
3.274 - node_name.get(gw.aNode(bfs)) <<
3.275 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.276 - node_name.get(gw.bNode(bfs)) <<
3.277 - (bfs.isBNodeNewlyReached() ? ": is newly reached." :
3.278 - ": is not newly reached.");
3.279 - } else {
3.280 - cout << "invalid" << /*endl*/", " <<
3.281 - node_name.get(bfs.aNode()) <<
3.282 - (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.283 -
3.284 - "invalid.";
3.285 - }
3.286 - cout << endl;
3.287 - ++bfs;
3.288 - }
3.289 -
3.290 - cout << " /--> -------------> "<< endl;
3.291 - cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
3.292 - cout << " / | | / /-> \\ "<< endl;
3.293 - cout << " / | | / | ^ \\ "<< endl;
3.294 - cout << "s | | / | | \\-> t "<< endl;
3.295 - cout << " \\ | | / | | /-> "<< endl;
3.296 - cout << " \\ | --/ / | | / "<< endl;
3.297 - cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
3.298 - cout << " \\--> -------------> "<< endl;
3.299 -
3.300 - cout << "dfs from t ..." << endl;
3.301 - DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
3.302 - dfs.pushAndSetReached(t);
3.303 - while (!dfs.finished()) {
3.304 - ++dfs;
3.305 - //cout << "edge: ";
3.306 - if (gw.valid(GW::OutEdgeIt(dfs))) {
3.307 - cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<
3.308 - node_name.get(gw.aNode(dfs)) <<
3.309 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.310 - node_name.get(gw.bNode(dfs)) <<
3.311 - (dfs.isBNodeNewlyReached() ? ": is newly reached." :
3.312 - ": is not newly reached.");
3.313 - } else {
3.314 - cout << "invalid" << /*endl*/", " <<
3.315 - node_name.get(dfs.aNode()) <<
3.316 - (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
3.317 -
3.318 - "invalid.";
3.319 - }
3.320 - cout << endl;
3.321 - }
3.322 - }
3.323 -
3.324 - return 0;
3.325 -}
4.1 --- a/src/work/makefile Mon Apr 05 14:56:41 2004 +0000
4.2 +++ b/src/work/makefile Mon Apr 05 15:02:39 2004 +0000
4.3 @@ -23,7 +23,7 @@
4.4
4.5
4.6 .depend dep depend:
4.7 - -$(CXX) $(CXXFLAGS) -M *.cc > .depend
4.8 + -$(CXX) $(CXXFLAGS) -M $(BINARIES:=.cc) > .depend
4.9
4.10 makefile: .depend
4.11 sinclude .depend
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/marci/bfs_iterator.h Mon Apr 05 15:02:39 2004 +0000
5.3 @@ -0,0 +1,841 @@
5.4 +// -*- c++ -*-
5.5 +#ifndef HUGO_BFS_ITERATOR_H
5.6 +#define HUGO_BFS_ITERATOR_H
5.7 +
5.8 +#include <queue>
5.9 +#include <stack>
5.10 +#include <utility>
5.11 +#include <graph_wrapper.h>
5.12 +
5.13 +namespace hugo {
5.14 +
5.15 +// template <typename Graph>
5.16 +// struct bfs {
5.17 +// typedef typename Graph::Node Node;
5.18 +// typedef typename Graph::Edge Edge;
5.19 +// typedef typename Graph::NodeIt NodeIt;
5.20 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
5.21 +// Graph& G;
5.22 +// Node s;
5.23 +// typename Graph::NodeMap<bool> reached;
5.24 +// typename Graph::NodeMap<Edge> pred;
5.25 +// typename Graph::NodeMap<int> dist;
5.26 +// std::queue<Node> bfs_queue;
5.27 +// bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
5.28 +// bfs_queue.push(s);
5.29 +// for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)
5.30 +// reached.set(i, false);
5.31 +// reached.set(s, true);
5.32 +// dist.set(s, 0);
5.33 +// }
5.34 +
5.35 +// void run() {
5.36 +// while (!bfs_queue.empty()) {
5.37 +// Node v=bfs_queue.front();
5.38 +// OutEdgeIt e=G.template first<OutEdgeIt>(v);
5.39 +// bfs_queue.pop();
5.40 +// for( ; e.valid(); ++e) {
5.41 +// Node w=G.bNode(e);
5.42 +// std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
5.43 +// if (!reached.get(w)) {
5.44 +// std::cout << G.id(w) << " is newly reached :-)" << std::endl;
5.45 +// bfs_queue.push(w);
5.46 +// dist.set(w, dist.get(v)+1);
5.47 +// pred.set(w, e);
5.48 +// reached.set(w, true);
5.49 +// } else {
5.50 +// std::cout << G.id(w) << " is already reached" << std::endl;
5.51 +// }
5.52 +// }
5.53 +// }
5.54 +// }
5.55 +// };
5.56 +
5.57 +// template <typename Graph>
5.58 +// struct bfs_visitor {
5.59 +// typedef typename Graph::Node Node;
5.60 +// typedef typename Graph::Edge Edge;
5.61 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
5.62 +// Graph& G;
5.63 +// bfs_visitor(Graph& _G) : G(_G) { }
5.64 +// void at_previously_reached(OutEdgeIt& e) {
5.65 +// //Node v=G.aNode(e);
5.66 +// Node w=G.bNode(e);
5.67 +// std::cout << G.id(w) << " is already reached" << std::endl;
5.68 +// }
5.69 +// void at_newly_reached(OutEdgeIt& e) {
5.70 +// //Node v=G.aNode(e);
5.71 +// Node w=G.bNode(e);
5.72 +// std::cout << G.id(w) << " is newly reached :-)" << std::endl;
5.73 +// }
5.74 +// };
5.75 +
5.76 +// template <typename Graph, typename ReachedMap, typename visitor_type>
5.77 +// struct bfs_iterator {
5.78 +// typedef typename Graph::Node Node;
5.79 +// typedef typename Graph::Edge Edge;
5.80 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
5.81 +// Graph& G;
5.82 +// std::queue<OutEdgeIt>& bfs_queue;
5.83 +// ReachedMap& reached;
5.84 +// visitor_type& visitor;
5.85 +// void process() {
5.86 +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
5.87 +// if (bfs_queue.empty()) return;
5.88 +// OutEdgeIt e=bfs_queue.front();
5.89 +// //Node v=G.aNode(e);
5.90 +// Node w=G.bNode(e);
5.91 +// if (!reached.get(w)) {
5.92 +// visitor.at_newly_reached(e);
5.93 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
5.94 +// reached.set(w, true);
5.95 +// } else {
5.96 +// visitor.at_previously_reached(e);
5.97 +// }
5.98 +// }
5.99 +// bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
5.100 +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
5.101 +// valid();
5.102 +// }
5.103 +// bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
5.104 +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
5.105 +// //if (bfs_queue.empty()) return *this;
5.106 +// if (!valid()) return *this;
5.107 +// ++(bfs_queue.front());
5.108 +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
5.109 +// valid();
5.110 +// return *this;
5.111 +// }
5.112 +// //void next() {
5.113 +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
5.114 +// // if (bfs_queue.empty()) return;
5.115 +// // ++(bfs_queue.front());
5.116 +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
5.117 +// //}
5.118 +// bool valid() {
5.119 +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
5.120 +// if (bfs_queue.empty()) return false; else return true;
5.121 +// }
5.122 +// //bool finished() {
5.123 +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
5.124 +// // if (bfs_queue.empty()) return true; else return false;
5.125 +// //}
5.126 +// operator Edge () { return bfs_queue.front(); }
5.127 +
5.128 +// };
5.129 +
5.130 +// template <typename Graph, typename ReachedMap>
5.131 +// struct bfs_iterator1 {
5.132 +// typedef typename Graph::Node Node;
5.133 +// typedef typename Graph::Edge Edge;
5.134 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
5.135 +// Graph& G;
5.136 +// std::queue<OutEdgeIt>& bfs_queue;
5.137 +// ReachedMap& reached;
5.138 +// bool _newly_reached;
5.139 +// bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
5.140 +// valid();
5.141 +// if (!bfs_queue.empty() && bfs_queue.front().valid()) {
5.142 +// OutEdgeIt e=bfs_queue.front();
5.143 +// Node w=G.bNode(e);
5.144 +// if (!reached.get(w)) {
5.145 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
5.146 +// reached.set(w, true);
5.147 +// _newly_reached=true;
5.148 +// } else {
5.149 +// _newly_reached=false;
5.150 +// }
5.151 +// }
5.152 +// }
5.153 +// bfs_iterator1<Graph, ReachedMap>& operator++() {
5.154 +// if (!valid()) return *this;
5.155 +// ++(bfs_queue.front());
5.156 +// valid();
5.157 +// if (!bfs_queue.empty() && bfs_queue.front().valid()) {
5.158 +// OutEdgeIt e=bfs_queue.front();
5.159 +// Node w=G.bNode(e);
5.160 +// if (!reached.get(w)) {
5.161 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
5.162 +// reached.set(w, true);
5.163 +// _newly_reached=true;
5.164 +// } else {
5.165 +// _newly_reached=false;
5.166 +// }
5.167 +// }
5.168 +// return *this;
5.169 +// }
5.170 +// bool valid() {
5.171 +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
5.172 +// if (bfs_queue.empty()) return false; else return true;
5.173 +// }
5.174 +// operator OutEdgeIt() { return bfs_queue.front(); }
5.175 +// //ize
5.176 +// bool newly_reached() { return _newly_reached; }
5.177 +
5.178 +// };
5.179 +
5.180 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
5.181 +// struct BfsIterator {
5.182 +// typedef typename Graph::Node Node;
5.183 +// Graph& G;
5.184 +// std::queue<OutEdgeIt>& bfs_queue;
5.185 +// ReachedMap& reached;
5.186 +// bool b_node_newly_reached;
5.187 +// OutEdgeIt actual_edge;
5.188 +// BfsIterator(Graph& _G,
5.189 +// std::queue<OutEdgeIt>& _bfs_queue,
5.190 +// ReachedMap& _reached) :
5.191 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
5.192 +// actual_edge=bfs_queue.front();
5.193 +// if (actual_edge.valid()) {
5.194 +// Node w=G.bNode(actual_edge);
5.195 +// if (!reached.get(w)) {
5.196 +// bfs_queue.push(G.firstOutEdge(w));
5.197 +// reached.set(w, true);
5.198 +// b_node_newly_reached=true;
5.199 +// } else {
5.200 +// b_node_newly_reached=false;
5.201 +// }
5.202 +// }
5.203 +// }
5.204 +// BfsIterator<Graph, OutEdgeIt, ReachedMap>&
5.205 +// operator++() {
5.206 +// if (bfs_queue.front().valid()) {
5.207 +// ++(bfs_queue.front());
5.208 +// actual_edge=bfs_queue.front();
5.209 +// if (actual_edge.valid()) {
5.210 +// Node w=G.bNode(actual_edge);
5.211 +// if (!reached.get(w)) {
5.212 +// bfs_queue.push(G.firstOutEdge(w));
5.213 +// reached.set(w, true);
5.214 +// b_node_newly_reached=true;
5.215 +// } else {
5.216 +// b_node_newly_reached=false;
5.217 +// }
5.218 +// }
5.219 +// } else {
5.220 +// bfs_queue.pop();
5.221 +// actual_edge=bfs_queue.front();
5.222 +// if (actual_edge.valid()) {
5.223 +// Node w=G.bNode(actual_edge);
5.224 +// if (!reached.get(w)) {
5.225 +// bfs_queue.push(G.firstOutEdge(w));
5.226 +// reached.set(w, true);
5.227 +// b_node_newly_reached=true;
5.228 +// } else {
5.229 +// b_node_newly_reached=false;
5.230 +// }
5.231 +// }
5.232 +// }
5.233 +// return *this;
5.234 +// }
5.235 +// bool finished() { return bfs_queue.empty(); }
5.236 +// operator OutEdgeIt () { return actual_edge; }
5.237 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
5.238 +// bool aNodeIsExamined() { return !(actual_edge.valid()); }
5.239 +// };
5.240 +
5.241 +
5.242 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
5.243 +// struct DfsIterator {
5.244 +// typedef typename Graph::Node Node;
5.245 +// Graph& G;
5.246 +// std::stack<OutEdgeIt>& bfs_queue;
5.247 +// ReachedMap& reached;
5.248 +// bool b_node_newly_reached;
5.249 +// OutEdgeIt actual_edge;
5.250 +// DfsIterator(Graph& _G,
5.251 +// std::stack<OutEdgeIt>& _bfs_queue,
5.252 +// ReachedMap& _reached) :
5.253 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
5.254 +// actual_edge=bfs_queue.top();
5.255 +// if (actual_edge.valid()) {
5.256 +// Node w=G.bNode(actual_edge);
5.257 +// if (!reached.get(w)) {
5.258 +// bfs_queue.push(G.firstOutEdge(w));
5.259 +// reached.set(w, true);
5.260 +// b_node_newly_reached=true;
5.261 +// } else {
5.262 +// ++(bfs_queue.top());
5.263 +// b_node_newly_reached=false;
5.264 +// }
5.265 +// } else {
5.266 +// bfs_queue.pop();
5.267 +// }
5.268 +// }
5.269 +// DfsIterator<Graph, OutEdgeIt, ReachedMap>&
5.270 +// operator++() {
5.271 +// actual_edge=bfs_queue.top();
5.272 +// if (actual_edge.valid()) {
5.273 +// Node w=G.bNode(actual_edge);
5.274 +// if (!reached.get(w)) {
5.275 +// bfs_queue.push(G.firstOutEdge(w));
5.276 +// reached.set(w, true);
5.277 +// b_node_newly_reached=true;
5.278 +// } else {
5.279 +// ++(bfs_queue.top());
5.280 +// b_node_newly_reached=false;
5.281 +// }
5.282 +// } else {
5.283 +// bfs_queue.pop();
5.284 +// }
5.285 +// return *this;
5.286 +// }
5.287 +// bool finished() { return bfs_queue.empty(); }
5.288 +// operator OutEdgeIt () { return actual_edge; }
5.289 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
5.290 +// bool aNodeIsExamined() { return !(actual_edge.valid()); }
5.291 +// };
5.292 +
5.293 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
5.294 +// struct BfsIterator1 {
5.295 +// typedef typename Graph::Node Node;
5.296 +// Graph& G;
5.297 +// std::queue<OutEdgeIt>& bfs_queue;
5.298 +// ReachedMap& reached;
5.299 +// bool b_node_newly_reached;
5.300 +// OutEdgeIt actual_edge;
5.301 +// BfsIterator1(Graph& _G,
5.302 +// std::queue<OutEdgeIt>& _bfs_queue,
5.303 +// ReachedMap& _reached) :
5.304 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
5.305 +// actual_edge=bfs_queue.front();
5.306 +// if (actual_edge.valid()) {
5.307 +// Node w=G.bNode(actual_edge);
5.308 +// if (!reached.get(w)) {
5.309 +// bfs_queue.push(OutEdgeIt(G, w));
5.310 +// reached.set(w, true);
5.311 +// b_node_newly_reached=true;
5.312 +// } else {
5.313 +// b_node_newly_reached=false;
5.314 +// }
5.315 +// }
5.316 +// }
5.317 +// void next() {
5.318 +// if (bfs_queue.front().valid()) {
5.319 +// ++(bfs_queue.front());
5.320 +// actual_edge=bfs_queue.front();
5.321 +// if (actual_edge.valid()) {
5.322 +// Node w=G.bNode(actual_edge);
5.323 +// if (!reached.get(w)) {
5.324 +// bfs_queue.push(OutEdgeIt(G, w));
5.325 +// reached.set(w, true);
5.326 +// b_node_newly_reached=true;
5.327 +// } else {
5.328 +// b_node_newly_reached=false;
5.329 +// }
5.330 +// }
5.331 +// } else {
5.332 +// bfs_queue.pop();
5.333 +// actual_edge=bfs_queue.front();
5.334 +// if (actual_edge.valid()) {
5.335 +// Node w=G.bNode(actual_edge);
5.336 +// if (!reached.get(w)) {
5.337 +// bfs_queue.push(OutEdgeIt(G, w));
5.338 +// reached.set(w, true);
5.339 +// b_node_newly_reached=true;
5.340 +// } else {
5.341 +// b_node_newly_reached=false;
5.342 +// }
5.343 +// }
5.344 +// }
5.345 +// //return *this;
5.346 +// }
5.347 +// bool finished() { return bfs_queue.empty(); }
5.348 +// operator OutEdgeIt () { return actual_edge; }
5.349 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
5.350 +// bool aNodeIsExamined() { return !(actual_edge.valid()); }
5.351 +// };
5.352 +
5.353 +
5.354 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
5.355 +// struct DfsIterator1 {
5.356 +// typedef typename Graph::Node Node;
5.357 +// Graph& G;
5.358 +// std::stack<OutEdgeIt>& bfs_queue;
5.359 +// ReachedMap& reached;
5.360 +// bool b_node_newly_reached;
5.361 +// OutEdgeIt actual_edge;
5.362 +// DfsIterator1(Graph& _G,
5.363 +// std::stack<OutEdgeIt>& _bfs_queue,
5.364 +// ReachedMap& _reached) :
5.365 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
5.366 +// //actual_edge=bfs_queue.top();
5.367 +// //if (actual_edge.valid()) {
5.368 +// // Node w=G.bNode(actual_edge);
5.369 +// //if (!reached.get(w)) {
5.370 +// // bfs_queue.push(OutEdgeIt(G, w));
5.371 +// // reached.set(w, true);
5.372 +// // b_node_newly_reached=true;
5.373 +// //} else {
5.374 +// // ++(bfs_queue.top());
5.375 +// // b_node_newly_reached=false;
5.376 +// //}
5.377 +// //} else {
5.378 +// // bfs_queue.pop();
5.379 +// //}
5.380 +// }
5.381 +// void next() {
5.382 +// actual_edge=bfs_queue.top();
5.383 +// if (actual_edge.valid()) {
5.384 +// Node w=G.bNode(actual_edge);
5.385 +// if (!reached.get(w)) {
5.386 +// bfs_queue.push(OutEdgeIt(G, w));
5.387 +// reached.set(w, true);
5.388 +// b_node_newly_reached=true;
5.389 +// } else {
5.390 +// ++(bfs_queue.top());
5.391 +// b_node_newly_reached=false;
5.392 +// }
5.393 +// } else {
5.394 +// bfs_queue.pop();
5.395 +// }
5.396 +// //return *this;
5.397 +// }
5.398 +// bool finished() { return bfs_queue.empty(); }
5.399 +// operator OutEdgeIt () { return actual_edge; }
5.400 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
5.401 +// bool aNodeIsLeaved() { return !(actual_edge.valid()); }
5.402 +// };
5.403 +
5.404 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
5.405 +// class BfsIterator2 {
5.406 +// typedef typename Graph::Node Node;
5.407 +// const Graph& G;
5.408 +// std::queue<OutEdgeIt> bfs_queue;
5.409 +// ReachedMap reached;
5.410 +// bool b_node_newly_reached;
5.411 +// OutEdgeIt actual_edge;
5.412 +// public:
5.413 +// BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
5.414 +// void pushAndSetReached(Node s) {
5.415 +// reached.set(s, true);
5.416 +// if (bfs_queue.empty()) {
5.417 +// bfs_queue.push(G.template first<OutEdgeIt>(s));
5.418 +// actual_edge=bfs_queue.front();
5.419 +// if (actual_edge.valid()) {
5.420 +// Node w=G.bNode(actual_edge);
5.421 +// if (!reached.get(w)) {
5.422 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
5.423 +// reached.set(w, true);
5.424 +// b_node_newly_reached=true;
5.425 +// } else {
5.426 +// b_node_newly_reached=false;
5.427 +// }
5.428 +// } //else {
5.429 +// //}
5.430 +// } else {
5.431 +// bfs_queue.push(G.template first<OutEdgeIt>(s));
5.432 +// }
5.433 +// }
5.434 +// BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
5.435 +// operator++() {
5.436 +// if (bfs_queue.front().valid()) {
5.437 +// ++(bfs_queue.front());
5.438 +// actual_edge=bfs_queue.front();
5.439 +// if (actual_edge.valid()) {
5.440 +// Node w=G.bNode(actual_edge);
5.441 +// if (!reached.get(w)) {
5.442 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
5.443 +// reached.set(w, true);
5.444 +// b_node_newly_reached=true;
5.445 +// } else {
5.446 +// b_node_newly_reached=false;
5.447 +// }
5.448 +// }
5.449 +// } else {
5.450 +// bfs_queue.pop();
5.451 +// if (!bfs_queue.empty()) {
5.452 +// actual_edge=bfs_queue.front();
5.453 +// if (actual_edge.valid()) {
5.454 +// Node w=G.bNode(actual_edge);
5.455 +// if (!reached.get(w)) {
5.456 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
5.457 +// reached.set(w, true);
5.458 +// b_node_newly_reached=true;
5.459 +// } else {
5.460 +// b_node_newly_reached=false;
5.461 +// }
5.462 +// }
5.463 +// }
5.464 +// }
5.465 +// return *this;
5.466 +// }
5.467 +// bool finished() const { return bfs_queue.empty(); }
5.468 +// operator OutEdgeIt () const { return actual_edge; }
5.469 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
5.470 +// bool isANodeExamined() const { return !(actual_edge.valid()); }
5.471 +// const ReachedMap& getReachedMap() const { return reached; }
5.472 +// const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
5.473 +// };
5.474 +
5.475 +
5.476 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
5.477 +// class BfsIterator3 {
5.478 +// typedef typename Graph::Node Node;
5.479 +// const Graph& G;
5.480 +// std::queue< std::pair<Node, OutEdgeIt> > bfs_queue;
5.481 +// ReachedMap reached;
5.482 +// bool b_node_newly_reached;
5.483 +// OutEdgeIt actual_edge;
5.484 +// public:
5.485 +// BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
5.486 +// void pushAndSetReached(Node s) {
5.487 +// reached.set(s, true);
5.488 +// if (bfs_queue.empty()) {
5.489 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
5.490 +// actual_edge=bfs_queue.front().second;
5.491 +// if (actual_edge.valid()) {
5.492 +// Node w=G.bNode(actual_edge);
5.493 +// if (!reached.get(w)) {
5.494 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
5.495 +// reached.set(w, true);
5.496 +// b_node_newly_reached=true;
5.497 +// } else {
5.498 +// b_node_newly_reached=false;
5.499 +// }
5.500 +// } //else {
5.501 +// //}
5.502 +// } else {
5.503 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
5.504 +// }
5.505 +// }
5.506 +// BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
5.507 +// operator++() {
5.508 +// if (bfs_queue.front().second.valid()) {
5.509 +// ++(bfs_queue.front().second);
5.510 +// actual_edge=bfs_queue.front().second;
5.511 +// if (actual_edge.valid()) {
5.512 +// Node w=G.bNode(actual_edge);
5.513 +// if (!reached.get(w)) {
5.514 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
5.515 +// reached.set(w, true);
5.516 +// b_node_newly_reached=true;
5.517 +// } else {
5.518 +// b_node_newly_reached=false;
5.519 +// }
5.520 +// }
5.521 +// } else {
5.522 +// bfs_queue.pop();
5.523 +// if (!bfs_queue.empty()) {
5.524 +// actual_edge=bfs_queue.front().second;
5.525 +// if (actual_edge.valid()) {
5.526 +// Node w=G.bNode(actual_edge);
5.527 +// if (!reached.get(w)) {
5.528 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
5.529 +// reached.set(w, true);
5.530 +// b_node_newly_reached=true;
5.531 +// } else {
5.532 +// b_node_newly_reached=false;
5.533 +// }
5.534 +// }
5.535 +// }
5.536 +// }
5.537 +// return *this;
5.538 +// }
5.539 +// bool finished() const { return bfs_queue.empty(); }
5.540 +// operator OutEdgeIt () const { return actual_edge; }
5.541 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
5.542 +// bool isANodeExamined() const { return !(actual_edge.valid()); }
5.543 +// Node aNode() const { return bfs_queue.front().first; }
5.544 +// Node bNode() const { return G.bNode(actual_edge); }
5.545 +// const ReachedMap& getReachedMap() const { return reached; }
5.546 +// //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
5.547 +// };
5.548 +
5.549 +
5.550 +// template <typename Graph, typename OutEdgeIt,
5.551 +// typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
5.552 +// class BfsIterator4 {
5.553 +// typedef typename Graph::Node Node;
5.554 +// const Graph& G;
5.555 +// std::queue<Node> bfs_queue;
5.556 +// ReachedMap& reached;
5.557 +// bool b_node_newly_reached;
5.558 +// OutEdgeIt actual_edge;
5.559 +// bool own_reached_map;
5.560 +// public:
5.561 +// BfsIterator4(const Graph& _G, ReachedMap& _reached) :
5.562 +// G(_G), reached(_reached),
5.563 +// own_reached_map(false) { }
5.564 +// BfsIterator4(const Graph& _G) :
5.565 +// G(_G), reached(*(new ReachedMap(G /*, false*/))),
5.566 +// own_reached_map(true) { }
5.567 +// ~BfsIterator4() { if (own_reached_map) delete &reached; }
5.568 +// void pushAndSetReached(Node s) {
5.569 +// //std::cout << "mimi" << &reached << std::endl;
5.570 +// reached.set(s, true);
5.571 +// //std::cout << "mumus" << std::endl;
5.572 +// if (bfs_queue.empty()) {
5.573 +// //std::cout << "bibi1" << std::endl;
5.574 +// bfs_queue.push(s);
5.575 +// //std::cout << "zizi" << std::endl;
5.576 +// G./*getF*/first(actual_edge, s);
5.577 +// //std::cout << "kiki" << std::endl;
5.578 +// if (G.valid(actual_edge)/*.valid()*/) {
5.579 +// Node w=G.bNode(actual_edge);
5.580 +// if (!reached.get(w)) {
5.581 +// bfs_queue.push(w);
5.582 +// reached.set(w, true);
5.583 +// b_node_newly_reached=true;
5.584 +// } else {
5.585 +// b_node_newly_reached=false;
5.586 +// }
5.587 +// }
5.588 +// } else {
5.589 +// //std::cout << "bibi2" << std::endl;
5.590 +// bfs_queue.push(s);
5.591 +// }
5.592 +// }
5.593 +// BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
5.594 +// operator++() {
5.595 +// if (G.valid(actual_edge)/*.valid()*/) {
5.596 +// /*++*/G.next(actual_edge);
5.597 +// if (G.valid(actual_edge)/*.valid()*/) {
5.598 +// Node w=G.bNode(actual_edge);
5.599 +// if (!reached.get(w)) {
5.600 +// bfs_queue.push(w);
5.601 +// reached.set(w, true);
5.602 +// b_node_newly_reached=true;
5.603 +// } else {
5.604 +// b_node_newly_reached=false;
5.605 +// }
5.606 +// }
5.607 +// } else {
5.608 +// bfs_queue.pop();
5.609 +// if (!bfs_queue.empty()) {
5.610 +// G./*getF*/first(actual_edge, bfs_queue.front());
5.611 +// if (G.valid(actual_edge)/*.valid()*/) {
5.612 +// Node w=G.bNode(actual_edge);
5.613 +// if (!reached.get(w)) {
5.614 +// bfs_queue.push(w);
5.615 +// reached.set(w, true);
5.616 +// b_node_newly_reached=true;
5.617 +// } else {
5.618 +// b_node_newly_reached=false;
5.619 +// }
5.620 +// }
5.621 +// }
5.622 +// }
5.623 +// return *this;
5.624 +// }
5.625 +// bool finished() const { return bfs_queue.empty(); }
5.626 +// operator OutEdgeIt () const { return actual_edge; }
5.627 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
5.628 +// bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
5.629 +// Node aNode() const { return bfs_queue.front(); }
5.630 +// Node bNode() const { return G.bNode(actual_edge); }
5.631 +// const ReachedMap& getReachedMap() const { return reached; }
5.632 +// const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
5.633 +// };
5.634 +
5.635 +
5.636 + template <typename GraphWrapper, /*typename OutEdgeIt,*/
5.637 + typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
5.638 + class BfsIterator5 {
5.639 + typedef typename GraphWrapper::Node Node;
5.640 + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
5.641 + GraphWrapper G;
5.642 + std::queue<Node> bfs_queue;
5.643 + ReachedMap& reached;
5.644 + bool b_node_newly_reached;
5.645 + OutEdgeIt actual_edge;
5.646 + bool own_reached_map;
5.647 + public:
5.648 + BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
5.649 + G(_G), reached(_reached),
5.650 + own_reached_map(false) { }
5.651 + BfsIterator5(const GraphWrapper& _G) :
5.652 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
5.653 + own_reached_map(true) { }
5.654 +// BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
5.655 +// ReachedMap& _reached) :
5.656 +// G(_G), reached(_reached),
5.657 +// own_reached_map(false) { }
5.658 +// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
5.659 +// G(_G), reached(*(new ReachedMap(G /*, false*/))),
5.660 +// own_reached_map(true) { }
5.661 + ~BfsIterator5() { if (own_reached_map) delete &reached; }
5.662 + void pushAndSetReached(Node s) {
5.663 + reached.set(s, true);
5.664 + if (bfs_queue.empty()) {
5.665 + bfs_queue.push(s);
5.666 + G./*getF*/first(actual_edge, s);
5.667 + if (G.valid(actual_edge)/*.valid()*/) {
5.668 + Node w=G.bNode(actual_edge);
5.669 + if (!reached.get(w)) {
5.670 + bfs_queue.push(w);
5.671 + reached.set(w, true);
5.672 + b_node_newly_reached=true;
5.673 + } else {
5.674 + b_node_newly_reached=false;
5.675 + }
5.676 + }
5.677 + } else {
5.678 + bfs_queue.push(s);
5.679 + }
5.680 + }
5.681 + BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
5.682 + operator++() {
5.683 + if (G.valid(actual_edge)/*.valid()*/) {
5.684 + /*++*/G.next(actual_edge);
5.685 + if (G.valid(actual_edge)/*.valid()*/) {
5.686 + Node w=G.bNode(actual_edge);
5.687 + if (!reached.get(w)) {
5.688 + bfs_queue.push(w);
5.689 + reached.set(w, true);
5.690 + b_node_newly_reached=true;
5.691 + } else {
5.692 + b_node_newly_reached=false;
5.693 + }
5.694 + }
5.695 + } else {
5.696 + bfs_queue.pop();
5.697 + if (!bfs_queue.empty()) {
5.698 + G./*getF*/first(actual_edge, bfs_queue.front());
5.699 + if (G.valid(actual_edge)/*.valid()*/) {
5.700 + Node w=G.bNode(actual_edge);
5.701 + if (!reached.get(w)) {
5.702 + bfs_queue.push(w);
5.703 + reached.set(w, true);
5.704 + b_node_newly_reached=true;
5.705 + } else {
5.706 + b_node_newly_reached=false;
5.707 + }
5.708 + }
5.709 + }
5.710 + }
5.711 + return *this;
5.712 + }
5.713 + bool finished() const { return bfs_queue.empty(); }
5.714 + operator OutEdgeIt () const { return actual_edge; }
5.715 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
5.716 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
5.717 + Node aNode() const { return bfs_queue.front(); }
5.718 + Node bNode() const { return G.bNode(actual_edge); }
5.719 + const ReachedMap& getReachedMap() const { return reached; }
5.720 + const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
5.721 + };
5.722 +
5.723 +// template <typename Graph, typename OutEdgeIt,
5.724 +// typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
5.725 +// class DfsIterator4 {
5.726 +// typedef typename Graph::Node Node;
5.727 +// const Graph& G;
5.728 +// std::stack<OutEdgeIt> dfs_stack;
5.729 +// bool b_node_newly_reached;
5.730 +// OutEdgeIt actual_edge;
5.731 +// Node actual_node;
5.732 +// ReachedMap& reached;
5.733 +// bool own_reached_map;
5.734 +// public:
5.735 +// DfsIterator4(const Graph& _G, ReachedMap& _reached) :
5.736 +// G(_G), reached(_reached),
5.737 +// own_reached_map(false) { }
5.738 +// DfsIterator4(const Graph& _G) :
5.739 +// G(_G), reached(*(new ReachedMap(G /*, false*/))),
5.740 +// own_reached_map(true) { }
5.741 +// ~DfsIterator4() { if (own_reached_map) delete &reached; }
5.742 +// void pushAndSetReached(Node s) {
5.743 +// actual_node=s;
5.744 +// reached.set(s, true);
5.745 +// dfs_stack.push(G.template first<OutEdgeIt>(s));
5.746 +// }
5.747 +// DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
5.748 +// operator++() {
5.749 +// actual_edge=dfs_stack.top();
5.750 +// //actual_node=G.aNode(actual_edge);
5.751 +// if (G.valid(actual_edge)/*.valid()*/) {
5.752 +// Node w=G.bNode(actual_edge);
5.753 +// actual_node=w;
5.754 +// if (!reached.get(w)) {
5.755 +// dfs_stack.push(G.template first<OutEdgeIt>(w));
5.756 +// reached.set(w, true);
5.757 +// b_node_newly_reached=true;
5.758 +// } else {
5.759 +// actual_node=G.aNode(actual_edge);
5.760 +// /*++*/G.next(dfs_stack.top());
5.761 +// b_node_newly_reached=false;
5.762 +// }
5.763 +// } else {
5.764 +// //actual_node=G.aNode(dfs_stack.top());
5.765 +// dfs_stack.pop();
5.766 +// }
5.767 +// return *this;
5.768 +// }
5.769 +// bool finished() const { return dfs_stack.empty(); }
5.770 +// operator OutEdgeIt () const { return actual_edge; }
5.771 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
5.772 +// bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
5.773 +// Node aNode() const { return actual_node; /*FIXME*/}
5.774 +// Node bNode() const { return G.bNode(actual_edge); }
5.775 +// const ReachedMap& getReachedMap() const { return reached; }
5.776 +// const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
5.777 +// };
5.778 +
5.779 + template <typename GraphWrapper, /*typename OutEdgeIt,*/
5.780 + typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
5.781 + class DfsIterator5 {
5.782 + typedef typename GraphWrapper::Node Node;
5.783 + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
5.784 + GraphWrapper G;
5.785 + std::stack<OutEdgeIt> dfs_stack;
5.786 + bool b_node_newly_reached;
5.787 + OutEdgeIt actual_edge;
5.788 + Node actual_node;
5.789 + ReachedMap& reached;
5.790 + bool own_reached_map;
5.791 + public:
5.792 + DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
5.793 + G(_G), reached(_reached),
5.794 + own_reached_map(false) { }
5.795 + DfsIterator5(const GraphWrapper& _G) :
5.796 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
5.797 + own_reached_map(true) { }
5.798 + ~DfsIterator5() { if (own_reached_map) delete &reached; }
5.799 + void pushAndSetReached(Node s) {
5.800 + actual_node=s;
5.801 + reached.set(s, true);
5.802 + OutEdgeIt e;
5.803 + G.first(e, s);
5.804 + dfs_stack.push(e);
5.805 + }
5.806 + DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
5.807 + operator++() {
5.808 + actual_edge=dfs_stack.top();
5.809 + //actual_node=G.aNode(actual_edge);
5.810 + if (G.valid(actual_edge)/*.valid()*/) {
5.811 + Node w=G.bNode(actual_edge);
5.812 + actual_node=w;
5.813 + if (!reached.get(w)) {
5.814 + OutEdgeIt e;
5.815 + G.first(e, w);
5.816 + dfs_stack.push(e);
5.817 + reached.set(w, true);
5.818 + b_node_newly_reached=true;
5.819 + } else {
5.820 + actual_node=G.aNode(actual_edge);
5.821 + /*++*/G.next(dfs_stack.top());
5.822 + b_node_newly_reached=false;
5.823 + }
5.824 + } else {
5.825 + //actual_node=G.aNode(dfs_stack.top());
5.826 + dfs_stack.pop();
5.827 + }
5.828 + return *this;
5.829 + }
5.830 + bool finished() const { return dfs_stack.empty(); }
5.831 + operator OutEdgeIt () const { return actual_edge; }
5.832 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
5.833 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
5.834 + Node aNode() const { return actual_node; /*FIXME*/}
5.835 + Node bNode() const { return G.bNode(actual_edge); }
5.836 + const ReachedMap& getReachedMap() const { return reached; }
5.837 + const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
5.838 + };
5.839 +
5.840 +
5.841 +
5.842 +} // namespace hugo
5.843 +
5.844 +#endif //HUGO_BFS_ITERATOR_H
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/work/marci/edmonds_karp.h Mon Apr 05 15:02:39 2004 +0000
6.3 @@ -0,0 +1,1238 @@
6.4 +// -*- c++ -*-
6.5 +#ifndef HUGO_EDMONDS_KARP_H
6.6 +#define HUGO_EDMONDS_KARP_H
6.7 +
6.8 +#include <algorithm>
6.9 +#include <list>
6.10 +#include <iterator>
6.11 +
6.12 +#include <bfs_iterator.h>
6.13 +#include <invalid.h>
6.14 +
6.15 +namespace hugo {
6.16 +
6.17 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
6.18 + class ResGraph {
6.19 + public:
6.20 + typedef typename Graph::Node Node;
6.21 + typedef typename Graph::NodeIt NodeIt;
6.22 + private:
6.23 + typedef typename Graph::SymEdgeIt OldSymEdgeIt;
6.24 + const Graph& G;
6.25 + FlowMap& flow;
6.26 + const CapacityMap& capacity;
6.27 + public:
6.28 + ResGraph(const Graph& _G, FlowMap& _flow,
6.29 + const CapacityMap& _capacity) :
6.30 + G(_G), flow(_flow), capacity(_capacity) { }
6.31 +
6.32 + class Edge;
6.33 + class OutEdgeIt;
6.34 + friend class Edge;
6.35 + friend class OutEdgeIt;
6.36 +
6.37 + class Edge {
6.38 + friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
6.39 + protected:
6.40 + const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
6.41 + OldSymEdgeIt sym;
6.42 + public:
6.43 + Edge() { }
6.44 + //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
6.45 + Number free() const {
6.46 + if (resG->G.aNode(sym)==resG->G.tail(sym)) {
6.47 + return (resG->capacity.get(sym)-resG->flow.get(sym));
6.48 + } else {
6.49 + return (resG->flow.get(sym));
6.50 + }
6.51 + }
6.52 + bool valid() const { return sym.valid(); }
6.53 + void augment(Number a) const {
6.54 + if (resG->G.aNode(sym)==resG->G.tail(sym)) {
6.55 + resG->flow.set(sym, resG->flow.get(sym)+a);
6.56 + //resG->flow[sym]+=a;
6.57 + } else {
6.58 + resG->flow.set(sym, resG->flow.get(sym)-a);
6.59 + //resG->flow[sym]-=a;
6.60 + }
6.61 + }
6.62 + };
6.63 +
6.64 + class OutEdgeIt : public Edge {
6.65 + friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
6.66 + public:
6.67 + OutEdgeIt() { }
6.68 + //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
6.69 + private:
6.70 + OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
6.71 + resG=&_resG;
6.72 + sym=resG->G.template first<OldSymEdgeIt>(v);
6.73 + while( sym.valid() && !(free()>0) ) { ++sym; }
6.74 + }
6.75 + public:
6.76 + OutEdgeIt& operator++() {
6.77 + ++sym;
6.78 + while( sym.valid() && !(free()>0) ) { ++sym; }
6.79 + return *this;
6.80 + }
6.81 + };
6.82 +
6.83 + void /*getF*/first(OutEdgeIt& e, Node v) const {
6.84 + e=OutEdgeIt(*this, v);
6.85 + }
6.86 + void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
6.87 +
6.88 + template< typename It >
6.89 + It first() const {
6.90 + It e;
6.91 + /*getF*/first(e);
6.92 + return e;
6.93 + }
6.94 +
6.95 + template< typename It >
6.96 + It first(Node v) const {
6.97 + It e;
6.98 + /*getF*/first(e, v);
6.99 + return e;
6.100 + }
6.101 +
6.102 + Node tail(Edge e) const { return G.aNode(e.sym); }
6.103 + Node head(Edge e) const { return G.bNode(e.sym); }
6.104 +
6.105 + Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
6.106 + Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
6.107 +
6.108 + int id(Node v) const { return G.id(v); }
6.109 +
6.110 + template <typename S>
6.111 + class NodeMap {
6.112 + typename Graph::NodeMap<S> node_map;
6.113 + public:
6.114 + NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
6.115 + NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
6.116 + void set(Node nit, S a) { node_map.set(nit, a); }
6.117 + S get(Node nit) const { return node_map.get(nit); }
6.118 + S& operator[](Node nit) { return node_map[nit]; }
6.119 + const S& operator[](Node nit) const { return node_map[nit]; }
6.120 + };
6.121 +
6.122 + };
6.123 +
6.124 +
6.125 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
6.126 + class ResGraph2 {
6.127 + public:
6.128 + typedef typename Graph::Node Node;
6.129 + typedef typename Graph::NodeIt NodeIt;
6.130 + private:
6.131 + //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
6.132 + typedef typename Graph::OutEdgeIt OldOutEdgeIt;
6.133 + typedef typename Graph::InEdgeIt OldInEdgeIt;
6.134 +
6.135 + const Graph& G;
6.136 + FlowMap& flow;
6.137 + const CapacityMap& capacity;
6.138 + public:
6.139 + ResGraph2(const Graph& _G, FlowMap& _flow,
6.140 + const CapacityMap& _capacity) :
6.141 + G(_G), flow(_flow), capacity(_capacity) { }
6.142 +
6.143 + class Edge;
6.144 + class OutEdgeIt;
6.145 + friend class Edge;
6.146 + friend class OutEdgeIt;
6.147 +
6.148 + class Edge {
6.149 + friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
6.150 + protected:
6.151 + const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
6.152 + //OldSymEdgeIt sym;
6.153 + OldOutEdgeIt out;
6.154 + OldInEdgeIt in;
6.155 + bool out_or_in; //true, iff out
6.156 + public:
6.157 + Edge() : out_or_in(true) { }
6.158 + Number free() const {
6.159 + if (out_or_in) {
6.160 + return (resG->capacity.get(out)-resG->flow.get(out));
6.161 + } else {
6.162 + return (resG->flow.get(in));
6.163 + }
6.164 + }
6.165 + bool valid() const {
6.166 + return out_or_in && out.valid() || in.valid(); }
6.167 + void augment(Number a) const {
6.168 + if (out_or_in) {
6.169 + resG->flow.set(out, resG->flow.get(out)+a);
6.170 + } else {
6.171 + resG->flow.set(in, resG->flow.get(in)-a);
6.172 + }
6.173 + }
6.174 + };
6.175 +
6.176 + class OutEdgeIt : public Edge {
6.177 + friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
6.178 + public:
6.179 + OutEdgeIt() { }
6.180 + private:
6.181 + OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
6.182 + resG=&_resG;
6.183 + out=resG->G.template first<OldOutEdgeIt>(v);
6.184 + while( out.valid() && !(free()>0) ) { ++out; }
6.185 + if (!out.valid()) {
6.186 + out_or_in=0;
6.187 + in=resG->G.template first<OldInEdgeIt>(v);
6.188 + while( in.valid() && !(free()>0) ) { ++in; }
6.189 + }
6.190 + }
6.191 + public:
6.192 + OutEdgeIt& operator++() {
6.193 + if (out_or_in) {
6.194 + Node v=resG->G.aNode(out);
6.195 + ++out;
6.196 + while( out.valid() && !(free()>0) ) { ++out; }
6.197 + if (!out.valid()) {
6.198 + out_or_in=0;
6.199 + in=resG->G.template first<OldInEdgeIt>(v);
6.200 + while( in.valid() && !(free()>0) ) { ++in; }
6.201 + }
6.202 + } else {
6.203 + ++in;
6.204 + while( in.valid() && !(free()>0) ) { ++in; }
6.205 + }
6.206 + return *this;
6.207 + }
6.208 + };
6.209 +
6.210 + void /*getF*/first(OutEdgeIt& e, Node v) const {
6.211 + e=OutEdgeIt(*this, v);
6.212 + }
6.213 + void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
6.214 +
6.215 + template< typename It >
6.216 + It first() const {
6.217 + It e;
6.218 + /*getF*/first(e);
6.219 + return e;
6.220 + }
6.221 +
6.222 + template< typename It >
6.223 + It first(Node v) const {
6.224 + It e;
6.225 + /*getF*/first(e, v);
6.226 + return e;
6.227 + }
6.228 +
6.229 + Node tail(Edge e) const {
6.230 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
6.231 + Node head(Edge e) const {
6.232 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
6.233 +
6.234 + Node aNode(OutEdgeIt e) const {
6.235 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
6.236 + Node bNode(OutEdgeIt e) const {
6.237 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
6.238 +
6.239 + int id(Node v) const { return G.id(v); }
6.240 +
6.241 + template <typename S>
6.242 + class NodeMap {
6.243 + typename Graph::NodeMap<S> node_map;
6.244 + public:
6.245 + NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
6.246 + NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
6.247 + void set(Node nit, S a) { node_map.set(nit, a); }
6.248 + S get(Node nit) const { return node_map.get(nit); }
6.249 + };
6.250 + };
6.251 +
6.252 +
6.253 + template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
6.254 + class MaxFlow {
6.255 + protected:
6.256 + typedef GraphWrapper GW;
6.257 + typedef typename GW::Node Node;
6.258 + typedef typename GW::Edge Edge;
6.259 + typedef typename GW::EdgeIt EdgeIt;
6.260 + typedef typename GW::OutEdgeIt OutEdgeIt;
6.261 + typedef typename GW::InEdgeIt InEdgeIt;
6.262 + //const Graph* G;
6.263 + GW gw;
6.264 + Node s;
6.265 + Node t;
6.266 + FlowMap* flow;
6.267 + const CapacityMap* capacity;
6.268 + typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW;
6.269 + typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
6.270 + typedef typename ResGW::Edge ResGWEdge;
6.271 + public:
6.272 +
6.273 + MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
6.274 + gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
6.275 +
6.276 + bool augmentOnShortestPath() {
6.277 + ResGW res_graph(gw, *flow, *capacity);
6.278 + bool _augment=false;
6.279 +
6.280 + typedef typename ResGW::NodeMap<bool> ReachedMap;
6.281 + BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
6.282 + bfs.pushAndSetReached(s);
6.283 +
6.284 + typename ResGW::NodeMap<ResGWEdge> pred(res_graph);
6.285 + pred.set(s, INVALID);
6.286 +
6.287 + typename ResGW::NodeMap<Number> free(res_graph);
6.288 +
6.289 + //searching for augmenting path
6.290 + while ( !bfs.finished() ) {
6.291 + ResGWOutEdgeIt e=bfs;
6.292 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
6.293 + Node v=res_graph.tail(e);
6.294 + Node w=res_graph.head(e);
6.295 + pred.set(w, e);
6.296 + if (res_graph.valid(pred.get(v))) {
6.297 + free.set(w, std::min(free.get(v), res_graph.resCap(e)));
6.298 + } else {
6.299 + free.set(w, res_graph.resCap(e));
6.300 + }
6.301 + if (res_graph.head(e)==t) { _augment=true; break; }
6.302 + }
6.303 +
6.304 + ++bfs;
6.305 + } //end of searching augmenting path
6.306 +
6.307 + if (_augment) {
6.308 + Node n=t;
6.309 + Number augment_value=free.get(t);
6.310 + while (res_graph.valid(pred.get(n))) {
6.311 + ResGWEdge e=pred.get(n);
6.312 + res_graph.augment(e, augment_value);
6.313 + n=res_graph.tail(e);
6.314 + }
6.315 + }
6.316 +
6.317 + return _augment;
6.318 + }
6.319 +
6.320 + template<typename MapGraphWrapper>
6.321 + class DistanceMap {
6.322 + protected:
6.323 + MapGraphWrapper gw;
6.324 + typename MapGraphWrapper::NodeMap<int> dist;
6.325 + public:
6.326 + DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
6.327 + void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
6.328 + int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
6.329 + bool get(const typename MapGraphWrapper::Edge& e) const {
6.330 + return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
6.331 + }
6.332 + };
6.333 +
6.334 + template<typename MutableGraph> bool augmentOnBlockingFlow() {
6.335 + typedef MutableGraph MG;
6.336 + bool _augment=false;
6.337 +
6.338 + ResGW res_graph(gw, *flow, *capacity);
6.339 +
6.340 + typedef typename ResGW::NodeMap<bool> ReachedMap;
6.341 + BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
6.342 +
6.343 + bfs.pushAndSetReached(s);
6.344 + //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
6.345 + DistanceMap<ResGW> dist(res_graph);
6.346 + while ( !bfs.finished() ) {
6.347 + ResGWOutEdgeIt e=bfs;
6.348 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
6.349 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
6.350 + }
6.351 + ++bfs;
6.352 + } //computing distances from s in the residual graph
6.353 +
6.354 + MG F;
6.355 + typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
6.356 + FilterResGW filter_res_graph(res_graph, dist);
6.357 + typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
6.358 + {
6.359 + typename ResGW::NodeIt n;
6.360 + for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
6.361 + res_graph_to_F.set(n, F.addNode());
6.362 + }
6.363 + }
6.364 +
6.365 + typename MG::Node sF=res_graph_to_F.get(s);
6.366 + typename MG::Node tF=res_graph_to_F.get(t);
6.367 + typename MG::EdgeMap<ResGWEdge> original_edge(F);
6.368 + typename MG::EdgeMap<Number> residual_capacity(F);
6.369 +
6.370 + //Making F to the graph containing the edges of the residual graph
6.371 + //which are in some shortest paths
6.372 + {
6.373 + typename FilterResGW::EdgeIt e;
6.374 + for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
6.375 + //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
6.376 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
6.377 + original_edge.update();
6.378 + original_edge.set(f, e);
6.379 + residual_capacity.update();
6.380 + residual_capacity.set(f, res_graph.resCap(e));
6.381 + //}
6.382 + }
6.383 + }
6.384 +
6.385 + bool __augment=true;
6.386 +
6.387 + while (__augment) {
6.388 + __augment=false;
6.389 + //computing blocking flow with dfs
6.390 + typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
6.391 + DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
6.392 + typename MG::NodeMap<typename MG::Edge> pred(F);
6.393 + pred.set(sF, INVALID);
6.394 + //invalid iterators for sources
6.395 +
6.396 + typename MG::NodeMap<Number> free(F);
6.397 +
6.398 + dfs.pushAndSetReached(sF);
6.399 + while (!dfs.finished()) {
6.400 + ++dfs;
6.401 + if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
6.402 + if (dfs.isBNodeNewlyReached()) {
6.403 + typename MG::Node v=F.aNode(dfs);
6.404 + typename MG::Node w=F.bNode(dfs);
6.405 + pred.set(w, dfs);
6.406 + if (F.valid(pred.get(v))) {
6.407 + free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
6.408 + } else {
6.409 + free.set(w, residual_capacity.get(dfs));
6.410 + }
6.411 + if (w==tF) {
6.412 + __augment=true;
6.413 + _augment=true;
6.414 + break;
6.415 + }
6.416 +
6.417 + } else {
6.418 + F.erase(/*typename MG::OutEdgeIt*/(dfs));
6.419 + }
6.420 + }
6.421 + }
6.422 +
6.423 + if (__augment) {
6.424 + typename MG::Node n=tF;
6.425 + Number augment_value=free.get(tF);
6.426 + while (F.valid(pred.get(n))) {
6.427 + typename MG::Edge e=pred.get(n);
6.428 + res_graph.augment(original_edge.get(e), augment_value);
6.429 + n=F.tail(e);
6.430 + if (residual_capacity.get(e)==augment_value)
6.431 + F.erase(e);
6.432 + else
6.433 + residual_capacity.set(e, residual_capacity.get(e)-augment_value);
6.434 + }
6.435 + }
6.436 +
6.437 + }
6.438 +
6.439 + return _augment;
6.440 + }
6.441 +
6.442 + template<typename MutableGraph> bool augmentOnBlockingFlow1() {
6.443 + typedef MutableGraph MG;
6.444 + bool _augment=false;
6.445 +
6.446 + ResGW res_graph(gw, *flow, *capacity);
6.447 +
6.448 + //bfs for distances on the residual graph
6.449 + typedef typename ResGW::NodeMap<bool> ReachedMap;
6.450 + BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
6.451 + bfs.pushAndSetReached(s);
6.452 + typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
6.453 +
6.454 + //F will contain the physical copy of the residual graph
6.455 + //with the set of edges which are on shortest paths
6.456 + MG F;
6.457 + typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
6.458 + {
6.459 + typename ResGW::NodeIt n;
6.460 + for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
6.461 + res_graph_to_F.set(n, F.addNode());
6.462 + }
6.463 + }
6.464 +
6.465 + typename MG::Node sF=res_graph_to_F.get(s);
6.466 + typename MG::Node tF=res_graph_to_F.get(t);
6.467 + typename MG::EdgeMap<ResGWEdge> original_edge(F);
6.468 + typename MG::EdgeMap<Number> residual_capacity(F);
6.469 +
6.470 + while ( !bfs.finished() ) {
6.471 + ResGWOutEdgeIt e=bfs;
6.472 + if (res_graph.valid(e)) {
6.473 + if (bfs.isBNodeNewlyReached()) {
6.474 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
6.475 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
6.476 + original_edge.update();
6.477 + original_edge.set(f, e);
6.478 + residual_capacity.update();
6.479 + residual_capacity.set(f, res_graph.resCap(e));
6.480 + } else {
6.481 + if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
6.482 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
6.483 + original_edge.update();
6.484 + original_edge.set(f, e);
6.485 + residual_capacity.update();
6.486 + residual_capacity.set(f, res_graph.resCap(e));
6.487 + }
6.488 + }
6.489 + }
6.490 + ++bfs;
6.491 + } //computing distances from s in the residual graph
6.492 +
6.493 + bool __augment=true;
6.494 +
6.495 + while (__augment) {
6.496 + __augment=false;
6.497 + //computing blocking flow with dfs
6.498 + typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
6.499 + DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
6.500 + typename MG::NodeMap<typename MG::Edge> pred(F);
6.501 + pred.set(sF, INVALID);
6.502 + //invalid iterators for sources
6.503 +
6.504 + typename MG::NodeMap<Number> free(F);
6.505 +
6.506 + dfs.pushAndSetReached(sF);
6.507 + while (!dfs.finished()) {
6.508 + ++dfs;
6.509 + if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
6.510 + if (dfs.isBNodeNewlyReached()) {
6.511 + typename MG::Node v=F.aNode(dfs);
6.512 + typename MG::Node w=F.bNode(dfs);
6.513 + pred.set(w, dfs);
6.514 + if (F.valid(pred.get(v))) {
6.515 + free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
6.516 + } else {
6.517 + free.set(w, residual_capacity.get(dfs));
6.518 + }
6.519 + if (w==tF) {
6.520 + __augment=true;
6.521 + _augment=true;
6.522 + break;
6.523 + }
6.524 +
6.525 + } else {
6.526 + F.erase(/*typename MG::OutEdgeIt*/(dfs));
6.527 + }
6.528 + }
6.529 + }
6.530 +
6.531 + if (__augment) {
6.532 + typename MG::Node n=tF;
6.533 + Number augment_value=free.get(tF);
6.534 + while (F.valid(pred.get(n))) {
6.535 + typename MG::Edge e=pred.get(n);
6.536 + res_graph.augment(original_edge.get(e), augment_value);
6.537 + n=F.tail(e);
6.538 + if (residual_capacity.get(e)==augment_value)
6.539 + F.erase(e);
6.540 + else
6.541 + residual_capacity.set(e, residual_capacity.get(e)-augment_value);
6.542 + }
6.543 + }
6.544 +
6.545 + }
6.546 +
6.547 + return _augment;
6.548 + }
6.549 +
6.550 + bool augmentOnBlockingFlow2() {
6.551 + bool _augment=false;
6.552 +
6.553 + ResGW res_graph(gw, *flow, *capacity);
6.554 +
6.555 + typedef typename ResGW::NodeMap<bool> ReachedMap;
6.556 + BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
6.557 +
6.558 + bfs.pushAndSetReached(s);
6.559 + DistanceMap<ResGW> dist(res_graph);
6.560 + while ( !bfs.finished() ) {
6.561 + ResGWOutEdgeIt e=bfs;
6.562 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
6.563 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
6.564 + }
6.565 + ++bfs;
6.566 + } //computing distances from s in the residual graph
6.567 +
6.568 + //Subgraph containing the edges on some shortest paths
6.569 + typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
6.570 + FilterResGW filter_res_graph(res_graph, dist);
6.571 +
6.572 + //Subgraph, which is able to delete edges which are already
6.573 + //met by the dfs
6.574 + typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>
6.575 + first_out_edges(filter_res_graph);
6.576 + typename FilterResGW::NodeIt v;
6.577 + for(filter_res_graph.first(v); filter_res_graph.valid(v);
6.578 + filter_res_graph.next(v))
6.579 + {
6.580 + typename FilterResGW::OutEdgeIt e;
6.581 + filter_res_graph.first(e, v);
6.582 + first_out_edges.set(v, e);
6.583 + }
6.584 + typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
6.585 + NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
6.586 + ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
6.587 +
6.588 + bool __augment=true;
6.589 +
6.590 + while (__augment) {
6.591 +
6.592 + __augment=false;
6.593 + //computing blocking flow with dfs
6.594 + typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;
6.595 + DfsIterator5< ErasingResGW, BlockingReachedMap >
6.596 + dfs(erasing_res_graph);
6.597 + typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
6.598 + pred(erasing_res_graph);
6.599 + pred.set(s, INVALID);
6.600 + //invalid iterators for sources
6.601 +
6.602 + typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
6.603 +
6.604 + dfs.pushAndSetReached(s);
6.605 + while (!dfs.finished()) {
6.606 + ++dfs;
6.607 + if (erasing_res_graph.valid(
6.608 + /*typename ErasingResGW::OutEdgeIt*/(dfs)))
6.609 + {
6.610 + if (dfs.isBNodeNewlyReached()) {
6.611 +
6.612 + typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
6.613 + typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
6.614 +
6.615 + pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
6.616 + if (erasing_res_graph.valid(pred.get(v))) {
6.617 + free.set(w, std::min(free.get(v), res_graph.resCap(dfs)));
6.618 + } else {
6.619 + free.set(w, res_graph.resCap(dfs));
6.620 + }
6.621 +
6.622 + if (w==t) {
6.623 + __augment=true;
6.624 + _augment=true;
6.625 + break;
6.626 + }
6.627 + } else {
6.628 + erasing_res_graph.erase(dfs);
6.629 + }
6.630 + }
6.631 + }
6.632 +
6.633 + if (__augment) {
6.634 + typename ErasingResGW::Node n=t;
6.635 + Number augment_value=free.get(n);
6.636 + while (erasing_res_graph.valid(pred.get(n))) {
6.637 + typename ErasingResGW::OutEdgeIt e=pred.get(n);
6.638 + res_graph.augment(e, augment_value);
6.639 + n=erasing_res_graph.tail(e);
6.640 + if (res_graph.resCap(e)==0)
6.641 + erasing_res_graph.erase(e);
6.642 + }
6.643 + }
6.644 +
6.645 + } //while (__augment)
6.646 +
6.647 + return _augment;
6.648 + }
6.649 +
6.650 +// bool augmentOnBlockingFlow2() {
6.651 +// bool _augment=false;
6.652 +
6.653 +// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
6.654 +// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
6.655 +// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
6.656 +// typedef typename EAugGraph::Edge EAugEdge;
6.657 +
6.658 +// EAugGraph res_graph(*G, *flow, *capacity);
6.659 +
6.660 +// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
6.661 +// BfsIterator5<
6.662 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
6.663 +// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
6.664 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
6.665 +
6.666 +// bfs.pushAndSetReached(s);
6.667 +
6.668 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
6.669 +// NodeMap<int>& dist=res_graph.dist;
6.670 +
6.671 +// while ( !bfs.finished() ) {
6.672 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
6.673 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
6.674 +// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
6.675 +// }
6.676 +// ++bfs;
6.677 +// } //computing distances from s in the residual graph
6.678 +
6.679 +// bool __augment=true;
6.680 +
6.681 +// while (__augment) {
6.682 +
6.683 +// __augment=false;
6.684 +// //computing blocking flow with dfs
6.685 +// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
6.686 +// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
6.687 +// dfs(res_graph);
6.688 +// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
6.689 +// pred.set(s, EAugEdge(INVALID));
6.690 +// //invalid iterators for sources
6.691 +
6.692 +// typename EAugGraph::NodeMap<Number> free(res_graph);
6.693 +
6.694 +// dfs.pushAndSetReached(s);
6.695 +// while (!dfs.finished()) {
6.696 +// ++dfs;
6.697 +// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
6.698 +// if (dfs.isBNodeNewlyReached()) {
6.699 +
6.700 +// typename EAugGraph::Node v=res_graph.aNode(dfs);
6.701 +// typename EAugGraph::Node w=res_graph.bNode(dfs);
6.702 +
6.703 +// pred.set(w, EAugOutEdgeIt(dfs));
6.704 +// if (res_graph.valid(pred.get(v))) {
6.705 +// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
6.706 +// } else {
6.707 +// free.set(w, res_graph.free(dfs));
6.708 +// }
6.709 +
6.710 +// if (w==t) {
6.711 +// __augment=true;
6.712 +// _augment=true;
6.713 +// break;
6.714 +// }
6.715 +// } else {
6.716 +// res_graph.erase(dfs);
6.717 +// }
6.718 +// }
6.719 +
6.720 +// }
6.721 +
6.722 +// if (__augment) {
6.723 +// typename EAugGraph::Node n=t;
6.724 +// Number augment_value=free.get(t);
6.725 +// while (res_graph.valid(pred.get(n))) {
6.726 +// EAugEdge e=pred.get(n);
6.727 +// res_graph.augment(e, augment_value);
6.728 +// n=res_graph.tail(e);
6.729 +// if (res_graph.free(e)==0)
6.730 +// res_graph.erase(e);
6.731 +// }
6.732 +// }
6.733 +
6.734 +// }
6.735 +
6.736 +// return _augment;
6.737 +// }
6.738 +
6.739 + void run() {
6.740 + //int num_of_augmentations=0;
6.741 + while (augmentOnShortestPath()) {
6.742 + //while (augmentOnBlockingFlow<MutableGraph>()) {
6.743 + //std::cout << ++num_of_augmentations << " ";
6.744 + //std::cout<<std::endl;
6.745 + }
6.746 + }
6.747 +
6.748 + template<typename MutableGraph> void run() {
6.749 + //int num_of_augmentations=0;
6.750 + //while (augmentOnShortestPath()) {
6.751 + while (augmentOnBlockingFlow<MutableGraph>()) {
6.752 + //std::cout << ++num_of_augmentations << " ";
6.753 + //std::cout<<std::endl;
6.754 + }
6.755 + }
6.756 +
6.757 + Number flowValue() {
6.758 + Number a=0;
6.759 + OutEdgeIt e;
6.760 + for(gw.first(e, s); gw.valid(e); gw.next(e)) {
6.761 + a+=flow->get(e);
6.762 + }
6.763 + return a;
6.764 + }
6.765 +
6.766 + };
6.767 +
6.768 +
6.769 +// template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
6.770 +// class MaxMatching {
6.771 +// public:
6.772 +// typedef typename Graph::Node Node;
6.773 +// typedef typename Graph::NodeIt NodeIt;
6.774 +// typedef typename Graph::Edge Edge;
6.775 +// typedef typename Graph::EdgeIt EdgeIt;
6.776 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
6.777 +// typedef typename Graph::InEdgeIt InEdgeIt;
6.778 +
6.779 +// typedef typename Graph::NodeMap<bool> SMap;
6.780 +// typedef typename Graph::NodeMap<bool> TMap;
6.781 +// private:
6.782 +// const Graph* G;
6.783 +// SMap* S;
6.784 +// TMap* T;
6.785 +// //Node s;
6.786 +// //Node t;
6.787 +// FlowMap* flow;
6.788 +// const CapacityMap* capacity;
6.789 +// typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
6.790 +// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
6.791 +// typedef typename AugGraph::Edge AugEdge;
6.792 +// typename Graph::NodeMap<int> used; //0
6.793 +
6.794 +// public:
6.795 +// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
6.796 +// G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
6.797 +// bool augmentOnShortestPath() {
6.798 +// AugGraph res_graph(*G, *flow, *capacity);
6.799 +// bool _augment=false;
6.800 +
6.801 +// typedef typename AugGraph::NodeMap<bool> ReachedMap;
6.802 +// BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
6.803 +// typename AugGraph::NodeMap<AugEdge> pred(res_graph);
6.804 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
6.805 +// if ((S->get(s)) && (used.get(s)<1) ) {
6.806 +// //Number u=0;
6.807 +// //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
6.808 +// //u+=flow->get(e);
6.809 +// //if (u<1) {
6.810 +// bfs.pushAndSetReached(s);
6.811 +// pred.set(s, AugEdge(INVALID));
6.812 +// //}
6.813 +// }
6.814 +// }
6.815 +
6.816 +// typename AugGraph::NodeMap<Number> free(res_graph);
6.817 +
6.818 +// Node n;
6.819 +// //searching for augmenting path
6.820 +// while ( !bfs.finished() ) {
6.821 +// AugOutEdgeIt e=bfs;
6.822 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
6.823 +// Node v=res_graph.tail(e);
6.824 +// Node w=res_graph.head(e);
6.825 +// pred.set(w, e);
6.826 +// if (res_graph.valid(pred.get(v))) {
6.827 +// free.set(w, std::min(free.get(v), res_graph.free(e)));
6.828 +// } else {
6.829 +// free.set(w, res_graph.free(e));
6.830 +// }
6.831 +// n=res_graph.head(e);
6.832 +// if (T->get(n) && (used.get(n)<1) ) {
6.833 +// //Number u=0;
6.834 +// //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
6.835 +// //u+=flow->get(f);
6.836 +// //if (u<1) {
6.837 +// _augment=true;
6.838 +// break;
6.839 +// //}
6.840 +// }
6.841 +// }
6.842 +
6.843 +// ++bfs;
6.844 +// } //end of searching augmenting path
6.845 +
6.846 +// if (_augment) {
6.847 +// //Node n=t;
6.848 +// used.set(n, 1); //mind2 vegen jav
6.849 +// Number augment_value=free.get(n);
6.850 +// while (res_graph.valid(pred.get(n))) {
6.851 +// AugEdge e=pred.get(n);
6.852 +// res_graph.augment(e, augment_value);
6.853 +// n=res_graph.tail(e);
6.854 +// }
6.855 +// used.set(n, 1); //mind2 vegen jav
6.856 +// }
6.857 +
6.858 +// return _augment;
6.859 +// }
6.860 +
6.861 +// // template<typename MutableGraph> bool augmentOnBlockingFlow() {
6.862 +// // bool _augment=false;
6.863 +
6.864 +// // AugGraph res_graph(*G, *flow, *capacity);
6.865 +
6.866 +// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
6.867 +// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
6.868 +
6.869 +
6.870 +
6.871 +
6.872 +
6.873 +// // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
6.874 +// // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
6.875 +// // if (S->get(s)) {
6.876 +// // Number u=0;
6.877 +// // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
6.878 +// // u+=flow->get(e);
6.879 +// // if (u<1) {
6.880 +// // bfs.pushAndSetReached(s);
6.881 +// // //pred.set(s, AugEdge(INVALID));
6.882 +// // }
6.883 +// // }
6.884 +// // }
6.885 +
6.886 +
6.887 +
6.888 +
6.889 +// // //bfs.pushAndSetReached(s);
6.890 +// // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
6.891 +// // while ( !bfs.finished() ) {
6.892 +// // AugOutEdgeIt e=bfs;
6.893 +// // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
6.894 +// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
6.895 +// // }
6.896 +
6.897 +// // ++bfs;
6.898 +// // } //computing distances from s in the residual graph
6.899 +
6.900 +// // MutableGraph F;
6.901 +// // typename AugGraph::NodeMap<typename MutableGraph::Node>
6.902 +// // res_graph_to_F(res_graph);
6.903 +// // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
6.904 +// // res_graph_to_F.set(n, F.addNode());
6.905 +// // }
6.906 +
6.907 +// // typename MutableGraph::Node sF=res_graph_to_F.get(s);
6.908 +// // typename MutableGraph::Node tF=res_graph_to_F.get(t);
6.909 +
6.910 +// // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
6.911 +// // typename MutableGraph::EdgeMap<Number> residual_capacity(F);
6.912 +
6.913 +// // //Making F to the graph containing the edges of the residual graph
6.914 +// // //which are in some shortest paths
6.915 +// // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
6.916 +// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
6.917 +// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
6.918 +// // original_edge.update();
6.919 +// // original_edge.set(f, e);
6.920 +// // residual_capacity.update();
6.921 +// // residual_capacity.set(f, res_graph.free(e));
6.922 +// // }
6.923 +// // }
6.924 +
6.925 +// // bool __augment=true;
6.926 +
6.927 +// // while (__augment) {
6.928 +// // __augment=false;
6.929 +// // //computing blocking flow with dfs
6.930 +// // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
6.931 +// // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
6.932 +// // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
6.933 +// // pred.set(sF, typename MutableGraph::Edge(INVALID));
6.934 +// // //invalid iterators for sources
6.935 +
6.936 +// // typename MutableGraph::NodeMap<Number> free(F);
6.937 +
6.938 +// // dfs.pushAndSetReached(sF);
6.939 +// // while (!dfs.finished()) {
6.940 +// // ++dfs;
6.941 +// // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
6.942 +// // if (dfs.isBNodeNewlyReached()) {
6.943 +// // typename MutableGraph::Node v=F.aNode(dfs);
6.944 +// // typename MutableGraph::Node w=F.bNode(dfs);
6.945 +// // pred.set(w, dfs);
6.946 +// // if (F.valid(pred.get(v))) {
6.947 +// // free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
6.948 +// // } else {
6.949 +// // free.set(w, residual_capacity.get(dfs));
6.950 +// // }
6.951 +// // if (w==tF) {
6.952 +// // __augment=true;
6.953 +// // _augment=true;
6.954 +// // break;
6.955 +// // }
6.956 +
6.957 +// // } else {
6.958 +// // F.erase(typename MutableGraph::OutEdgeIt(dfs));
6.959 +// // }
6.960 +// // }
6.961 +// // }
6.962 +
6.963 +// // if (__augment) {
6.964 +// // typename MutableGraph::Node n=tF;
6.965 +// // Number augment_value=free.get(tF);
6.966 +// // while (F.valid(pred.get(n))) {
6.967 +// // typename MutableGraph::Edge e=pred.get(n);
6.968 +// // res_graph.augment(original_edge.get(e), augment_value);
6.969 +// // n=F.tail(e);
6.970 +// // if (residual_capacity.get(e)==augment_value)
6.971 +// // F.erase(e);
6.972 +// // else
6.973 +// // residual_capacity.set(e, residual_capacity.get(e)-augment_value);
6.974 +// // }
6.975 +// // }
6.976 +
6.977 +// // }
6.978 +
6.979 +// // return _augment;
6.980 +// // }
6.981 +// bool augmentOnBlockingFlow2() {
6.982 +// bool _augment=false;
6.983 +
6.984 +// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
6.985 +// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
6.986 +// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
6.987 +// typedef typename EAugGraph::Edge EAugEdge;
6.988 +
6.989 +// EAugGraph res_graph(*G, *flow, *capacity);
6.990 +
6.991 +// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
6.992 +// BfsIterator5<
6.993 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
6.994 +// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
6.995 +// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
6.996 +
6.997 +
6.998 +// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
6.999 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
6.1000 +// if (S->get(s)) {
6.1001 +// Number u=0;
6.1002 +// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
6.1003 +// u+=flow->get(e);
6.1004 +// if (u<1) {
6.1005 +// bfs.pushAndSetReached(s);
6.1006 +// //pred.set(s, AugEdge(INVALID));
6.1007 +// }
6.1008 +// }
6.1009 +// }
6.1010 +
6.1011 +
6.1012 +// //bfs.pushAndSetReached(s);
6.1013 +
6.1014 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
6.1015 +// NodeMap<int>& dist=res_graph.dist;
6.1016 +
6.1017 +// while ( !bfs.finished() ) {
6.1018 +// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
6.1019 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
6.1020 +// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
6.1021 +// }
6.1022 +// ++bfs;
6.1023 +// } //computing distances from s in the residual graph
6.1024 +
6.1025 +// bool __augment=true;
6.1026 +
6.1027 +// while (__augment) {
6.1028 +
6.1029 +// __augment=false;
6.1030 +// //computing blocking flow with dfs
6.1031 +// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
6.1032 +// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
6.1033 +// dfs(res_graph);
6.1034 +// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
6.1035 +// //pred.set(s, EAugEdge(INVALID));
6.1036 +// //invalid iterators for sources
6.1037 +
6.1038 +// typename EAugGraph::NodeMap<Number> free(res_graph);
6.1039 +
6.1040 +
6.1041 +// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
6.1042 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
6.1043 +// if (S->get(s)) {
6.1044 +// Number u=0;
6.1045 +// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
6.1046 +// u+=flow->get(e);
6.1047 +// if (u<1) {
6.1048 +// dfs.pushAndSetReached(s);
6.1049 +// //pred.set(s, AugEdge(INVALID));
6.1050 +// }
6.1051 +// }
6.1052 +// }
6.1053 +
6.1054 +
6.1055 +
6.1056 +// //dfs.pushAndSetReached(s);
6.1057 +// typename EAugGraph::Node n;
6.1058 +// while (!dfs.finished()) {
6.1059 +// ++dfs;
6.1060 +// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
6.1061 +// if (dfs.isBNodeNewlyReached()) {
6.1062 +
6.1063 +// typename EAugGraph::Node v=res_graph.aNode(dfs);
6.1064 +// typename EAugGraph::Node w=res_graph.bNode(dfs);
6.1065 +
6.1066 +// pred.set(w, EAugOutEdgeIt(dfs));
6.1067 +// if (res_graph.valid(pred.get(v))) {
6.1068 +// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
6.1069 +// } else {
6.1070 +// free.set(w, res_graph.free(dfs));
6.1071 +// }
6.1072 +
6.1073 +// n=w;
6.1074 +// if (T->get(w)) {
6.1075 +// Number u=0;
6.1076 +// for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
6.1077 +// u+=flow->get(f);
6.1078 +// if (u<1) {
6.1079 +// __augment=true;
6.1080 +// _augment=true;
6.1081 +// break;
6.1082 +// }
6.1083 +// }
6.1084 +// } else {
6.1085 +// res_graph.erase(dfs);
6.1086 +// }
6.1087 +// }
6.1088 +
6.1089 +// }
6.1090 +
6.1091 +// if (__augment) {
6.1092 +// // typename EAugGraph::Node n=t;
6.1093 +// Number augment_value=free.get(n);
6.1094 +// while (res_graph.valid(pred.get(n))) {
6.1095 +// EAugEdge e=pred.get(n);
6.1096 +// res_graph.augment(e, augment_value);
6.1097 +// n=res_graph.tail(e);
6.1098 +// if (res_graph.free(e)==0)
6.1099 +// res_graph.erase(e);
6.1100 +// }
6.1101 +// }
6.1102 +
6.1103 +// }
6.1104 +
6.1105 +// return _augment;
6.1106 +// }
6.1107 +// void run() {
6.1108 +// //int num_of_augmentations=0;
6.1109 +// while (augmentOnShortestPath()) {
6.1110 +// //while (augmentOnBlockingFlow<MutableGraph>()) {
6.1111 +// //std::cout << ++num_of_augmentations << " ";
6.1112 +// //std::cout<<std::endl;
6.1113 +// }
6.1114 +// }
6.1115 +// // template<typename MutableGraph> void run() {
6.1116 +// // //int num_of_augmentations=0;
6.1117 +// // //while (augmentOnShortestPath()) {
6.1118 +// // while (augmentOnBlockingFlow<MutableGraph>()) {
6.1119 +// // //std::cout << ++num_of_augmentations << " ";
6.1120 +// // //std::cout<<std::endl;
6.1121 +// // }
6.1122 +// // }
6.1123 +// Number flowValue() {
6.1124 +// Number a=0;
6.1125 +// EdgeIt e;
6.1126 +// for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
6.1127 +// a+=flow->get(e);
6.1128 +// }
6.1129 +// return a;
6.1130 +// }
6.1131 +// };
6.1132 +
6.1133 +
6.1134 +
6.1135 +
6.1136 +
6.1137 +
6.1138 +// // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
6.1139 +// // class MaxFlow2 {
6.1140 +// // public:
6.1141 +// // typedef typename Graph::Node Node;
6.1142 +// // typedef typename Graph::Edge Edge;
6.1143 +// // typedef typename Graph::EdgeIt EdgeIt;
6.1144 +// // typedef typename Graph::OutEdgeIt OutEdgeIt;
6.1145 +// // typedef typename Graph::InEdgeIt InEdgeIt;
6.1146 +// // private:
6.1147 +// // const Graph& G;
6.1148 +// // std::list<Node>& S;
6.1149 +// // std::list<Node>& T;
6.1150 +// // FlowMap& flow;
6.1151 +// // const CapacityMap& capacity;
6.1152 +// // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
6.1153 +// // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
6.1154 +// // typedef typename AugGraph::Edge AugEdge;
6.1155 +// // typename Graph::NodeMap<bool> SMap;
6.1156 +// // typename Graph::NodeMap<bool> TMap;
6.1157 +// // public:
6.1158 +// // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
6.1159 +// // for(typename std::list<Node>::const_iterator i=S.begin();
6.1160 +// // i!=S.end(); ++i) {
6.1161 +// // SMap.set(*i, true);
6.1162 +// // }
6.1163 +// // for (typename std::list<Node>::const_iterator i=T.begin();
6.1164 +// // i!=T.end(); ++i) {
6.1165 +// // TMap.set(*i, true);
6.1166 +// // }
6.1167 +// // }
6.1168 +// // bool augment() {
6.1169 +// // AugGraph res_graph(G, flow, capacity);
6.1170 +// // bool _augment=false;
6.1171 +// // Node reached_t_node;
6.1172 +
6.1173 +// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
6.1174 +// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
6.1175 +// // for(typename std::list<Node>::const_iterator i=S.begin();
6.1176 +// // i!=S.end(); ++i) {
6.1177 +// // bfs.pushAndSetReached(*i);
6.1178 +// // }
6.1179 +// // //bfs.pushAndSetReached(s);
6.1180 +
6.1181 +// // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
6.1182 +// // //filled up with invalid iterators
6.1183 +
6.1184 +// // typename AugGraph::NodeMap<Number> free(res_graph);
6.1185 +
6.1186 +// // //searching for augmenting path
6.1187 +// // while ( !bfs.finished() ) {
6.1188 +// // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
6.1189 +// // if (e.valid() && bfs.isBNodeNewlyReached()) {
6.1190 +// // Node v=res_graph.tail(e);
6.1191 +// // Node w=res_graph.head(e);
6.1192 +// // pred.set(w, e);
6.1193 +// // if (pred.get(v).valid()) {
6.1194 +// // free.set(w, std::min(free.get(v), e.free()));
6.1195 +// // } else {
6.1196 +// // free.set(w, e.free());
6.1197 +// // }
6.1198 +// // if (TMap.get(res_graph.head(e))) {
6.1199 +// // _augment=true;
6.1200 +// // reached_t_node=res_graph.head(e);
6.1201 +// // break;
6.1202 +// // }
6.1203 +// // }
6.1204 +
6.1205 +// // ++bfs;
6.1206 +// // } //end of searching augmenting path
6.1207 +
6.1208 +// // if (_augment) {
6.1209 +// // Node n=reached_t_node;
6.1210 +// // Number augment_value=free.get(reached_t_node);
6.1211 +// // while (pred.get(n).valid()) {
6.1212 +// // AugEdge e=pred.get(n);
6.1213 +// // e.augment(augment_value);
6.1214 +// // n=res_graph.tail(e);
6.1215 +// // }
6.1216 +// // }
6.1217 +
6.1218 +// // return _augment;
6.1219 +// // }
6.1220 +// // void run() {
6.1221 +// // while (augment()) { }
6.1222 +// // }
6.1223 +// // Number flowValue() {
6.1224 +// // Number a=0;
6.1225 +// // for(typename std::list<Node>::const_iterator i=S.begin();
6.1226 +// // i!=S.end(); ++i) {
6.1227 +// // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
6.1228 +// // a+=flow.get(e);
6.1229 +// // }
6.1230 +// // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
6.1231 +// // a-=flow.get(e);
6.1232 +// // }
6.1233 +// // }
6.1234 +// // return a;
6.1235 +// // }
6.1236 +// // };
6.1237 +
6.1238 +
6.1239 +} // namespace hugo
6.1240 +
6.1241 +#endif //HUGO_EDMONDS_KARP_H
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/work/marci/iterator_bfs_demo.cc Mon Apr 05 15:02:39 2004 +0000
7.3 @@ -0,0 +1,322 @@
7.4 +// -*- c++ -*-
7.5 +#include <iostream>
7.6 +#include <vector>
7.7 +#include <string>
7.8 +
7.9 +#include <list_graph.h>
7.10 +#include <smart_graph.h>
7.11 +#include <bfs_iterator.h>
7.12 +#include <graph_wrapper.h>
7.13 +
7.14 +using namespace hugo;
7.15 +using std::cout;
7.16 +using std::endl;
7.17 +using std::string;
7.18 +
7.19 +template <typename Graph, typename NodeNameMap>
7.20 +class EdgeNameMap {
7.21 + Graph& graph;
7.22 + NodeNameMap& node_name_map;
7.23 +public:
7.24 + EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
7.25 + graph(_graph), node_name_map(_node_name_map) { }
7.26 + string get(typename Graph::Edge e) const {
7.27 + return
7.28 + (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
7.29 + }
7.30 +};
7.31 +
7.32 +int main (int, char*[])
7.33 +{
7.34 + //typedef SmartGraph Graph;
7.35 + typedef ListGraph Graph;
7.36 +
7.37 + typedef Graph::Node Node;
7.38 + typedef Graph::Edge Edge;
7.39 +
7.40 + Graph G;
7.41 +
7.42 + Node s=G.addNode();
7.43 + Node v1=G.addNode();
7.44 + Node v2=G.addNode();
7.45 + Node v3=G.addNode();
7.46 + Node v4=G.addNode();
7.47 + Node t=G.addNode();
7.48 +
7.49 + Graph::NodeMap<string> node_name(G);
7.50 + node_name.set(s, "s");
7.51 + node_name.set(v1, "v1");
7.52 + node_name.set(v2, "v2");
7.53 + node_name.set(v3, "v3");
7.54 + node_name.set(v4, "v4");
7.55 + node_name.set(t, "t");
7.56 +
7.57 + G.addEdge(s, v1);
7.58 + G.addEdge(s, v2);
7.59 + G.addEdge(v1, v2);
7.60 + G.addEdge(v2, v1);
7.61 + G.addEdge(v1, v3);
7.62 + G.addEdge(v3, v2);
7.63 + G.addEdge(v2, v4);
7.64 + G.addEdge(v4, v3);
7.65 + G.addEdge(v3, t);
7.66 + G.addEdge(v4, t);
7.67 +
7.68 + cout << " /--> -------------> "<< endl;
7.69 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
7.70 + cout << " / | | / /-> \\ "<< endl;
7.71 + cout << " / | | / | ^ \\ "<< endl;
7.72 + cout << "s | | / | | \\-> t "<< endl;
7.73 + cout << " \\ | | / | | /-> "<< endl;
7.74 + cout << " \\ | --/ / | | / "<< endl;
7.75 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
7.76 + cout << " \\--> -------------> "<< endl;
7.77 +
7.78 +// typedef TrivGraphWrapper<const Graph> CGW;
7.79 +// CGW gw(G);
7.80 +
7.81 +// cout << "bfs and dfs demo on the directed graph" << endl;
7.82 +// for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) {
7.83 +// cout << n << ": ";
7.84 +// cout << "out edges: ";
7.85 +// for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
7.86 +// cout << e << " ";
7.87 +// cout << "in edges: ";
7.88 +// for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e)
7.89 +// cout << e << " ";
7.90 +// cout << endl;
7.91 +// }
7.92 +
7.93 + {
7.94 + typedef TrivGraphWrapper<const Graph> GW;
7.95 + GW gw(G);
7.96 +
7.97 + EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
7.98 +
7.99 + cout << "bfs and dfs iterator demo on the directed graph" << endl;
7.100 + for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
7.101 + cout << node_name.get(n) << ": ";
7.102 + cout << "out edges: ";
7.103 + for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
7.104 + cout << edge_name.get(e) << " ";
7.105 + cout << "in edges: ";
7.106 + for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
7.107 + cout << edge_name.get(e) << " ";
7.108 + cout << endl;
7.109 + }
7.110 +
7.111 + cout << "bfs from s ..." << endl;
7.112 + BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
7.113 + bfs.pushAndSetReached(s);
7.114 + while (!bfs.finished()) {
7.115 + //cout << "edge: ";
7.116 + if (gw.valid(bfs)) {
7.117 + cout << edge_name.get(bfs) << /*endl*/", " <<
7.118 + node_name.get(gw.aNode(bfs)) <<
7.119 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.120 + node_name.get(gw.bNode(bfs)) <<
7.121 + (bfs.isBNodeNewlyReached() ? ": is newly reached." :
7.122 + ": is not newly reached.");
7.123 + } else {
7.124 + cout << "invalid" << /*endl*/", " <<
7.125 + node_name.get(bfs.aNode()) <<
7.126 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.127 +
7.128 + "invalid.";
7.129 + }
7.130 + cout << endl;
7.131 + ++bfs;
7.132 + }
7.133 +
7.134 + cout << " /--> -------------> "<< endl;
7.135 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
7.136 + cout << " / | | / /-> \\ "<< endl;
7.137 + cout << " / | | / | ^ \\ "<< endl;
7.138 + cout << "s | | / | | \\-> t "<< endl;
7.139 + cout << " \\ | | / | | /-> "<< endl;
7.140 + cout << " \\ | --/ / | | / "<< endl;
7.141 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
7.142 + cout << " \\--> -------------> "<< endl;
7.143 +
7.144 + cout << "dfs from s ..." << endl;
7.145 + DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
7.146 + dfs.pushAndSetReached(s);
7.147 + while (!dfs.finished()) {
7.148 + ++dfs;
7.149 + //cout << "edge: ";
7.150 + if (gw.valid(dfs)) {
7.151 + cout << edge_name.get(dfs) << /*endl*/", " <<
7.152 + node_name.get(gw.aNode(dfs)) <<
7.153 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.154 + node_name.get(gw.bNode(dfs)) <<
7.155 + (dfs.isBNodeNewlyReached() ? ": is newly reached." :
7.156 + ": is not newly reached.");
7.157 + } else {
7.158 + cout << "invalid" << /*endl*/", " <<
7.159 + node_name.get(dfs.aNode()) <<
7.160 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.161 +
7.162 + "invalid.";
7.163 + }
7.164 + cout << endl;
7.165 + }
7.166 + }
7.167 +
7.168 +
7.169 + {
7.170 + typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW;
7.171 + GW gw(G);
7.172 +
7.173 + EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
7.174 +
7.175 + cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
7.176 + for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
7.177 + cout << node_name.get(n) << ": ";
7.178 + cout << "out edges: ";
7.179 + for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
7.180 + cout << edge_name.get(e) << " ";
7.181 + cout << "in edges: ";
7.182 + for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
7.183 + cout << edge_name.get(e) << " ";
7.184 + cout << endl;
7.185 + }
7.186 +
7.187 + cout << "bfs from t ..." << endl;
7.188 + BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
7.189 + bfs.pushAndSetReached(t);
7.190 + while (!bfs.finished()) {
7.191 + //cout << "edge: ";
7.192 + if (gw.valid(bfs)) {
7.193 + cout << edge_name.get(bfs) << /*endl*/", " <<
7.194 + node_name.get(gw.aNode(bfs)) <<
7.195 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.196 + node_name.get(gw.bNode(bfs)) <<
7.197 + (bfs.isBNodeNewlyReached() ? ": is newly reached." :
7.198 + ": is not newly reached.");
7.199 + } else {
7.200 + cout << "invalid" << /*endl*/", " <<
7.201 + node_name.get(bfs.aNode()) <<
7.202 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.203 +
7.204 + "invalid.";
7.205 + }
7.206 + cout << endl;
7.207 + ++bfs;
7.208 + }
7.209 +
7.210 + cout << " /--> -------------> "<< endl;
7.211 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
7.212 + cout << " / | | / /-> \\ "<< endl;
7.213 + cout << " / | | / | ^ \\ "<< endl;
7.214 + cout << "s | | / | | \\-> t "<< endl;
7.215 + cout << " \\ | | / | | /-> "<< endl;
7.216 + cout << " \\ | --/ / | | / "<< endl;
7.217 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
7.218 + cout << " \\--> -------------> "<< endl;
7.219 +
7.220 + cout << "dfs from t ..." << endl;
7.221 + DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
7.222 + dfs.pushAndSetReached(t);
7.223 + while (!dfs.finished()) {
7.224 + ++dfs;
7.225 + //cout << "edge: ";
7.226 + if (gw.valid(dfs)) {
7.227 + cout << edge_name.get(dfs) << /*endl*/", " <<
7.228 + node_name.get(gw.aNode(dfs)) <<
7.229 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.230 + node_name.get(gw.bNode(dfs)) <<
7.231 + (dfs.isBNodeNewlyReached() ? ": is newly reached." :
7.232 + ": is not newly reached.");
7.233 + } else {
7.234 + cout << "invalid" << /*endl*/", " <<
7.235 + node_name.get(dfs.aNode()) <<
7.236 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.237 +
7.238 + "invalid.";
7.239 + }
7.240 + cout << endl;
7.241 + }
7.242 + }
7.243 +
7.244 + {
7.245 + //typedef UndirGraphWrapper<const Graph> GW;
7.246 + typedef UndirGraphWrapper<const TrivGraphWrapper<const Graph> > GW;
7.247 + GW gw(G);
7.248 +
7.249 + EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
7.250 +
7.251 + cout << "bfs and dfs iterator demo on the undirected graph" << endl;
7.252 + for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
7.253 + cout << node_name.get(n) << ": ";
7.254 + cout << "out edges: ";
7.255 + for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
7.256 + cout << edge_name.get(e) << " ";
7.257 + cout << "in edges: ";
7.258 + for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
7.259 + cout << edge_name.get(e) << " ";
7.260 + cout << endl;
7.261 + }
7.262 +// for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
7.263 +// cout << edge_name.get(e) << " ";
7.264 +// }
7.265 +// cout << endl;
7.266 +
7.267 + cout << "bfs from t ..." << endl;
7.268 + BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
7.269 + bfs.pushAndSetReached(t);
7.270 + while (!bfs.finished()) {
7.271 + //cout << "edge: ";
7.272 + if (gw.valid(GW::OutEdgeIt(bfs))) {
7.273 + cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<
7.274 + node_name.get(gw.aNode(bfs)) <<
7.275 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.276 + node_name.get(gw.bNode(bfs)) <<
7.277 + (bfs.isBNodeNewlyReached() ? ": is newly reached." :
7.278 + ": is not newly reached.");
7.279 + } else {
7.280 + cout << "invalid" << /*endl*/", " <<
7.281 + node_name.get(bfs.aNode()) <<
7.282 + (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.283 +
7.284 + "invalid.";
7.285 + }
7.286 + cout << endl;
7.287 + ++bfs;
7.288 + }
7.289 +
7.290 + cout << " /--> -------------> "<< endl;
7.291 + cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
7.292 + cout << " / | | / /-> \\ "<< endl;
7.293 + cout << " / | | / | ^ \\ "<< endl;
7.294 + cout << "s | | / | | \\-> t "<< endl;
7.295 + cout << " \\ | | / | | /-> "<< endl;
7.296 + cout << " \\ | --/ / | | / "<< endl;
7.297 + cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
7.298 + cout << " \\--> -------------> "<< endl;
7.299 +
7.300 + cout << "dfs from t ..." << endl;
7.301 + DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
7.302 + dfs.pushAndSetReached(t);
7.303 + while (!dfs.finished()) {
7.304 + ++dfs;
7.305 + //cout << "edge: ";
7.306 + if (gw.valid(GW::OutEdgeIt(dfs))) {
7.307 + cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<
7.308 + node_name.get(gw.aNode(dfs)) <<
7.309 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.310 + node_name.get(gw.bNode(dfs)) <<
7.311 + (dfs.isBNodeNewlyReached() ? ": is newly reached." :
7.312 + ": is not newly reached.");
7.313 + } else {
7.314 + cout << "invalid" << /*endl*/", " <<
7.315 + node_name.get(dfs.aNode()) <<
7.316 + (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
7.317 +
7.318 + "invalid.";
7.319 + }
7.320 + cout << endl;
7.321 + }
7.322 + }
7.323 +
7.324 + return 0;
7.325 +}