1.1 --- a/src/work/jacint/max_flow.h Mon May 10 16:52:51 2004 +0000
1.2 +++ b/src/work/jacint/max_flow.h Mon May 10 16:59:20 2004 +0000
1.3 @@ -44,7 +44,7 @@
1.4 #include <stack>
1.5
1.6 #include <hugo/graph_wrapper.h>
1.7 -#include <bfs_iterator.h>
1.8 +#include <bfs_dfs.h>
1.9 #include <hugo/invalid.h>
1.10 #include <hugo/maps.h>
1.11 #include <for_each_macros.h>
1.12 @@ -55,7 +55,7 @@
1.13 namespace hugo {
1.14
1.15
1.16 -// ///\author Marton Makai, Jacint Szabo
1.17 + // ///\author Marton Makai, Jacint Szabo
1.18 /// A class for computing max flows and related quantities.
1.19 template <typename Graph, typename Num,
1.20 typename CapMap=typename Graph::template EdgeMap<Num>,
1.21 @@ -88,20 +88,20 @@
1.22 //In preflow, it shows levels of nodes.
1.23 //typename Graph::template NodeMap<int> level;
1.24 typename Graph::template NodeMap<Num> excess;
1.25 -// protected:
1.26 -// MaxFlow() { }
1.27 -// void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
1.28 -// FlowMap& _flow)
1.29 -// {
1.30 -// g=&_G;
1.31 -// s=_s;
1.32 -// t=_t;
1.33 -// capacity=&_capacity;
1.34 -// flow=&_flow;
1.35 -// n=_G.nodeNum;
1.36 -// level.set (_G); //kellene vmi ilyesmi fv
1.37 -// excess(_G,0); //itt is
1.38 -// }
1.39 + // protected:
1.40 + // MaxFlow() { }
1.41 + // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
1.42 + // FlowMap& _flow)
1.43 + // {
1.44 + // g=&_G;
1.45 + // s=_s;
1.46 + // t=_t;
1.47 + // capacity=&_capacity;
1.48 + // flow=&_flow;
1.49 + // n=_G.nodeNum;
1.50 + // level.set (_G); //kellene vmi ilyesmi fv
1.51 + // excess(_G,0); //itt is
1.52 + // }
1.53
1.54 public:
1.55
1.56 @@ -362,126 +362,127 @@
1.57
1.58
1.59 void preflowPreproc ( flowEnum fe, VecStack& active,
1.60 - VecNode& level_list, NNMap& left, NNMap& right ) {
1.61 + VecNode& level_list, NNMap& left, NNMap& right )
1.62 + {
1.63
1.64 - std::queue<Node> bfs_queue;
1.65 + std::queue<Node> bfs_queue;
1.66
1.67 - switch ( fe ) {
1.68 - case ZERO_FLOW:
1.69 - {
1.70 - //Reverse_bfs from t, to find the starting level.
1.71 - level.set(t,0);
1.72 - bfs_queue.push(t);
1.73 + switch ( fe ) {
1.74 + case ZERO_FLOW:
1.75 + {
1.76 + //Reverse_bfs from t, to find the starting level.
1.77 + level.set(t,0);
1.78 + bfs_queue.push(t);
1.79
1.80 - while (!bfs_queue.empty()) {
1.81 + while (!bfs_queue.empty()) {
1.82
1.83 - Node v=bfs_queue.front();
1.84 - bfs_queue.pop();
1.85 - int l=level[v]+1;
1.86 + Node v=bfs_queue.front();
1.87 + bfs_queue.pop();
1.88 + int l=level[v]+1;
1.89
1.90 - InEdgeIt e;
1.91 - for(g->first(e,v); g->valid(e); g->next(e)) {
1.92 - Node w=g->tail(e);
1.93 - if ( level[w] == n && w != s ) {
1.94 - bfs_queue.push(w);
1.95 - Node first=level_list[l];
1.96 - if ( g->valid(first) ) left.set(first,w);
1.97 - right.set(w,first);
1.98 - level_list[l]=w;
1.99 - level.set(w, l);
1.100 - }
1.101 - }
1.102 - }
1.103 + InEdgeIt e;
1.104 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.105 + Node w=g->tail(e);
1.106 + if ( level[w] == n && w != s ) {
1.107 + bfs_queue.push(w);
1.108 + Node first=level_list[l];
1.109 + if ( g->valid(first) ) left.set(first,w);
1.110 + right.set(w,first);
1.111 + level_list[l]=w;
1.112 + level.set(w, l);
1.113 + }
1.114 + }
1.115 + }
1.116
1.117 - //the starting flow
1.118 - OutEdgeIt e;
1.119 - for(g->first(e,s); g->valid(e); g->next(e))
1.120 - {
1.121 - Num c=(*capacity)[e];
1.122 - if ( c <= 0 ) continue;
1.123 - Node w=g->head(e);
1.124 - if ( level[w] < n ) {
1.125 - if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.126 - flow->set(e, c);
1.127 - excess.set(w, excess[w]+c);
1.128 - }
1.129 - }
1.130 - break;
1.131 - }
1.132 + //the starting flow
1.133 + OutEdgeIt e;
1.134 + for(g->first(e,s); g->valid(e); g->next(e))
1.135 + {
1.136 + Num c=(*capacity)[e];
1.137 + if ( c <= 0 ) continue;
1.138 + Node w=g->head(e);
1.139 + if ( level[w] < n ) {
1.140 + if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.141 + flow->set(e, c);
1.142 + excess.set(w, excess[w]+c);
1.143 + }
1.144 + }
1.145 + break;
1.146 + }
1.147
1.148 - case GEN_FLOW:
1.149 - case PREFLOW:
1.150 - {
1.151 - //Reverse_bfs from t in the residual graph,
1.152 - //to find the starting level.
1.153 - level.set(t,0);
1.154 - bfs_queue.push(t);
1.155 + case GEN_FLOW:
1.156 + case PREFLOW:
1.157 + {
1.158 + //Reverse_bfs from t in the residual graph,
1.159 + //to find the starting level.
1.160 + level.set(t,0);
1.161 + bfs_queue.push(t);
1.162
1.163 - while (!bfs_queue.empty()) {
1.164 + while (!bfs_queue.empty()) {
1.165
1.166 - Node v=bfs_queue.front();
1.167 - bfs_queue.pop();
1.168 - int l=level[v]+1;
1.169 + Node v=bfs_queue.front();
1.170 + bfs_queue.pop();
1.171 + int l=level[v]+1;
1.172
1.173 - InEdgeIt e;
1.174 - for(g->first(e,v); g->valid(e); g->next(e)) {
1.175 - if ( (*capacity)[e] <= (*flow)[e] ) continue;
1.176 - Node w=g->tail(e);
1.177 - if ( level[w] == n && w != s ) {
1.178 - bfs_queue.push(w);
1.179 - Node first=level_list[l];
1.180 - if ( g->valid(first) ) left.set(first,w);
1.181 - right.set(w,first);
1.182 - level_list[l]=w;
1.183 - level.set(w, l);
1.184 - }
1.185 - }
1.186 + InEdgeIt e;
1.187 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.188 + if ( (*capacity)[e] <= (*flow)[e] ) continue;
1.189 + Node w=g->tail(e);
1.190 + if ( level[w] == n && w != s ) {
1.191 + bfs_queue.push(w);
1.192 + Node first=level_list[l];
1.193 + if ( g->valid(first) ) left.set(first,w);
1.194 + right.set(w,first);
1.195 + level_list[l]=w;
1.196 + level.set(w, l);
1.197 + }
1.198 + }
1.199
1.200 - OutEdgeIt f;
1.201 - for(g->first(f,v); g->valid(f); g->next(f)) {
1.202 - if ( 0 >= (*flow)[f] ) continue;
1.203 - Node w=g->head(f);
1.204 - if ( level[w] == n && w != s ) {
1.205 - bfs_queue.push(w);
1.206 - Node first=level_list[l];
1.207 - if ( g->valid(first) ) left.set(first,w);
1.208 - right.set(w,first);
1.209 - level_list[l]=w;
1.210 - level.set(w, l);
1.211 - }
1.212 - }
1.213 - }
1.214 + OutEdgeIt f;
1.215 + for(g->first(f,v); g->valid(f); g->next(f)) {
1.216 + if ( 0 >= (*flow)[f] ) continue;
1.217 + Node w=g->head(f);
1.218 + if ( level[w] == n && w != s ) {
1.219 + bfs_queue.push(w);
1.220 + Node first=level_list[l];
1.221 + if ( g->valid(first) ) left.set(first,w);
1.222 + right.set(w,first);
1.223 + level_list[l]=w;
1.224 + level.set(w, l);
1.225 + }
1.226 + }
1.227 + }
1.228
1.229
1.230 - //the starting flow
1.231 - OutEdgeIt e;
1.232 - for(g->first(e,s); g->valid(e); g->next(e))
1.233 - {
1.234 - Num rem=(*capacity)[e]-(*flow)[e];
1.235 - if ( rem <= 0 ) continue;
1.236 - Node w=g->head(e);
1.237 - if ( level[w] < n ) {
1.238 - if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.239 - flow->set(e, (*capacity)[e]);
1.240 - excess.set(w, excess[w]+rem);
1.241 - }
1.242 - }
1.243 + //the starting flow
1.244 + OutEdgeIt e;
1.245 + for(g->first(e,s); g->valid(e); g->next(e))
1.246 + {
1.247 + Num rem=(*capacity)[e]-(*flow)[e];
1.248 + if ( rem <= 0 ) continue;
1.249 + Node w=g->head(e);
1.250 + if ( level[w] < n ) {
1.251 + if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.252 + flow->set(e, (*capacity)[e]);
1.253 + excess.set(w, excess[w]+rem);
1.254 + }
1.255 + }
1.256
1.257 - InEdgeIt f;
1.258 - for(g->first(f,s); g->valid(f); g->next(f))
1.259 - {
1.260 - if ( (*flow)[f] <= 0 ) continue;
1.261 - Node w=g->tail(f);
1.262 - if ( level[w] < n ) {
1.263 - if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.264 - excess.set(w, excess[w]+(*flow)[f]);
1.265 - flow->set(f, 0);
1.266 - }
1.267 - }
1.268 - break;
1.269 - } //case PREFLOW
1.270 - }
1.271 - } //preflowPreproc
1.272 + InEdgeIt f;
1.273 + for(g->first(f,s); g->valid(f); g->next(f))
1.274 + {
1.275 + if ( (*flow)[f] <= 0 ) continue;
1.276 + Node w=g->tail(f);
1.277 + if ( level[w] < n ) {
1.278 + if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.279 + excess.set(w, excess[w]+(*flow)[f]);
1.280 + flow->set(f, 0);
1.281 + }
1.282 + }
1.283 + break;
1.284 + } //case PREFLOW
1.285 + }
1.286 + } //preflowPreproc
1.287
1.288
1.289
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/marci/bfs_dfs.h Mon May 10 16:59:20 2004 +0000
2.3 @@ -0,0 +1,314 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef HUGO_BFS_DFS_H
2.6 +#define HUGO_BFS_DFS_H
2.7 +
2.8 +#include <queue>
2.9 +#include <stack>
2.10 +#include <utility>
2.11 +
2.12 +#include <hugo/invalid.h>
2.13 +
2.14 +namespace hugo {
2.15 +
2.16 + /// Bfs searches for the nodes wich are not marked in
2.17 + /// \c reached_map
2.18 + /// Reached have to work as read-write bool Node-map.
2.19 + template <typename Graph, /*typename OutEdgeIt,*/
2.20 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
2.21 + class BfsIterator {
2.22 + protected:
2.23 + typedef typename Graph::Node Node;
2.24 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.25 + const Graph* graph;
2.26 + std::queue<Node> bfs_queue;
2.27 + ReachedMap& reached;
2.28 + bool b_node_newly_reached;
2.29 + OutEdgeIt actual_edge;
2.30 + bool own_reached_map;
2.31 + public:
2.32 + /// In that constructor \c _reached have to be a reference
2.33 + /// for a bool Node-map. The algorithm will search in a bfs order for
2.34 + /// the nodes which are \c false initially
2.35 + BfsIterator(const Graph& _graph, ReachedMap& _reached) :
2.36 + graph(&_graph), reached(_reached),
2.37 + own_reached_map(false) { }
2.38 + /// The same as above, but the map storing the reached nodes
2.39 + /// is constructed dynamically to everywhere false.
2.40 + BfsIterator(const Graph& _graph) :
2.41 + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
2.42 + own_reached_map(true) { }
2.43 + /// The storing the reached nodes have to be destroyed if
2.44 + /// it was constructed dynamically
2.45 + ~BfsIterator() { if (own_reached_map) delete &reached; }
2.46 + /// This method markes \c s reached.
2.47 + /// If the queue is empty, then \c s is pushed in the bfs queue
2.48 + /// and the first out-edge is processed.
2.49 + /// If the queue is not empty, then \c s is simply pushed.
2.50 + void pushAndSetReached(Node s) {
2.51 + reached.set(s, true);
2.52 + if (bfs_queue.empty()) {
2.53 + bfs_queue.push(s);
2.54 + graph->first(actual_edge, s);
2.55 + if (graph->valid(actual_edge)) {
2.56 + Node w=graph->bNode(actual_edge);
2.57 + if (!reached[w]) {
2.58 + bfs_queue.push(w);
2.59 + reached.set(w, true);
2.60 + b_node_newly_reached=true;
2.61 + } else {
2.62 + b_node_newly_reached=false;
2.63 + }
2.64 + }
2.65 + } else {
2.66 + bfs_queue.push(s);
2.67 + }
2.68 + }
2.69 + /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
2.70 + /// its \c operator++() iterates on the edges in a bfs order.
2.71 + BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
2.72 + operator++() {
2.73 + if (graph->valid(actual_edge)) {
2.74 + graph->next(actual_edge);
2.75 + if (graph->valid(actual_edge)) {
2.76 + Node w=graph->bNode(actual_edge);
2.77 + if (!reached[w]) {
2.78 + bfs_queue.push(w);
2.79 + reached.set(w, true);
2.80 + b_node_newly_reached=true;
2.81 + } else {
2.82 + b_node_newly_reached=false;
2.83 + }
2.84 + }
2.85 + } else {
2.86 + bfs_queue.pop();
2.87 + if (!bfs_queue.empty()) {
2.88 + graph->first(actual_edge, bfs_queue.front());
2.89 + if (graph->valid(actual_edge)) {
2.90 + Node w=graph->bNode(actual_edge);
2.91 + if (!reached[w]) {
2.92 + bfs_queue.push(w);
2.93 + reached.set(w, true);
2.94 + b_node_newly_reached=true;
2.95 + } else {
2.96 + b_node_newly_reached=false;
2.97 + }
2.98 + }
2.99 + }
2.100 + }
2.101 + return *this;
2.102 + }
2.103 + ///
2.104 + bool finished() const { return bfs_queue.empty(); }
2.105 + /// The conversion operator makes for converting the bfs-iterator
2.106 + /// to an \c out-edge-iterator.
2.107 + ///\bug Edge have to be in HUGO 0.2
2.108 + operator OutEdgeIt() const { return actual_edge; }
2.109 + ///
2.110 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
2.111 + ///
2.112 + bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
2.113 + ///
2.114 + Node aNode() const { return bfs_queue.front(); }
2.115 + ///
2.116 + Node bNode() const { return graph->bNode(actual_edge); }
2.117 + ///
2.118 + const ReachedMap& getReachedMap() const { return reached; }
2.119 + ///
2.120 + const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
2.121 + };
2.122 +
2.123 + /// Bfs searches for the nodes wich are not marked in
2.124 + /// \c reached_map
2.125 + /// Reached have to work as a read-write bool Node-map,
2.126 + /// Pred is a write Edge Node-map and
2.127 + /// Dist is a read-write int Node-map, have to be.
2.128 + ///\todo In fact onsly simple operations requirement are needed for
2.129 + /// Dist::Value.
2.130 + template <typename Graph,
2.131 + typename ReachedMap=typename Graph::template NodeMap<bool>,
2.132 + typename PredMap
2.133 + =typename Graph::template NodeMap<typename Graph::Edge>,
2.134 + typename DistMap=typename Graph::template NodeMap<int> >
2.135 + class Bfs : public BfsIterator<Graph, ReachedMap> {
2.136 + typedef BfsIterator<Graph, ReachedMap> Parent;
2.137 + protected:
2.138 + typedef typename Parent::Node Node;
2.139 + PredMap& pred;
2.140 + DistMap& dist;
2.141 + public:
2.142 + /// The algorithm will search in a bfs order for
2.143 + /// the nodes which are \c false initially.
2.144 + /// The constructor makes no initial changes on the maps.
2.145 + Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
2.146 + /// \c s is marked to be reached and pushed in the bfs queue.
2.147 + /// If the queue is empty, then the first out-edge is processed.
2.148 + /// If \c s was not marked previously, then
2.149 + /// in addition its pred is set to be \c INVALID, and dist to \c 0.
2.150 + /// if \c s was marked previuosly, then it is simply pushed.
2.151 + void push(Node s) {
2.152 + if (this->reached[s]) {
2.153 + Parent::pushAndSetReached(s);
2.154 + } else {
2.155 + Parent::pushAndSetReached(s);
2.156 + pred.set(s, INVALID);
2.157 + dist.set(s, 0);
2.158 + }
2.159 + }
2.160 + /// A bfs is processed from \c s.
2.161 + void run(Node s) {
2.162 + push(s);
2.163 + while (!this->finished()) this->operator++();
2.164 + }
2.165 + /// Beside the bfs iteration, \c pred and \dist are saved in a
2.166 + /// newly reached node.
2.167 + Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
2.168 + Parent::operator++();
2.169 + if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
2.170 + {
2.171 + pred.set(this->bNode(), this->actual_edge);
2.172 + dist.set(this->bNode(), dist[this->aNode()]);
2.173 + }
2.174 + return *this;
2.175 + }
2.176 + ///
2.177 + const PredMap& getPredMap() const { return pred; }
2.178 + ///
2.179 + const DistMap& getDistMap() const { return dist; }
2.180 + };
2.181 +
2.182 + /// Dfs searches for the nodes wich are not marked in
2.183 + /// \c reached_map
2.184 + /// Reached have to be a read-write bool Node-map.
2.185 + template <typename Graph, /*typename OutEdgeIt,*/
2.186 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
2.187 + class DfsIterator {
2.188 + protected:
2.189 + typedef typename Graph::Node Node;
2.190 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.191 + const Graph* graph;
2.192 + std::stack<OutEdgeIt> dfs_stack;
2.193 + bool b_node_newly_reached;
2.194 + OutEdgeIt actual_edge;
2.195 + Node actual_node;
2.196 + ReachedMap& reached;
2.197 + bool own_reached_map;
2.198 + public:
2.199 + /// In that constructor \c _reached have to be a reference
2.200 + /// for a bool Node-map. The algorithm will search in a dfs order for
2.201 + /// the nodes which are \c false initially
2.202 + DfsIterator(const Graph& _graph, ReachedMap& _reached) :
2.203 + graph(&_graph), reached(_reached),
2.204 + own_reached_map(false) { }
2.205 + /// The same as above, but the map of reached nodes is
2.206 + /// constructed dynamically
2.207 + /// to everywhere false.
2.208 + DfsIterator(const Graph& _graph) :
2.209 + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
2.210 + own_reached_map(true) { }
2.211 + ~DfsIterator() { if (own_reached_map) delete &reached; }
2.212 + /// This method markes s reached and first out-edge is processed.
2.213 + void pushAndSetReached(Node s) {
2.214 + actual_node=s;
2.215 + reached.set(s, true);
2.216 + OutEdgeIt e;
2.217 + graph->first(e, s);
2.218 + dfs_stack.push(e);
2.219 + }
2.220 + /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
2.221 + /// its \c operator++() iterates on the edges in a dfs order.
2.222 + DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
2.223 + operator++() {
2.224 + actual_edge=dfs_stack.top();
2.225 + //actual_node=G.aNode(actual_edge);
2.226 + if (graph->valid(actual_edge)/*.valid()*/) {
2.227 + Node w=graph->bNode(actual_edge);
2.228 + actual_node=w;
2.229 + if (!reached[w]) {
2.230 + OutEdgeIt e;
2.231 + graph->first(e, w);
2.232 + dfs_stack.push(e);
2.233 + reached.set(w, true);
2.234 + b_node_newly_reached=true;
2.235 + } else {
2.236 + actual_node=graph->aNode(actual_edge);
2.237 + graph->next(dfs_stack.top());
2.238 + b_node_newly_reached=false;
2.239 + }
2.240 + } else {
2.241 + //actual_node=G.aNode(dfs_stack.top());
2.242 + dfs_stack.pop();
2.243 + }
2.244 + return *this;
2.245 + }
2.246 + ///
2.247 + bool finished() const { return dfs_stack.empty(); }
2.248 + ///
2.249 + operator OutEdgeIt() const { return actual_edge; }
2.250 + ///
2.251 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
2.252 + ///
2.253 + bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
2.254 + ///
2.255 + Node aNode() const { return actual_node; /*FIXME*/}
2.256 + ///
2.257 + Node bNode() const { return graph->bNode(actual_edge); }
2.258 + ///
2.259 + const ReachedMap& getReachedMap() const { return reached; }
2.260 + ///
2.261 + const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
2.262 + };
2.263 +
2.264 + /// Dfs searches for the nodes wich are not marked in
2.265 + /// \c reached_map
2.266 + /// Reached is a read-write bool Node-map,
2.267 + /// Pred is a write Node-map, have to be.
2.268 + template <typename Graph,
2.269 + typename ReachedMap=typename Graph::template NodeMap<bool>,
2.270 + typename PredMap
2.271 + =typename Graph::template NodeMap<typename Graph::Edge> >
2.272 + class Dfs : public DfsIterator<Graph, ReachedMap> {
2.273 + typedef DfsIterator<Graph, ReachedMap> Parent;
2.274 + protected:
2.275 + typedef typename Parent::Node Node;
2.276 + PredMap& pred;
2.277 + public:
2.278 + /// The algorithm will search in a dfs order for
2.279 + /// the nodes which are \c false initially.
2.280 + /// The constructor makes no initial changes on the maps.
2.281 + Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
2.282 + /// \c s is marked to be reached and pushed in the bfs queue.
2.283 + /// If the queue is empty, then the first out-edge is processed.
2.284 + /// If \c s was not marked previously, then
2.285 + /// in addition its pred is set to be \c INVALID.
2.286 + /// if \c s was marked previuosly, then it is simply pushed.
2.287 + void push(Node s) {
2.288 + if (this->reached[s]) {
2.289 + Parent::pushAndSetReached(s);
2.290 + } else {
2.291 + Parent::pushAndSetReached(s);
2.292 + pred.set(s, INVALID);
2.293 + }
2.294 + }
2.295 + /// A bfs is processed from \c s.
2.296 + void run(Node s) {
2.297 + push(s);
2.298 + while (!this->finished()) this->operator++();
2.299 + }
2.300 + /// Beside the dfs iteration, \c pred is saved in a
2.301 + /// newly reached node.
2.302 + Dfs<Graph, ReachedMap, PredMap> operator++() {
2.303 + Parent::operator++();
2.304 + if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
2.305 + {
2.306 + pred.set(this->bNode(), this->actual_edge);
2.307 + }
2.308 + return *this;
2.309 + }
2.310 + ///
2.311 + const PredMap& getPredMap() const { return pred; }
2.312 + };
2.313 +
2.314 +
2.315 +} // namespace hugo
2.316 +
2.317 +#endif //HUGO_BFS_DFS_H
3.1 --- a/src/work/marci/bfs_dfs_misc.h Mon May 10 16:52:51 2004 +0000
3.2 +++ b/src/work/marci/bfs_dfs_misc.h Mon May 10 16:59:20 2004 +0000
3.3 @@ -2,7 +2,7 @@
3.4 #ifndef HUGO_BFS_DFS_MISC_H
3.5 #define HUGO_BFS_DFS_MISC_H
3.6
3.7 -#include <bfs_iterator.h>
3.8 +#include <bfs_dfs.h>
3.9 #include <for_each_macros.h>
3.10
3.11 namespace hugo {
4.1 --- a/src/work/marci/bfs_iterator.h Mon May 10 16:52:51 2004 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,314 +0,0 @@
4.4 -// -*- c++ -*-
4.5 -#ifndef HUGO_BFS_ITERATOR_H
4.6 -#define HUGO_BFS_ITERATOR_H
4.7 -
4.8 -#include <queue>
4.9 -#include <stack>
4.10 -#include <utility>
4.11 -
4.12 -#include <hugo/invalid.h>
4.13 -
4.14 -namespace hugo {
4.15 -
4.16 - /// Bfs searches for the nodes wich are not marked in
4.17 - /// \c reached_map
4.18 - /// Reached have to work as read-write bool Node-map.
4.19 - template <typename Graph, /*typename OutEdgeIt,*/
4.20 - typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
4.21 - class BfsIterator {
4.22 - protected:
4.23 - typedef typename Graph::Node Node;
4.24 - typedef typename Graph::OutEdgeIt OutEdgeIt;
4.25 - const Graph* graph;
4.26 - std::queue<Node> bfs_queue;
4.27 - ReachedMap& reached;
4.28 - bool b_node_newly_reached;
4.29 - OutEdgeIt actual_edge;
4.30 - bool own_reached_map;
4.31 - public:
4.32 - /// In that constructor \c _reached have to be a reference
4.33 - /// for a bool Node-map. The algorithm will search in a bfs order for
4.34 - /// the nodes which are \c false initially
4.35 - BfsIterator(const Graph& _graph, ReachedMap& _reached) :
4.36 - graph(&_graph), reached(_reached),
4.37 - own_reached_map(false) { }
4.38 - /// The same as above, but the map storing the reached nodes
4.39 - /// is constructed dynamically to everywhere false.
4.40 - BfsIterator(const Graph& _graph) :
4.41 - graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
4.42 - own_reached_map(true) { }
4.43 - /// The storing the reached nodes have to be destroyed if
4.44 - /// it was constructed dynamically
4.45 - ~BfsIterator() { if (own_reached_map) delete &reached; }
4.46 - /// This method markes \c s reached.
4.47 - /// If the queue is empty, then \c s is pushed in the bfs queue
4.48 - /// and the first out-edge is processed.
4.49 - /// If the queue is not empty, then \c s is simply pushed.
4.50 - void pushAndSetReached(Node s) {
4.51 - reached.set(s, true);
4.52 - if (bfs_queue.empty()) {
4.53 - bfs_queue.push(s);
4.54 - graph->first(actual_edge, s);
4.55 - if (graph->valid(actual_edge)) {
4.56 - Node w=graph->bNode(actual_edge);
4.57 - if (!reached[w]) {
4.58 - bfs_queue.push(w);
4.59 - reached.set(w, true);
4.60 - b_node_newly_reached=true;
4.61 - } else {
4.62 - b_node_newly_reached=false;
4.63 - }
4.64 - }
4.65 - } else {
4.66 - bfs_queue.push(s);
4.67 - }
4.68 - }
4.69 - /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
4.70 - /// its \c operator++() iterates on the edges in a bfs order.
4.71 - BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
4.72 - operator++() {
4.73 - if (graph->valid(actual_edge)) {
4.74 - graph->next(actual_edge);
4.75 - if (graph->valid(actual_edge)) {
4.76 - Node w=graph->bNode(actual_edge);
4.77 - if (!reached[w]) {
4.78 - bfs_queue.push(w);
4.79 - reached.set(w, true);
4.80 - b_node_newly_reached=true;
4.81 - } else {
4.82 - b_node_newly_reached=false;
4.83 - }
4.84 - }
4.85 - } else {
4.86 - bfs_queue.pop();
4.87 - if (!bfs_queue.empty()) {
4.88 - graph->first(actual_edge, bfs_queue.front());
4.89 - if (graph->valid(actual_edge)) {
4.90 - Node w=graph->bNode(actual_edge);
4.91 - if (!reached[w]) {
4.92 - bfs_queue.push(w);
4.93 - reached.set(w, true);
4.94 - b_node_newly_reached=true;
4.95 - } else {
4.96 - b_node_newly_reached=false;
4.97 - }
4.98 - }
4.99 - }
4.100 - }
4.101 - return *this;
4.102 - }
4.103 - ///
4.104 - bool finished() const { return bfs_queue.empty(); }
4.105 - /// The conversion operator makes for converting the bfs-iterator
4.106 - /// to an \c out-edge-iterator.
4.107 - ///\bug Edge have to be in HUGO 0.2
4.108 - operator OutEdgeIt() const { return actual_edge; }
4.109 - ///
4.110 - bool isBNodeNewlyReached() const { return b_node_newly_reached; }
4.111 - ///
4.112 - bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
4.113 - ///
4.114 - Node aNode() const { return bfs_queue.front(); }
4.115 - ///
4.116 - Node bNode() const { return graph->bNode(actual_edge); }
4.117 - ///
4.118 - const ReachedMap& getReachedMap() const { return reached; }
4.119 - ///
4.120 - const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
4.121 - };
4.122 -
4.123 - /// Bfs searches for the nodes wich are not marked in
4.124 - /// \c reached_map
4.125 - /// Reached have to work as a read-write bool Node-map,
4.126 - /// Pred is a write Edge Node-map and
4.127 - /// Dist is a read-write int Node-map, have to be.
4.128 - ///\todo In fact onsly simple operations requirement are needed for
4.129 - /// Dist::Value.
4.130 - template <typename Graph,
4.131 - typename ReachedMap=typename Graph::template NodeMap<bool>,
4.132 - typename PredMap
4.133 - =typename Graph::template NodeMap<typename Graph::Edge>,
4.134 - typename DistMap=typename Graph::template NodeMap<int> >
4.135 - class Bfs : public BfsIterator<Graph, ReachedMap> {
4.136 - typedef BfsIterator<Graph, ReachedMap> Parent;
4.137 - protected:
4.138 - typedef typename Parent::Node Node;
4.139 - PredMap& pred;
4.140 - DistMap& dist;
4.141 - public:
4.142 - /// The algorithm will search in a bfs order for
4.143 - /// the nodes which are \c false initially.
4.144 - /// The constructor makes no initial changes on the maps.
4.145 - Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
4.146 - /// \c s is marked to be reached and pushed in the bfs queue.
4.147 - /// If the queue is empty, then the first out-edge is processed.
4.148 - /// If \c s was not marked previously, then
4.149 - /// in addition its pred is set to be \c INVALID, and dist to \c 0.
4.150 - /// if \c s was marked previuosly, then it is simply pushed.
4.151 - void push(Node s) {
4.152 - if (this->reached[s]) {
4.153 - Parent::pushAndSetReached(s);
4.154 - } else {
4.155 - Parent::pushAndSetReached(s);
4.156 - pred.set(s, INVALID);
4.157 - dist.set(s, 0);
4.158 - }
4.159 - }
4.160 - /// A bfs is processed from \c s.
4.161 - void run(Node s) {
4.162 - push(s);
4.163 - while (!this->finished()) this->operator++();
4.164 - }
4.165 - /// Beside the bfs iteration, \c pred and \dist are saved in a
4.166 - /// newly reached node.
4.167 - Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
4.168 - Parent::operator++();
4.169 - if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
4.170 - {
4.171 - pred.set(this->bNode(), this->actual_edge);
4.172 - dist.set(this->bNode(), dist[this->aNode()]);
4.173 - }
4.174 - return *this;
4.175 - }
4.176 - ///
4.177 - const PredMap& getPredMap() const { return pred; }
4.178 - ///
4.179 - const DistMap& getDistMap() const { return dist; }
4.180 - };
4.181 -
4.182 - /// Dfs searches for the nodes wich are not marked in
4.183 - /// \c reached_map
4.184 - /// Reached have to be a read-write bool Node-map.
4.185 - template <typename Graph, /*typename OutEdgeIt,*/
4.186 - typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
4.187 - class DfsIterator {
4.188 - protected:
4.189 - typedef typename Graph::Node Node;
4.190 - typedef typename Graph::OutEdgeIt OutEdgeIt;
4.191 - const Graph* graph;
4.192 - std::stack<OutEdgeIt> dfs_stack;
4.193 - bool b_node_newly_reached;
4.194 - OutEdgeIt actual_edge;
4.195 - Node actual_node;
4.196 - ReachedMap& reached;
4.197 - bool own_reached_map;
4.198 - public:
4.199 - /// In that constructor \c _reached have to be a reference
4.200 - /// for a bool Node-map. The algorithm will search in a dfs order for
4.201 - /// the nodes which are \c false initially
4.202 - DfsIterator(const Graph& _graph, ReachedMap& _reached) :
4.203 - graph(&_graph), reached(_reached),
4.204 - own_reached_map(false) { }
4.205 - /// The same as above, but the map of reached nodes is
4.206 - /// constructed dynamically
4.207 - /// to everywhere false.
4.208 - DfsIterator(const Graph& _graph) :
4.209 - graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
4.210 - own_reached_map(true) { }
4.211 - ~DfsIterator() { if (own_reached_map) delete &reached; }
4.212 - /// This method markes s reached and first out-edge is processed.
4.213 - void pushAndSetReached(Node s) {
4.214 - actual_node=s;
4.215 - reached.set(s, true);
4.216 - OutEdgeIt e;
4.217 - graph->first(e, s);
4.218 - dfs_stack.push(e);
4.219 - }
4.220 - /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
4.221 - /// its \c operator++() iterates on the edges in a dfs order.
4.222 - DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
4.223 - operator++() {
4.224 - actual_edge=dfs_stack.top();
4.225 - //actual_node=G.aNode(actual_edge);
4.226 - if (graph->valid(actual_edge)/*.valid()*/) {
4.227 - Node w=graph->bNode(actual_edge);
4.228 - actual_node=w;
4.229 - if (!reached[w]) {
4.230 - OutEdgeIt e;
4.231 - graph->first(e, w);
4.232 - dfs_stack.push(e);
4.233 - reached.set(w, true);
4.234 - b_node_newly_reached=true;
4.235 - } else {
4.236 - actual_node=graph->aNode(actual_edge);
4.237 - graph->next(dfs_stack.top());
4.238 - b_node_newly_reached=false;
4.239 - }
4.240 - } else {
4.241 - //actual_node=G.aNode(dfs_stack.top());
4.242 - dfs_stack.pop();
4.243 - }
4.244 - return *this;
4.245 - }
4.246 - ///
4.247 - bool finished() const { return dfs_stack.empty(); }
4.248 - ///
4.249 - operator OutEdgeIt() const { return actual_edge; }
4.250 - ///
4.251 - bool isBNodeNewlyReached() const { return b_node_newly_reached; }
4.252 - ///
4.253 - bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
4.254 - ///
4.255 - Node aNode() const { return actual_node; /*FIXME*/}
4.256 - ///
4.257 - Node bNode() const { return graph->bNode(actual_edge); }
4.258 - ///
4.259 - const ReachedMap& getReachedMap() const { return reached; }
4.260 - ///
4.261 - const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
4.262 - };
4.263 -
4.264 - /// Dfs searches for the nodes wich are not marked in
4.265 - /// \c reached_map
4.266 - /// Reached is a read-write bool Node-map,
4.267 - /// Pred is a write Node-map, have to be.
4.268 - template <typename Graph,
4.269 - typename ReachedMap=typename Graph::template NodeMap<bool>,
4.270 - typename PredMap
4.271 - =typename Graph::template NodeMap<typename Graph::Edge> >
4.272 - class Dfs : public DfsIterator<Graph, ReachedMap> {
4.273 - typedef DfsIterator<Graph, ReachedMap> Parent;
4.274 - protected:
4.275 - typedef typename Parent::Node Node;
4.276 - PredMap& pred;
4.277 - public:
4.278 - /// The algorithm will search in a dfs order for
4.279 - /// the nodes which are \c false initially.
4.280 - /// The constructor makes no initial changes on the maps.
4.281 - Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
4.282 - /// \c s is marked to be reached and pushed in the bfs queue.
4.283 - /// If the queue is empty, then the first out-edge is processed.
4.284 - /// If \c s was not marked previously, then
4.285 - /// in addition its pred is set to be \c INVALID.
4.286 - /// if \c s was marked previuosly, then it is simply pushed.
4.287 - void push(Node s) {
4.288 - if (this->reached[s]) {
4.289 - Parent::pushAndSetReached(s);
4.290 - } else {
4.291 - Parent::pushAndSetReached(s);
4.292 - pred.set(s, INVALID);
4.293 - }
4.294 - }
4.295 - /// A bfs is processed from \c s.
4.296 - void run(Node s) {
4.297 - push(s);
4.298 - while (!this->finished()) this->operator++();
4.299 - }
4.300 - /// Beside the dfs iteration, \c pred is saved in a
4.301 - /// newly reached node.
4.302 - Dfs<Graph, ReachedMap, PredMap> operator++() {
4.303 - Parent::operator++();
4.304 - if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
4.305 - {
4.306 - pred.set(this->bNode(), this->actual_edge);
4.307 - }
4.308 - return *this;
4.309 - }
4.310 - ///
4.311 - const PredMap& getPredMap() const { return pred; }
4.312 - };
4.313 -
4.314 -
4.315 -} // namespace hugo
4.316 -
4.317 -#endif //HUGO_BFS_ITERATOR_H
5.1 --- a/src/work/marci/bfsit_vs_byhand.cc Mon May 10 16:52:51 2004 +0000
5.2 +++ b/src/work/marci/bfsit_vs_byhand.cc Mon May 10 16:59:20 2004 +0000
5.3 @@ -7,7 +7,7 @@
5.4 #include <hugo/dimacs.h>
5.5 #include <hugo/time_measure.h>
5.6 #include <for_each_macros.h>
5.7 -#include <bfs_iterator.h>
5.8 +#include <bfs_dfs.h>
5.9
5.10 using namespace hugo;
5.11
6.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc Mon May 10 16:52:51 2004 +0000
6.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc Mon May 10 16:59:20 2004 +0000
6.3 @@ -8,7 +8,7 @@
6.4 //#include <dimacs.h>
6.5 #include <hugo/time_measure.h>
6.6 #include <for_each_macros.h>
6.7 -#include <bfs_iterator.h>
6.8 +#include <bfs_dfs.h>
6.9 #include <hugo/graph_wrapper.h>
6.10 #include <bipartite_graph_wrapper.h>
6.11 #include <hugo/maps.h>
7.1 --- a/src/work/marci/bipartite_matching_try.cc Mon May 10 16:52:51 2004 +0000
7.2 +++ b/src/work/marci/bipartite_matching_try.cc Mon May 10 16:59:20 2004 +0000
7.3 @@ -9,7 +9,7 @@
7.4 //#include <dimacs.h>
7.5 #include <hugo/time_measure.h>
7.6 #include <for_each_macros.h>
7.7 -#include <bfs_iterator.h>
7.8 +#include <bfs_dfs.h>
7.9 #include <hugo/graph_wrapper.h>
7.10 #include <bipartite_graph_wrapper.h>
7.11 #include <hugo/maps.h>
8.1 --- a/src/work/marci/bipartite_matching_try_2.cc Mon May 10 16:52:51 2004 +0000
8.2 +++ b/src/work/marci/bipartite_matching_try_2.cc Mon May 10 16:59:20 2004 +0000
8.3 @@ -9,7 +9,7 @@
8.4 //#include <dimacs.h>
8.5 #include <hugo/time_measure.h>
8.6 #include <for_each_macros.h>
8.7 -#include <bfs_iterator.h>
8.8 +#include <bfs_dfs.h>
8.9 #include <bipartite_graph_wrapper.h>
8.10 #include <hugo/maps.h>
8.11 #include <max_flow.h>
9.1 --- a/src/work/marci/bipartite_matching_try_3.cc Mon May 10 16:52:51 2004 +0000
9.2 +++ b/src/work/marci/bipartite_matching_try_3.cc Mon May 10 16:59:20 2004 +0000
9.3 @@ -8,7 +8,7 @@
9.4 //#include <dimacs.h>
9.5 #include <hugo/time_measure.h>
9.6 #include <for_each_macros.h>
9.7 -#include <bfs_iterator.h>
9.8 +#include <bfs_dfs.h>
9.9 #include <bipartite_graph_wrapper.h>
9.10 #include <hugo/maps.h>
9.11 #include <max_flow.h>
10.1 --- a/src/work/marci/iterator_bfs_demo.cc Mon May 10 16:52:51 2004 +0000
10.2 +++ b/src/work/marci/iterator_bfs_demo.cc Mon May 10 16:59:20 2004 +0000
10.3 @@ -5,7 +5,7 @@
10.4
10.5 #include <list_graph.h>
10.6 //#include <smart_graph.h>
10.7 -#include <bfs_iterator.h>
10.8 +#include <bfs_dfs.h>
10.9 #include <hugo/graph_wrapper.h>
10.10
10.11 using namespace hugo;