1.1 --- a/src/work/marci/augmenting_flow.h Wed Oct 13 15:52:35 2004 +0000
1.2 +++ b/src/work/marci/augmenting_flow.h Sat Oct 16 00:20:13 2004 +0000
1.3 @@ -6,16 +6,19 @@
1.4 #include <iostream>
1.5
1.6 #include <lemon/graph_wrapper.h>
1.7 -#include <bfs_dfs.h>
1.8 +//#include <bfs_dfs.h>
1.9 +#include <bfs_mm.h>
1.10 #include <lemon/invalid.h>
1.11 #include <lemon/maps.h>
1.12 -#include <lemon/tight_edge_filter_map.h>
1.13 +#include <demo/tight_edge_filter_map.h>
1.14
1.15 /// \file
1.16 /// \brief Maximum flow algorithms.
1.17 /// \ingroup galgs
1.18
1.19 namespace lemon {
1.20 + using lemon::marci::BfsIterator;
1.21 + using lemon::marci::DfsIterator;
1.22
1.23 /// \addtogroup galgs
1.24 /// @{
1.25 @@ -109,6 +112,8 @@
1.26 IntMap* map;
1.27 int* number_of_augmentations;
1.28 public:
1.29 + typedef Node KeyType;
1.30 + typedef bool ValueType;
1.31 TrickyReachedMap(IntMap& _map, int& _number_of_augmentations) :
1.32 map(&_map), number_of_augmentations(&_number_of_augmentations) { }
1.33 void set(const Node& n, bool b) {
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/marci/bfs_mm.h Sat Oct 16 00:20:13 2004 +0000
2.3 @@ -0,0 +1,559 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef LEMON_BFS_DFS_H
2.6 +#define LEMON_BFS_DFS_H
2.7 +
2.8 +/// \ingroup galgs
2.9 +/// \file
2.10 +/// \brief Bfs and dfs iterators.
2.11 +///
2.12 +/// This file contains bfs and dfs iterator classes.
2.13 +///
2.14 +// /// \author Marton Makai
2.15 +
2.16 +#include <queue>
2.17 +#include <stack>
2.18 +#include <utility>
2.19 +
2.20 +#include <lemon/invalid.h>
2.21 +
2.22 +namespace lemon {
2.23 + namespace marci {
2.24 +
2.25 + /// Bfs searches for the nodes wich are not marked in
2.26 + /// \c reached_map
2.27 + /// RM have to be a read-write bool node-map.
2.28 + /// \ingroup galgs
2.29 + template <typename Graph, /*typename OutEdgeIt,*/
2.30 + typename RM/*=typename Graph::NodeMap<bool>*/ >
2.31 + class BfsIterator {
2.32 + public:
2.33 + typedef RM ReachedMap;
2.34 + protected:
2.35 + typedef typename Graph::Node Node;
2.36 + typedef typename Graph::Edge Edge;
2.37 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.38 + const Graph* graph;
2.39 + std::queue<Node> bfs_queue;
2.40 + ReachedMap* reached_map;
2.41 + bool b_node_newly_reached;
2.42 + //OutEdgeIt actual_edge;
2.43 + Edge actual_edge;
2.44 + /// \e
2.45 + BfsIterator(const Graph& _graph) : graph(&_graph), reached_map(0) { }
2.46 + /// RM have to be set before any bfs operation.
2.47 + BfsIterator<Graph, RM>& setReached(RM& _reached_map) {
2.48 + reached_map=&_reached_map;
2.49 + }
2.50 + public:
2.51 + /// In that constructor \c _reached_map have to be a reference
2.52 + /// for a bool bode-map. The algorithm will search for the
2.53 + /// initially \c false nodes
2.54 + /// in a bfs order.
2.55 + BfsIterator(const Graph& _graph, ReachedMap& _reached_map) :
2.56 + graph(&_graph), reached_map(&_reached_map) { }
2.57 + /// The same as above, but the map storing the reached nodes
2.58 + /// is constructed dynamically to everywhere false.
2.59 + /// \deprecated
2.60 +// BfsIterator(const Graph& _graph) :
2.61 +// graph(&_graph), reached_map(new ReachedMap(*graph /*, false*/)),
2.62 +// own_reached_map(true) { }
2.63 +// /// The map storing the reached nodes have to be destroyed if
2.64 +// /// it was constructed dynamically
2.65 +// ~BfsIterator() { if (own_reached_map) delete reached_map; }
2.66 + /// This method markes \c s reached.
2.67 + /// If the queue is empty, then \c s is pushed in the bfs queue
2.68 + /// and the first out-edge is processed.
2.69 + /// If the queue is not empty, then \c s is simply pushed.
2.70 + BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
2.71 + reached_map->set(s, true);
2.72 + if (bfs_queue.empty()) {
2.73 + bfs_queue.push(s);
2.74 + actual_edge=OutEdgeIt(*graph, s);
2.75 + //graph->first(actual_edge, s);
2.76 + if (actual_edge!=INVALID) {
2.77 + Node w=graph->head(actual_edge);
2.78 + if (!(*reached_map)[w]) {
2.79 + bfs_queue.push(w);
2.80 + reached_map->set(w, true);
2.81 + b_node_newly_reached=true;
2.82 + } else {
2.83 + b_node_newly_reached=false;
2.84 + }
2.85 + }
2.86 + } else {
2.87 + bfs_queue.push(s);
2.88 + }
2.89 + return *this;
2.90 + }
2.91 + /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
2.92 + /// its \c operator++() iterates on the edges in a bfs order.
2.93 + BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
2.94 + operator++() {
2.95 + if (actual_edge!=INVALID) {
2.96 + actual_edge=++OutEdgeIt(*graph, actual_edge);
2.97 + //++actual_edge;
2.98 + if (actual_edge!=INVALID) {
2.99 + Node w=graph->head(actual_edge);
2.100 + if (!(*reached_map)[w]) {
2.101 + bfs_queue.push(w);
2.102 + reached_map->set(w, true);
2.103 + b_node_newly_reached=true;
2.104 + } else {
2.105 + b_node_newly_reached=false;
2.106 + }
2.107 + }
2.108 + } else {
2.109 + bfs_queue.pop();
2.110 + if (!bfs_queue.empty()) {
2.111 + actual_edge=OutEdgeIt(*graph, bfs_queue.front());
2.112 + //graph->first(actual_edge, bfs_queue.front());
2.113 + if (actual_edge!=INVALID) {
2.114 + Node w=graph->head(actual_edge);
2.115 + if (!(*reached_map)[w]) {
2.116 + bfs_queue.push(w);
2.117 + reached_map->set(w, true);
2.118 + b_node_newly_reached=true;
2.119 + } else {
2.120 + b_node_newly_reached=false;
2.121 + }
2.122 + }
2.123 + }
2.124 + }
2.125 + return *this;
2.126 + }
2.127 + /// Returns true iff the algorithm is finished.
2.128 + bool finished() const { return bfs_queue.empty(); }
2.129 + /// The conversion operator makes for converting the bfs-iterator
2.130 + /// to an \c out-edge-iterator.
2.131 + ///\bug Edge have to be in LEMON 0.2
2.132 + operator Edge() const { return actual_edge; }
2.133 + /// Returns if b-node has been reached just now.
2.134 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
2.135 + /// Returns if a-node is examined.
2.136 + bool isANodeExamined() const { return actual_edge==INVALID; }
2.137 + /// Returns a-node of the actual edge, so does if the edge is invalid.
2.138 + Node tail() const { return bfs_queue.front(); }
2.139 + /// \pre The actual edge have to be valid.
2.140 + Node head() const { return graph->head(actual_edge); }
2.141 + /// Guess what?
2.142 + /// \deprecated
2.143 + const ReachedMap& reachedMap() const { return *reached_map; }
2.144 + /// Guess what?
2.145 + /// \deprecated
2.146 + typename ReachedMap::ValueType reached(const Node& n) const {
2.147 + return (*reached_map)[n];
2.148 + }
2.149 + /// Guess what?
2.150 + /// \deprecated
2.151 + const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
2.152 + };
2.153 +
2.154 + /// Bfs searches for the nodes wich are not marked in
2.155 + /// \c reached_map
2.156 + /// RM have to work as a read-write bool Node-map,
2.157 + /// PM is a write edge node-map and
2.158 + /// PNM is a write node node-map and
2.159 + /// DM is a read-write node-map of integral value, have to be.
2.160 + /// \ingroup galgs
2.161 + template <typename Graph,
2.162 + typename RM=typename Graph::template NodeMap<bool>,
2.163 + typename PM
2.164 + =typename Graph::template NodeMap<typename Graph::Edge>,
2.165 + typename PNM
2.166 + =typename Graph::template NodeMap<typename Graph::Node>,
2.167 + typename DM=typename Graph::template NodeMap<int> >
2.168 + class Bfs : public BfsIterator<Graph, RM> {
2.169 + typedef BfsIterator<Graph, RM> Parent;
2.170 + public:
2.171 + typedef RM ReachedMap;
2.172 + typedef PM PredMap;
2.173 + typedef PNM PredNodeMap;
2.174 + typedef DM DistMap;
2.175 + protected:
2.176 + typedef typename Parent::Node Node;
2.177 + PredMap* pred_map;
2.178 + PredNodeMap* pred_node_map;
2.179 + DistMap* dist_map;
2.180 + /// \e
2.181 + Bfs<Graph, RM, PM, PNM, DM>
2.182 + (const Graph& _graph) : BfsIterator<Graph, RM>(_graph) { }
2.183 + /// PM have to be set before any bfs operation.
2.184 + Bfs<Graph, RM, PM, PNM, DM>&
2.185 + setPredMap(PredMap& _pred_map) {
2.186 + pred_map=&_pred_map;
2.187 + }
2.188 + /// PredNodeMap have to be set before any bfs operation.
2.189 + Bfs<Graph, RM, PM, PNM, DM>&
2.190 + setPredNodeMap(PredNodeMap& _pred_node_map) {
2.191 + pred_node_map=&_pred_node_map;
2.192 + }
2.193 + /// DistMap have to be set before any bfs operation.
2.194 + Bfs<Graph, RM, PM, PNM, DM>&
2.195 + setDistMap(DistMap& _dist_map) {
2.196 + dist_map=&_dist_map;
2.197 + }
2.198 + public:
2.199 + /// The algorithm will search in a bfs order for
2.200 + /// the nodes which are \c false initially.
2.201 + /// The constructor makes no initial changes on the maps.
2.202 + Bfs<Graph, RM, PM, PNM, DM>
2.203 + (const Graph& _graph, ReachedMap& _reached_map,
2.204 + PredMap& _pred_map, PredNodeMap& _pred_node_map,
2.205 + DistMap& _dist_map) : BfsIterator<Graph, RM>(_graph, _reached_map),
2.206 + pred_map(&_pred_map), pred_node_map(&_pred_node_map),
2.207 + dist_map(&_dist_map) { }
2.208 + /// \c s is marked to be reached and pushed in the bfs queue.
2.209 + /// If the queue is empty, then the first out-edge is processed.
2.210 + /// If \c s was not marked previously, then
2.211 + /// in addition its pred_map is set to be \c INVALID,
2.212 + /// and dist_map to \c 0.
2.213 + /// if \c s was marked previuosly, then it is simply pushed.
2.214 + Bfs<Graph, RM, PM, PNM, DM>& push(Node s) {
2.215 + if ((*(this->reached_map))[s]) {
2.216 + Parent::pushAndSetReached(s);
2.217 + } else {
2.218 + Parent::pushAndSetReached(s);
2.219 + pred_map->set(s, INVALID);
2.220 + pred_node_map->set(s, INVALID);
2.221 + dist_map->set(s, 0);
2.222 + }
2.223 + return *this;
2.224 + }
2.225 + /// A bfs is processed from \c s.
2.226 + Bfs<Graph, RM, PM, PNM, DM>& run(Node s) {
2.227 + push(s);
2.228 + while (!this->finished()) this->operator++();
2.229 + return *this;
2.230 + }
2.231 + /// Beside the bfs iteration, \c pred_map and \dist_map are saved in a
2.232 + /// newly reached node.
2.233 + Bfs<Graph, RM, PM, PNM, DM>& operator++() {
2.234 + Parent::operator++();
2.235 + if ((this->actual_edge)!=INVALID && this->b_node_newly_reached)
2.236 + {
2.237 + pred_map->set(this->head(), this->actual_edge);
2.238 + pred_node_map->set(this->head(), this->tail());
2.239 + dist_map->set(this->head(), (*dist_map)[this->tail()]);
2.240 + }
2.241 + return *this;
2.242 + }
2.243 + /// Guess what?
2.244 + /// \deprecated
2.245 + const PredMap& predMap() const { return *pred_map; }
2.246 + /// Guess what?
2.247 + /// \deprecated
2.248 + typename PredMap::ValueType pred(const Node& n) const {
2.249 + return (*pred_map)[n];
2.250 + }
2.251 + /// Guess what?
2.252 + /// \deprecated
2.253 + const PredNodeMap& predNodeMap() const { return *pred_node_map; }
2.254 + /// Guess what?
2.255 + /// \deprecated
2.256 + typename PredNodeMap::ValueType predNode(const Node& n) const {
2.257 + return (*pred_node_map)[n];
2.258 + }
2.259 + /// Guess what?
2.260 + /// \deprecated
2.261 + const DistMap& distMap() const { return *dist_map; }
2.262 + /// Guess what?
2.263 + /// \deprecated
2.264 + typename DistMap::ValueType dist(const Node& n) const {
2.265 + return (*dist_map)[n];
2.266 + }
2.267 + };
2.268 +
2.269 +// template <typename Graph,
2.270 +// typename RM=typename Graph::template NodeMap<bool>,
2.271 +// typename PM
2.272 +// =typename Graph::template NodeMap<typename Graph::Edge>,
2.273 +// typename PredNodeMap
2.274 +// =typename Graph::template NodeMap<typename Graph::Node>,
2.275 +// typename DistMap=typename Graph::template NodeMap<int> >
2.276 +// class BfsWizard : public Bfs<Graph> {
2.277 +// public:
2.278 +// typedef Bfs<Graph, PM, PredNodeMap, DistMap> Parent;
2.279 +// protected:
2.280 +// typedef typename Parent::Node Node;
2.281 +// bool own_reached_map;
2.282 +// bool own_pred_map;
2.283 +// bool own_pred_node_map;
2.284 +// bool own_dist_map;
2.285 +
2.286 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.287 +// makeRreached() {
2.288 +// own_reached_map=true;
2.289 +// reached=new ReachedMap(*graph, false);
2.290 +// }
2.291 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.292 +// deleteReachedMap() {
2.293 +// own_reached_map=false;
2.294 +// delete reached;
2.295 +// }
2.296 +
2.297 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.298 +// makePM() {
2.299 +// own_pred_map=true;
2.300 +// pred_map=new PM(*graph, INVALID);
2.301 +// }
2.302 +// BfsWizard<Graph, ReachedMap, PM, PredNodeMap, DistMap>&
2.303 +// deletePM() {
2.304 +// own_pred_map=false;
2.305 +// delete pred_map;
2.306 +// }
2.307 +
2.308 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.309 +// makePredNodeMap() {
2.310 +// own_pred_node_map=true;
2.311 +// pred_node_map=new PredNodeMap(*graph, INVALID);
2.312 +// }
2.313 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.314 +// deletePredNodeMap() {
2.315 +// own_pred_node_map=false;
2.316 +// delete pred_node_map;
2.317 +// }
2.318 +
2.319 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.320 +// makeDistMap() {
2.321 +// own_dist_map=true;
2.322 +// dist_map=new DistMap(*graph, 0);
2.323 +// }
2.324 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.325 +// deleteDistMap() {
2.326 +// own_dist_map=false;
2.327 +// delete dist_map;
2.328 +// }
2.329 +
2.330 +// public:
2.331 +// /// User friendly Bfs class.
2.332 +// /// The maps which are not explicitly given by the user are
2.333 +// /// constructed with false, INVALID, INVALID and 0 values.
2.334 +// /// For the user defined maps, the values are not modified, and
2.335 +// /// the bfs is processed without any preset on maps. Therefore,
2.336 +// /// the bfs will search only the nodes which are set false previously
2.337 +// /// in reached, and in the nodes wich are not newly reached by the
2.338 +// /// search, the map values are not modified.
2.339 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>
2.340 +// (const Graph& _graph) :
2.341 +// own_reached_map(false),
2.342 +// own_pred_map(false),
2.343 +// own_pred_node_map(false),
2.344 +// own_dist_map(false) {
2.345 +// }
2.346 +
2.347 +// /// \e
2.348 +// ~BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>() {
2.349 +// if (own_reached_map) deleteReachedMap();
2.350 +// if (own_pred_map) deletePM();
2.351 +// if (own_pred_node_map) deletePredNodeMap();
2.352 +// if (own_dist_map) deleteDistMap();
2.353 +// }
2.354 +
2.355 +// /// \e
2.356 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.357 +// setReachedMap(ReachedMap& _reached) {
2.358 +// if (own_reached_map) deleteReachedMap();
2.359 +// Parent::setReachedMap(_reached);
2.360 +// }
2.361 +// /// \e
2.362 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.363 +// setPM(PM& _pred) {
2.364 +// if (own_pred_map) deletePM();
2.365 +// Parent::setPM(_pred);
2.366 +// }
2.367 +// /// \e
2.368 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.369 +// setPredNodeMap(PredNodeMap& _pred_node) {
2.370 +// if (own_pred_node_map) deletePredNodeMap();
2.371 +// Parent::setPredNodeMap(_pred_node);
2.372 +// }
2.373 +// /// \e
2.374 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.375 +// setDistMap(DistMap& _dist) {
2.376 +// if (own_dist_map) deleteDistMap();
2.377 +// Parent::setDistMap(_dist);
2.378 +// }
2.379 +
2.380 +// /// \e
2.381 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.382 +// push(Node s) {
2.383 +// if (!reached) makeReachedMap();
2.384 +// if (!pred_map) makePMMap();
2.385 +// if (!pred_node_map) makePredNodeMap();
2.386 +// if (!dist_map) makeDistMap();
2.387 +// push(s);
2.388 +// return *this;
2.389 +// }
2.390 +
2.391 +// /// \e
2.392 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.393 +// operator++() {
2.394 +// if (!reached) makeRM();
2.395 +// if (!pred_map) makePMMap();
2.396 +// if (!pred_node_map) makePredNodeMap();
2.397 +// if (!dist_map) makeDistMap();
2.398 +// ++(*this);
2.399 +// return *this;
2.400 +// }
2.401 +
2.402 +// /// \e
2.403 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
2.404 +// run(Node s) {
2.405 +// if (!reached) makeRM();
2.406 +// if (!pred_map) makePMMap();
2.407 +// if (!pred_node_map) makePredNodeMap();
2.408 +// if (!dist_map) makeDistMap();
2.409 +// run(s);
2.410 +// return *this;
2.411 +// }
2.412 +
2.413 +// };
2.414 +
2.415 +
2.416 + /// Dfs searches for the nodes wich are not marked in
2.417 + /// \c reached_map
2.418 + /// Reached have to be a read-write bool Node-map.
2.419 + /// \ingroup galgs
2.420 + template <typename Graph, /*typename OutEdgeIt,*/
2.421 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
2.422 + class DfsIterator {
2.423 + protected:
2.424 + typedef typename Graph::Node Node;
2.425 + typedef typename Graph::Edge Edge;
2.426 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.427 + const Graph* graph;
2.428 + std::stack<OutEdgeIt> dfs_stack;
2.429 + bool b_node_newly_reached;
2.430 + Edge actual_edge;
2.431 + Node actual_node;
2.432 + ReachedMap& reached;
2.433 + bool own_reached_map;
2.434 + public:
2.435 + /// In that constructor \c _reached have to be a reference
2.436 + /// for a bool node-map. The algorithm will search in a dfs order for
2.437 + /// the nodes which are \c false initially
2.438 + DfsIterator(const Graph& _graph, ReachedMap& _reached) :
2.439 + graph(&_graph), reached(_reached),
2.440 + own_reached_map(false) { }
2.441 + /// The same as above, but the map of reached nodes is
2.442 + /// constructed dynamically
2.443 + /// to everywhere false.
2.444 + DfsIterator(const Graph& _graph) :
2.445 + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
2.446 + own_reached_map(true) { }
2.447 + ~DfsIterator() { if (own_reached_map) delete &reached; }
2.448 + /// This method markes s reached and first out-edge is processed.
2.449 + DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
2.450 + actual_node=s;
2.451 + reached.set(s, true);
2.452 + OutEdgeIt e(*graph, s);
2.453 + //graph->first(e, s);
2.454 + dfs_stack.push(e);
2.455 + return *this;
2.456 + }
2.457 + /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
2.458 + /// its \c operator++() iterates on the edges in a dfs order.
2.459 + DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
2.460 + operator++() {
2.461 + actual_edge=dfs_stack.top();
2.462 + if (actual_edge!=INVALID/*.valid()*/) {
2.463 + Node w=graph->head(actual_edge);
2.464 + actual_node=w;
2.465 + if (!reached[w]) {
2.466 + OutEdgeIt e(*graph, w);
2.467 + //graph->first(e, w);
2.468 + dfs_stack.push(e);
2.469 + reached.set(w, true);
2.470 + b_node_newly_reached=true;
2.471 + } else {
2.472 + actual_node=graph->tail(actual_edge);
2.473 + ++dfs_stack.top();
2.474 + b_node_newly_reached=false;
2.475 + }
2.476 + } else {
2.477 + //actual_node=G.aNode(dfs_stack.top());
2.478 + dfs_stack.pop();
2.479 + }
2.480 + return *this;
2.481 + }
2.482 + /// Returns true iff the algorithm is finished.
2.483 + bool finished() const { return dfs_stack.empty(); }
2.484 + /// The conversion operator makes for converting the bfs-iterator
2.485 + /// to an \c out-edge-iterator.
2.486 + ///\bug Edge have to be in LEMON 0.2
2.487 + operator Edge() const { return actual_edge; }
2.488 + /// Returns if b-node has been reached just now.
2.489 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
2.490 + /// Returns if a-node is examined.
2.491 + bool isANodeExamined() const { return actual_edge==INVALID; }
2.492 + /// Returns a-node of the actual edge, so does if the edge is invalid.
2.493 + Node tail() const { return actual_node; /*FIXME*/}
2.494 + /// Returns b-node of the actual edge.
2.495 + /// \pre The actual edge have to be valid.
2.496 + Node head() const { return graph->head(actual_edge); }
2.497 + /// Guess what?
2.498 + /// \deprecated
2.499 + const ReachedMap& getReachedMap() const { return reached; }
2.500 + /// Guess what?
2.501 + /// \deprecated
2.502 + const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
2.503 + };
2.504 +
2.505 + /// Dfs searches for the nodes wich are not marked in
2.506 + /// \c reached_map
2.507 + /// Reached is a read-write bool node-map,
2.508 + /// Pred is a write node-map, have to be.
2.509 + /// \ingroup galgs
2.510 + template <typename Graph,
2.511 + typename ReachedMap=typename Graph::template NodeMap<bool>,
2.512 + typename PredMap
2.513 + =typename Graph::template NodeMap<typename Graph::Edge> >
2.514 + class Dfs : public DfsIterator<Graph, ReachedMap> {
2.515 + typedef DfsIterator<Graph, ReachedMap> Parent;
2.516 + protected:
2.517 + typedef typename Parent::Node Node;
2.518 + PredMap& pred;
2.519 + public:
2.520 + /// The algorithm will search in a dfs order for
2.521 + /// the nodes which are \c false initially.
2.522 + /// The constructor makes no initial changes on the maps.
2.523 + Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
2.524 + /// \c s is marked to be reached and pushed in the bfs queue.
2.525 + /// If the queue is empty, then the first out-edge is processed.
2.526 + /// If \c s was not marked previously, then
2.527 + /// in addition its pred is set to be \c INVALID.
2.528 + /// if \c s was marked previuosly, then it is simply pushed.
2.529 + Dfs<Graph, ReachedMap, PredMap>& push(Node s) {
2.530 + if (this->reached[s]) {
2.531 + Parent::pushAndSetReached(s);
2.532 + } else {
2.533 + Parent::pushAndSetReached(s);
2.534 + pred.set(s, INVALID);
2.535 + }
2.536 + return *this;
2.537 + }
2.538 + /// A bfs is processed from \c s.
2.539 + Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
2.540 + push(s);
2.541 + while (!this->finished()) this->operator++();
2.542 + return *this;
2.543 + }
2.544 + /// Beside the dfs iteration, \c pred is saved in a
2.545 + /// newly reached node.
2.546 + Dfs<Graph, ReachedMap, PredMap>& operator++() {
2.547 + Parent::operator++();
2.548 + if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
2.549 + {
2.550 + pred.set(this->head(), this->actual_edge);
2.551 + }
2.552 + return *this;
2.553 + }
2.554 + /// Guess what?
2.555 + /// \deprecated
2.556 + const PredMap& getPredMap() const { return pred; }
2.557 + };
2.558 +
2.559 + } // namespace marci
2.560 +} // namespace lemon
2.561 +
2.562 +#endif //LEMON_BFS_DFS_H
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/marci/bfs_mm_test.cc Sat Oct 16 00:20:13 2004 +0000
3.3 @@ -0,0 +1,114 @@
3.4 +/* -*- C++ -*-
3.5 + * src/test/bfs_test.cc - Part of LEMON, a generic C++ optimization library
3.6 + *
3.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
3.9 + *
3.10 + * Permission to use, modify and distribute this software is granted
3.11 + * provided that this copyright notice appears in all copies. For
3.12 + * precise terms see the accompanying LICENSE file.
3.13 + *
3.14 + * This software is provided "AS IS" with no warranty of any kind,
3.15 + * express or implied, and with no claim as to its suitability for any
3.16 + * purpose.
3.17 + *
3.18 + */
3.19 +
3.20 +#include <test/test_tools.h>
3.21 +#include <lemon/smart_graph.h>
3.22 +#include <bfs_mm.h>
3.23 +#include <lemon/skeletons/graph.h>
3.24 +
3.25 +using namespace lemon;
3.26 +
3.27 +const int PET_SIZE =5;
3.28 +
3.29 +
3.30 +void check_Bfs_Compile()
3.31 +{
3.32 + typedef skeleton::StaticGraph Graph;
3.33 +
3.34 + typedef Graph::Edge Edge;
3.35 + typedef Graph::Node Node;
3.36 + typedef Graph::EdgeIt EdgeIt;
3.37 + typedef Graph::NodeIt NodeIt;
3.38 +
3.39 + typedef marci::Bfs<Graph> BType;
3.40 +
3.41 + Graph G;
3.42 + Node n;
3.43 + Edge e;
3.44 + int l;
3.45 + bool b;
3.46 + BType::DistMap d(G);
3.47 + BType::PredMap p(G);
3.48 + BType::PredNodeMap pn(G);
3.49 +
3.50 + Graph::NodeMap<bool> reached(G);
3.51 + Graph::NodeMap<Edge> pred(G);
3.52 + Graph::NodeMap<Node> pred_node(G);
3.53 + Graph::NodeMap<int> dist(G);
3.54 + BType bfs_test(G, reached, pred, pred_node, dist);
3.55 +
3.56 + bfs_test.run(n);
3.57 +
3.58 + l = bfs_test.dist(n);
3.59 + e = bfs_test.pred(n);
3.60 + n = bfs_test.predNode(n);
3.61 + d = bfs_test.distMap();
3.62 + p = bfs_test.predMap();
3.63 + pn = bfs_test.predNodeMap();
3.64 + b = bfs_test.reached(n);
3.65 +
3.66 +}
3.67 +
3.68 +int main()
3.69 +{
3.70 +
3.71 + typedef SmartGraph Graph;
3.72 +
3.73 + typedef Graph::Edge Edge;
3.74 + typedef Graph::Node Node;
3.75 + typedef Graph::EdgeIt EdgeIt;
3.76 + typedef Graph::NodeIt NodeIt;
3.77 + typedef Graph::EdgeMap<int> LengthMap;
3.78 +
3.79 + Graph G;
3.80 + Node s, t;
3.81 + PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
3.82 +
3.83 + s=ps.outer[2];
3.84 + t=ps.inner[0];
3.85 +
3.86 + Graph::NodeMap<bool> reached(G);
3.87 + Graph::NodeMap<Edge> pred(G);
3.88 + Graph::NodeMap<Node> pred_node(G);
3.89 + Graph::NodeMap<int> dist(G);
3.90 + marci::Bfs<Graph> bfs_test(G, reached, pred, pred_node, dist);
3.91 + bfs_test.run(s);
3.92 +
3.93 +// check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
3.94 +
3.95 +
3.96 +// for(EdgeIt e(G); e==INVALID; ++e) {
3.97 +// Node u=G.tail(e);
3.98 +// Node v=G.head(e);
3.99 +// check( !bfs_test.reached(u) ||
3.100 +// (bfs_test.dist(v) > bfs_test.dist(u)+1),
3.101 +// "Wrong output.");
3.102 +// }
3.103 +
3.104 +// for(NodeIt v(G); v==INVALID; ++v) {
3.105 +// check(bfs_test.reached(v),"Each node should be reached.");
3.106 +// if ( bfs_test.pred(v)!=INVALID ) {
3.107 +// Edge e=bfs_test.pred(v);
3.108 +// Node u=G.tail(e);
3.109 +// check(u==bfs_test.predNode(v),"Wrong tree.");
3.110 +// check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
3.111 +// "Wrong distance. Difference: "
3.112 +// << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
3.113 +// - 1));
3.114 +// }
3.115 +// }
3.116 +}
3.117 +
4.1 --- a/src/work/marci/bfsit_vs_byhand.cc Wed Oct 13 15:52:35 2004 +0000
4.2 +++ b/src/work/marci/bfsit_vs_byhand.cc Sat Oct 16 00:20:13 2004 +0000
4.3 @@ -2,12 +2,14 @@
4.4 #include <iostream>
4.5 #include <fstream>
4.6
4.7 -#include <sage_graph.h>
4.8 +//#include <sage_graph.h>
4.9 #include <lemon/smart_graph.h>
4.10 +#include <lemon/list_graph.h>
4.11 #include <lemon/dimacs.h>
4.12 #include <lemon/time_measure.h>
4.13 //#include <lemon/for_each_macros.h>
4.14 -#include <bfs_dfs.h>
4.15 +#include <bfs_mm.h>
4.16 +#include <lemon/bfs.h>
4.17
4.18 using namespace lemon;
4.19
4.20 @@ -15,7 +17,9 @@
4.21 using std::endl;
4.22
4.23 int main() {
4.24 - typedef SageGraph Graph;
4.25 + // typedef SageGraph Graph;
4.26 + typedef SmartGraph Graph ;
4.27 + //typedef ListGraph Graph;
4.28 typedef Graph::Node Node;
4.29 typedef Graph::NodeIt NodeIt;
4.30 typedef Graph::Edge Edge;
4.31 @@ -23,12 +27,8 @@
4.32 typedef Graph::OutEdgeIt OutEdgeIt;
4.33
4.34 Graph g;
4.35 - //Node s;
4.36 - //Graph::EdgeMap<int> cap(g);
4.37 - //readDimacsMaxFlow(std::cin, g, s, t, cap);
4.38 readDimacs(std::cin, g);
4.39 - NodeIt s;
4.40 - g.first(s);
4.41 + NodeIt s(g);
4.42
4.43 cout << g.nodeNum() << endl;
4.44 cout << g.edgeNum() << endl;
4.45 @@ -36,8 +36,9 @@
4.46 Graph::NodeMap<Edge> pred(g);
4.47 cout << "iteration time of bfs written by hand..." << endl;
4.48 Timer ts;
4.49 + ts.reset();
4.50 + for (int i=0; i<100; ++i)
4.51 {
4.52 - ts.reset();
4.53 Graph::NodeMap<bool> reached(g);
4.54 reached.set(s, true);
4.55 pred.set(s, INVALID);
4.56 @@ -46,8 +47,7 @@
4.57 while (!bfs_queue.empty()) {
4.58 Node v=bfs_queue.front();
4.59 bfs_queue.pop();
4.60 - OutEdgeIt e;
4.61 - for(g.first(e,v); g.valid(e); g.next(e)) {
4.62 + for(OutEdgeIt e(g,v); e!=INVALID; ++e) {
4.63 Node w=g.head(e);
4.64 if (!reached[w]) {
4.65 bfs_queue.push(w);
4.66 @@ -56,23 +56,35 @@
4.67 }
4.68 }
4.69 }
4.70 -
4.71 - std::cout << ts << std::endl;
4.72 }
4.73 + std::cout << ts << std::endl;
4.74
4.75 cout << "iteration time with bfs iterator..." << endl;
4.76 + ts.reset();
4.77 + for (int i=0; i<100; ++i)
4.78 {
4.79 - ts.reset();
4.80 - BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
4.81 + Graph::NodeMap<bool> reached(g);
4.82 + marci::BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g, reached);
4.83 bfs.pushAndSetReached(s);
4.84 pred.set(s, INVALID);
4.85 while (!bfs.finished()) {
4.86 ++bfs;
4.87 - if (g.valid(bfs) && bfs.isBNodeNewlyReached())
4.88 + if (Graph::Edge(bfs)!=INVALID && bfs.isBNodeNewlyReached())
4.89 pred.set(bfs.head(), Graph::Edge(bfs));
4.90 }
4.91 - std::cout << ts << std::endl;
4.92 }
4.93 + std::cout << ts << std::endl;
4.94 +
4.95 + cout << "iteration time with bfs aplar..." << endl;
4.96 + ts.reset();
4.97 + for (int i=0; i<100; ++i)
4.98 + {
4.99 + Bfs<Graph> bfs(g);
4.100 + bfs.setPredMap(pred);
4.101 + bfs.run(s);
4.102 + }
4.103 + std::cout << ts << std::endl;
4.104 +
4.105
4.106 return 0;
4.107 }
5.1 --- a/src/work/marci/makefile Wed Oct 13 15:52:35 2004 +0000
5.2 +++ b/src/work/marci/makefile Sat Oct 16 00:20:13 2004 +0000
5.3 @@ -4,7 +4,7 @@
5.4 INCLUDEDIRS ?= -I../{jacint,marci,alpar,klao,akos,athos} -I../.. -I.. -I$(BOOSTROOT)
5.5
5.6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
5.7 -BINARIES = merge_node_graph_wrapper_test#sub_graph_wrapper_demo.cc graph_wrapper_time max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7 proba10
5.8 +BINARIES = bfsit_vs_byhand max_flow_demo bfs_mm_test#merge_node_graph_wrapper_test sub_graph_wrapper_demo.cc graph_wrapper_time iterator_bfs_demo macro_test lg_vs_sg_vs_sg bipartite_graph_wrapper_test bipartite_matching_demo top_sort_test max_flow_1 proba7 proba10
5.9 #BINARIES = preflow_bug
5.10 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
5.11