1.1 --- a/src/work/bfs_iterator.hh Tue Mar 02 20:40:39 2004 +0000
1.2 +++ b/src/work/bfs_iterator.hh Wed Mar 03 14:30:38 2004 +0000
1.3 @@ -544,7 +544,7 @@
1.4
1.5
1.6 template <typename Graph, typename OutEdgeIt,
1.7 - typename ReachedMap=typename Graph::NodeMap<bool> >
1.8 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.9 class BfsIterator4 {
1.10 typedef typename Graph::NodeIt NodeIt;
1.11 const Graph& G;
1.12 @@ -566,7 +566,7 @@
1.13 if (bfs_queue.empty()) {
1.14 bfs_queue.push(s);
1.15 G.getFirst(actual_edge, s);
1.16 - if (actual_edge.valid()) {
1.17 + if (G.valid(actual_edge)/*.valid()*/) {
1.18 NodeIt w=G.bNode(actual_edge);
1.19 if (!reached.get(w)) {
1.20 bfs_queue.push(w);
1.21 @@ -582,9 +582,9 @@
1.22 }
1.23 BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.24 operator++() {
1.25 - if (actual_edge.valid()) {
1.26 - ++actual_edge;
1.27 - if (actual_edge.valid()) {
1.28 + if (G.valid(actual_edge)/*.valid()*/) {
1.29 + /*++*/G.next(actual_edge);
1.30 + if (G.valid(actual_edge)/*.valid()*/) {
1.31 NodeIt w=G.bNode(actual_edge);
1.32 if (!reached.get(w)) {
1.33 bfs_queue.push(w);
1.34 @@ -598,7 +598,7 @@
1.35 bfs_queue.pop();
1.36 if (!bfs_queue.empty()) {
1.37 G.getFirst(actual_edge, bfs_queue.front());
1.38 - if (actual_edge.valid()) {
1.39 + if (G.valid(actual_edge)/*.valid()*/) {
1.40 NodeIt w=G.bNode(actual_edge);
1.41 if (!reached.get(w)) {
1.42 bfs_queue.push(w);
1.43 @@ -615,15 +615,95 @@
1.44 bool finished() const { return bfs_queue.empty(); }
1.45 operator OutEdgeIt () const { return actual_edge; }
1.46 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.47 - bool isANodeExamined() const { return !(actual_edge.valid()); }
1.48 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.49 NodeIt aNode() const { return bfs_queue.front(); }
1.50 NodeIt bNode() const { return G.bNode(actual_edge); }
1.51 const ReachedMap& getReachedMap() const { return reached; }
1.52 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
1.53 };
1.54
1.55 +
1.56 + template <typename GraphWrapper, typename OutEdgeIt,
1.57 + typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.58 + class BfsIterator5 {
1.59 + typedef typename GraphWrapper::NodeIt NodeIt;
1.60 + GraphWrapper G;
1.61 + std::queue<NodeIt> bfs_queue;
1.62 + ReachedMap& reached;
1.63 + bool b_node_newly_reached;
1.64 + OutEdgeIt actual_edge;
1.65 + bool own_reached_map;
1.66 + public:
1.67 + BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.68 + G(_G), reached(_reached),
1.69 + own_reached_map(false) { }
1.70 + BfsIterator5(const GraphWrapper& _G) :
1.71 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.72 + own_reached_map(true) { }
1.73 + ~BfsIterator5() { if (own_reached_map) delete &reached; }
1.74 + void pushAndSetReached(NodeIt s) {
1.75 + reached.set(s, true);
1.76 + if (bfs_queue.empty()) {
1.77 + bfs_queue.push(s);
1.78 + G.getFirst(actual_edge, s);
1.79 + if (G.valid(actual_edge)/*.valid()*/) {
1.80 + NodeIt w=G.bNode(actual_edge);
1.81 + if (!reached.get(w)) {
1.82 + bfs_queue.push(w);
1.83 + reached.set(w, true);
1.84 + b_node_newly_reached=true;
1.85 + } else {
1.86 + b_node_newly_reached=false;
1.87 + }
1.88 + }
1.89 + } else {
1.90 + bfs_queue.push(s);
1.91 + }
1.92 + }
1.93 + BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
1.94 + operator++() {
1.95 + if (G.valid(actual_edge)/*.valid()*/) {
1.96 + /*++*/G.next(actual_edge);
1.97 + if (G.valid(actual_edge)/*.valid()*/) {
1.98 + NodeIt w=G.bNode(actual_edge);
1.99 + if (!reached.get(w)) {
1.100 + bfs_queue.push(w);
1.101 + reached.set(w, true);
1.102 + b_node_newly_reached=true;
1.103 + } else {
1.104 + b_node_newly_reached=false;
1.105 + }
1.106 + }
1.107 + } else {
1.108 + bfs_queue.pop();
1.109 + if (!bfs_queue.empty()) {
1.110 + G.getFirst(actual_edge, bfs_queue.front());
1.111 + if (G.valid(actual_edge)/*.valid()*/) {
1.112 + NodeIt w=G.bNode(actual_edge);
1.113 + if (!reached.get(w)) {
1.114 + bfs_queue.push(w);
1.115 + reached.set(w, true);
1.116 + b_node_newly_reached=true;
1.117 + } else {
1.118 + b_node_newly_reached=false;
1.119 + }
1.120 + }
1.121 + }
1.122 + }
1.123 + return *this;
1.124 + }
1.125 + bool finished() const { return bfs_queue.empty(); }
1.126 + operator OutEdgeIt () const { return actual_edge; }
1.127 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.128 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.129 + NodeIt aNode() const { return bfs_queue.front(); }
1.130 + NodeIt bNode() const { return G.bNode(actual_edge); }
1.131 + const ReachedMap& getReachedMap() const { return reached; }
1.132 + const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
1.133 + };
1.134 +
1.135 template <typename Graph, typename OutEdgeIt,
1.136 - typename ReachedMap=typename Graph::NodeMap<bool> >
1.137 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.138 class DfsIterator4 {
1.139 typedef typename Graph::NodeIt NodeIt;
1.140 const Graph& G;
1.141 @@ -650,7 +730,7 @@
1.142 operator++() {
1.143 actual_edge=dfs_stack.top();
1.144 //actual_node=G.aNode(actual_edge);
1.145 - if (actual_edge.valid()) {
1.146 + if (G.valid(actual_edge)/*.valid()*/) {
1.147 NodeIt w=G.bNode(actual_edge);
1.148 actual_node=w;
1.149 if (!reached.get(w)) {
1.150 @@ -659,7 +739,7 @@
1.151 b_node_newly_reached=true;
1.152 } else {
1.153 actual_node=G.aNode(actual_edge);
1.154 - ++(dfs_stack.top());
1.155 + /*++*/G.next(dfs_stack.top());
1.156 b_node_newly_reached=false;
1.157 }
1.158 } else {
1.159 @@ -671,87 +751,68 @@
1.160 bool finished() const { return dfs_stack.empty(); }
1.161 operator OutEdgeIt () const { return actual_edge; }
1.162 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.163 - bool isANodeExamined() const { return !(actual_edge.valid()); }
1.164 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.165 NodeIt aNode() const { return actual_node; /*FIXME*/}
1.166 NodeIt bNode() const { return G.bNode(actual_edge); }
1.167 const ReachedMap& getReachedMap() const { return reached; }
1.168 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.169 };
1.170
1.171 -
1.172 -
1.173 - template <typename GraphWrapper, typename ReachedMap>
1.174 - class BfsIterator5 {
1.175 + template <typename GraphWrapper, typename OutEdgeIt,
1.176 + typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.177 + class DfsIterator5 {
1.178 typedef typename GraphWrapper::NodeIt NodeIt;
1.179 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.180 - GraphWrapper gw;
1.181 - std::queue<NodeIt> bfs_queue;
1.182 - ReachedMap reached;
1.183 + GraphWrapper G;
1.184 + std::stack<OutEdgeIt> dfs_stack;
1.185 bool b_node_newly_reached;
1.186 OutEdgeIt actual_edge;
1.187 + NodeIt actual_node;
1.188 + ReachedMap& reached;
1.189 + bool own_reached_map;
1.190 public:
1.191 - BfsIterator5(GraphWrapper _gw) :
1.192 - gw(_gw), reached(_gw.getGraph()) { }
1.193 + DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.194 + G(_G), reached(_reached),
1.195 + own_reached_map(false) { }
1.196 + DfsIterator5(const GraphWrapper& _G) :
1.197 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.198 + own_reached_map(true) { }
1.199 + ~DfsIterator5() { if (own_reached_map) delete &reached; }
1.200 void pushAndSetReached(NodeIt s) {
1.201 + actual_node=s;
1.202 reached.set(s, true);
1.203 - if (bfs_queue.empty()) {
1.204 - bfs_queue.push(s);
1.205 - gw.getFirst(actual_edge, s);
1.206 - if (actual_edge.valid()) {
1.207 - NodeIt w=gw.bNode(actual_edge);
1.208 - if (!reached.get(w)) {
1.209 - bfs_queue.push(w);
1.210 - reached.set(w, true);
1.211 - b_node_newly_reached=true;
1.212 - } else {
1.213 - b_node_newly_reached=false;
1.214 - }
1.215 - }
1.216 - } else {
1.217 - bfs_queue.push(s);
1.218 - }
1.219 + dfs_stack.push(G.template first<OutEdgeIt>(s));
1.220 }
1.221 - BfsIterator5<GraphWrapper, ReachedMap>&
1.222 + DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
1.223 operator++() {
1.224 - if (actual_edge.valid()) {
1.225 - ++actual_edge;
1.226 - if (actual_edge.valid()) {
1.227 - NodeIt w=gw.bNode(actual_edge);
1.228 - if (!reached.get(w)) {
1.229 - bfs_queue.push(w);
1.230 - reached.set(w, true);
1.231 - b_node_newly_reached=true;
1.232 - } else {
1.233 - b_node_newly_reached=false;
1.234 - }
1.235 + actual_edge=dfs_stack.top();
1.236 + //actual_node=G.aNode(actual_edge);
1.237 + if (G.valid(actual_edge)/*.valid()*/) {
1.238 + NodeIt w=G.bNode(actual_edge);
1.239 + actual_node=w;
1.240 + if (!reached.get(w)) {
1.241 + dfs_stack.push(G.template first<OutEdgeIt>(w));
1.242 + reached.set(w, true);
1.243 + b_node_newly_reached=true;
1.244 + } else {
1.245 + actual_node=G.aNode(actual_edge);
1.246 + /*++*/G.next(dfs_stack.top());
1.247 + b_node_newly_reached=false;
1.248 }
1.249 } else {
1.250 - bfs_queue.pop();
1.251 - if (!bfs_queue.empty()) {
1.252 - gw.getFirst(actual_edge, bfs_queue.front());
1.253 - if (actual_edge.valid()) {
1.254 - NodeIt w=gw.bNode(actual_edge);
1.255 - if (!reached.get(w)) {
1.256 - bfs_queue.push(w);
1.257 - reached.set(w, true);
1.258 - b_node_newly_reached=true;
1.259 - } else {
1.260 - b_node_newly_reached=false;
1.261 - }
1.262 - }
1.263 - }
1.264 + //actual_node=G.aNode(dfs_stack.top());
1.265 + dfs_stack.pop();
1.266 }
1.267 return *this;
1.268 }
1.269 - bool finished() const { return bfs_queue.empty(); }
1.270 + bool finished() const { return dfs_stack.empty(); }
1.271 operator OutEdgeIt () const { return actual_edge; }
1.272 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.273 - bool isANodeExamined() const { return !(actual_edge.valid()); }
1.274 - NodeIt aNode() const { return bfs_queue.front(); }
1.275 - NodeIt bNode() const { return gw.bNode(actual_edge); }
1.276 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.277 + NodeIt aNode() const { return actual_node; /*FIXME*/}
1.278 + NodeIt bNode() const { return G.bNode(actual_edge); }
1.279 const ReachedMap& getReachedMap() const { return reached; }
1.280 - const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
1.281 - };
1.282 + const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.283 + };
1.284
1.285
1.286