COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_mm.h @ 987:87f7c54892df

Last change on this file since 987:87f7c54892df was 987:87f7c54892df, checked in by Alpar Juttner, 15 years ago

Naming changes:

File size: 18.5 KB
Line 
1// -*- c++ -*-
2#ifndef LEMON_BFS_DFS_H
3#define LEMON_BFS_DFS_H
4
5/// \ingroup galgs
6/// \file
7/// \brief Bfs and dfs iterators.
8///
9/// This file contains bfs and dfs iterator classes.
10///
11// /// \author Marton Makai
12
13#include <queue>
14#include <stack>
15#include <utility>
16
17#include <lemon/invalid.h>
18
19namespace lemon {
20  namespace marci {
21
22  /// Bfs searches for the nodes wich are not marked in
23  /// \c reached_map
24  /// RM have to be a read-write bool node-map.
25  /// \ingroup galgs
26  template <typename Graph, /*typename OutEdgeIt,*/
27            typename RM/*=typename Graph::NodeMap<bool>*/ >
28  class BfsIterator {
29  public:
30    typedef RM ReachedMap;
31  protected:
32    typedef typename Graph::Node Node;
33    typedef typename Graph::Edge Edge;
34    typedef typename Graph::OutEdgeIt OutEdgeIt;
35    const Graph* graph;
36    std::queue<Node> bfs_queue;
37    ReachedMap* reached_map;
38    bool b_node_newly_reached;
39    //OutEdgeIt actual_edge;
40    Edge actual_edge;
41    /// \e
42    BfsIterator(const Graph& _graph) : graph(&_graph), reached_map(0) { }
43    /// RM have to be set before any bfs operation.
44    BfsIterator<Graph, RM>& setReached(RM& _reached_map) {
45      reached_map=&_reached_map;
46    }
47  public:
48    /// In that constructor \c _reached_map have to be a reference
49    /// for a bool bode-map. The algorithm will search for the
50    /// initially \c false nodes
51    /// in a bfs order.
52    BfsIterator(const Graph& _graph, ReachedMap& _reached_map) :
53      graph(&_graph), reached_map(&_reached_map) { }
54    /// The same as above, but the map storing the reached nodes
55    /// is constructed dynamically to everywhere false.
56    /// \deprecated
57//     BfsIterator(const Graph& _graph) :
58//       graph(&_graph), reached_map(new ReachedMap(*graph /*, false*/)),
59//       own_reached_map(true) { }
60//     /// The map storing the reached nodes have to be destroyed if
61//     /// it was constructed dynamically
62//     ~BfsIterator() { if (own_reached_map) delete reached_map; }
63    /// This method markes \c s reached.
64    /// If the queue is empty, then \c s is pushed in the bfs queue
65    /// and the first out-edge is processed.
66    /// If the queue is not empty, then \c s is simply pushed.
67    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
68      reached_map->set(s, true);
69      if (bfs_queue.empty()) {
70        bfs_queue.push(s);
71        actual_edge=OutEdgeIt(*graph, s);
72        //graph->first(actual_edge, s);
73        if (actual_edge!=INVALID) {
74          Node w=graph->target(actual_edge);
75          if (!(*reached_map)[w]) {
76            bfs_queue.push(w);
77            reached_map->set(w, true);
78            b_node_newly_reached=true;
79          } else {
80            b_node_newly_reached=false;
81          }
82        }
83      } else {
84        bfs_queue.push(s);
85      }
86      return *this;
87    }
88    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
89    /// its \c operator++() iterates on the edges in a bfs order.
90    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
91    operator++() {
92      if (actual_edge!=INVALID) {
93        actual_edge=++OutEdgeIt(*graph, actual_edge);
94        //++actual_edge;
95        if (actual_edge!=INVALID) {
96          Node w=graph->target(actual_edge);
97          if (!(*reached_map)[w]) {
98            bfs_queue.push(w);
99            reached_map->set(w, true);
100            b_node_newly_reached=true;
101          } else {
102            b_node_newly_reached=false;
103          }
104        }
105      } else {
106        bfs_queue.pop();
107        if (!bfs_queue.empty()) {
108          actual_edge=OutEdgeIt(*graph, bfs_queue.front());
109          //graph->first(actual_edge, bfs_queue.front());
110          if (actual_edge!=INVALID) {
111            Node w=graph->target(actual_edge);
112            if (!(*reached_map)[w]) {
113              bfs_queue.push(w);
114              reached_map->set(w, true);
115              b_node_newly_reached=true;
116            } else {
117              b_node_newly_reached=false;
118            }
119          }
120        }
121      }
122      return *this;
123    }
124    /// Returns true iff the algorithm is finished.
125    bool finished() const { return bfs_queue.empty(); }
126    /// The conversion operator makes for converting the bfs-iterator
127    /// to an \c out-edge-iterator.
128    ///\bug Edge have to be in LEMON 0.2
129    operator Edge() const { return actual_edge; }
130    /// Returns if b-node has been reached just now.
131    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
132    /// Returns if a-node is examined.
133    bool isANodeExamined() const { return actual_edge==INVALID; }
134    /// Returns a-node of the actual edge, so does if the edge is invalid.
135    Node source() const { return bfs_queue.front(); }
136    /// \pre The actual edge have to be valid.
137    Node target() const { return graph->target(actual_edge); }
138    /// Guess what?
139    /// \deprecated
140    const ReachedMap& reachedMap() const { return *reached_map; }
141    /// Guess what?
142    /// \deprecated
143    typename ReachedMap::Value reached(const Node& n) const {
144      return (*reached_map)[n];
145    }
146    /// Guess what?
147    /// \deprecated
148    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
149  };
150
151  /// Bfs searches for the nodes wich are not marked in
152  /// \c reached_map
153  /// RM have to work as a read-write bool Node-map,
154  /// PM is a write edge node-map and
155  /// PNM is a write node node-map and
156  /// DM is a read-write node-map of integral value, have to be.
157  /// \ingroup galgs
158  template <typename Graph,
159            typename RM=typename Graph::template NodeMap<bool>,
160            typename PM
161            =typename Graph::template NodeMap<typename Graph::Edge>,
162            typename PNM
163            =typename Graph::template NodeMap<typename Graph::Node>,
164            typename DM=typename Graph::template NodeMap<int> >
165  class Bfs : public BfsIterator<Graph, RM> {
166    typedef BfsIterator<Graph, RM> Parent;
167  public:
168    typedef RM ReachedMap;
169    typedef PM PredMap;
170    typedef PNM PredNodeMap;
171    typedef DM DistMap;
172  protected:
173    typedef typename Parent::Node Node;
174    PredMap* pred_map;
175    PredNodeMap* pred_node_map;
176    DistMap* dist_map;
177    /// \e
178    Bfs<Graph, RM, PM, PNM, DM>
179    (const Graph& _graph) : BfsIterator<Graph, RM>(_graph) { }
180    /// PM have to be set before any bfs operation.
181    Bfs<Graph, RM, PM, PNM, DM>&
182    setPredMap(PredMap& _pred_map) {
183      pred_map=&_pred_map;
184    }
185    /// PredNodeMap have to be set before any bfs operation.
186    Bfs<Graph, RM, PM, PNM, DM>&
187    setPredNodeMap(PredNodeMap& _pred_node_map) {
188      pred_node_map=&_pred_node_map;
189    }
190    /// DistMap have to be set before any bfs operation.
191    Bfs<Graph, RM, PM, PNM, DM>&
192    setDistMap(DistMap& _dist_map) {
193      dist_map=&_dist_map;
194    }
195  public:
196    /// The algorithm will search in a bfs order for
197    /// the nodes which are \c false initially.
198    /// The constructor makes no initial changes on the maps.
199    Bfs<Graph, RM, PM, PNM, DM>
200    (const Graph& _graph, ReachedMap& _reached_map,
201     PredMap& _pred_map, PredNodeMap& _pred_node_map,
202     DistMap& _dist_map) : BfsIterator<Graph, RM>(_graph, _reached_map),
203      pred_map(&_pred_map), pred_node_map(&_pred_node_map),
204                           dist_map(&_dist_map) { }
205    /// \c s is marked to be reached and pushed in the bfs queue.
206    /// If the queue is empty, then the first out-edge is processed.
207    /// If \c s was not marked previously, then
208    /// in addition its pred_map is set to be \c INVALID,
209    /// and dist_map to \c 0.
210    /// if \c s was marked previuosly, then it is simply pushed.
211    Bfs<Graph, RM, PM, PNM, DM>& push(Node s) {
212      if ((*(this->reached_map))[s]) {
213        Parent::pushAndSetReached(s);
214      } else {
215        Parent::pushAndSetReached(s);
216        pred_map->set(s, INVALID);
217        pred_node_map->set(s, INVALID);
218        dist_map->set(s, 0);
219      }
220      return *this;
221    }
222    /// A bfs is processed from \c s.
223    Bfs<Graph, RM, PM, PNM, DM>& run(Node s) {
224      push(s);
225      while (!this->finished()) this->operator++();
226      return *this;
227    }
228    /// Beside the bfs iteration, \c pred_map and \dist_map are saved in a
229    /// newly reached node.
230    Bfs<Graph, RM, PM, PNM, DM>& operator++() {
231      Parent::operator++();
232      if ((this->actual_edge)!=INVALID && this->b_node_newly_reached)
233      {
234        pred_map->set(this->target(), this->actual_edge);
235        pred_node_map->set(this->target(), this->source());
236        dist_map->set(this->target(), (*dist_map)[this->source()]);
237      }
238      return *this;
239    }
240    /// Guess what?
241    /// \deprecated
242    const PredMap& predMap() const { return *pred_map; }
243    /// Guess what?
244    /// \deprecated
245    typename PredMap::Value pred(const Node& n) const {
246      return (*pred_map)[n];
247    }
248    /// Guess what?
249    /// \deprecated
250    const PredNodeMap& predNodeMap() const { return *pred_node_map; }
251    /// Guess what?
252    /// \deprecated
253    typename PredNodeMap::Value predNode(const Node& n) const {
254      return (*pred_node_map)[n];
255    }
256    /// Guess what?
257    /// \deprecated
258    const DistMap& distMap() const { return *dist_map; }
259    /// Guess what?
260    /// \deprecated
261    typename DistMap::Value dist(const Node& n) const {
262      return (*dist_map)[n];
263    }
264  };
265
266//   template <typename Graph,
267//          typename RM=typename Graph::template NodeMap<bool>,
268//          typename PM
269//          =typename Graph::template NodeMap<typename Graph::Edge>,
270//          typename PredNodeMap
271//          =typename Graph::template NodeMap<typename Graph::Node>,
272//          typename DistMap=typename Graph::template NodeMap<int> >
273//     class BfsWizard : public Bfs<Graph> {
274//     public:
275//       typedef Bfs<Graph, PM, PredNodeMap, DistMap> Parent;
276//     protected:
277//       typedef typename Parent::Node Node;
278//       bool own_reached_map;
279//       bool own_pred_map;
280//       bool own_pred_node_map;
281//       bool own_dist_map;
282
283//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
284//       makeRreached() {
285//      own_reached_map=true;
286//      reached=new ReachedMap(*graph, false);
287//       }
288//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
289//       deleteReachedMap() {
290//      own_reached_map=false;
291//      delete reached;
292//       }
293
294//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
295//       makePM() {
296//      own_pred_map=true;
297//      pred_map=new PM(*graph, INVALID);
298//       }
299//       BfsWizard<Graph, ReachedMap, PM, PredNodeMap, DistMap>&
300//       deletePM() {
301//      own_pred_map=false;
302//      delete pred_map;
303//       }
304
305//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
306//       makePredNodeMap() {
307//      own_pred_node_map=true;
308//      pred_node_map=new PredNodeMap(*graph, INVALID);
309//       }
310//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
311//       deletePredNodeMap() {
312//      own_pred_node_map=false;
313//      delete pred_node_map;
314//       }
315
316//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
317//       makeDistMap() {
318//      own_dist_map=true;
319//      dist_map=new DistMap(*graph, 0);
320//       }
321//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
322//       deleteDistMap() {
323//      own_dist_map=false;
324//      delete dist_map;
325//       }
326
327//     public:
328//       /// User friendly Bfs class.
329//       /// The maps which are not explicitly given by the user are
330//       /// constructed with false, INVALID, INVALID and 0 values.
331//       /// For the user defined maps, the values are not modified, and
332//       /// the bfs is processed without any preset on maps. Therefore,
333//       /// the bfs will search only the nodes which are set false previously
334//       /// in reached, and in the nodes wich are not newly reached by the
335//       /// search, the map values are not modified.
336//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>
337//       (const Graph& _graph) :
338//      own_reached_map(false),
339//      own_pred_map(false),
340//      own_pred_node_map(false),
341//      own_dist_map(false) {
342//       }
343
344//       /// \e
345//       ~BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>() {
346//      if (own_reached_map) deleteReachedMap();
347//      if (own_pred_map) deletePM();
348//      if (own_pred_node_map) deletePredNodeMap();
349//      if (own_dist_map) deleteDistMap();
350//       }
351
352//       /// \e
353//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
354//       setReachedMap(ReachedMap& _reached) {
355//      if (own_reached_map) deleteReachedMap();
356//      Parent::setReachedMap(_reached);
357//       }
358//       /// \e
359//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
360//       setPM(PM& _pred) {
361//      if (own_pred_map) deletePM();
362//      Parent::setPM(_pred);
363//       }
364//       /// \e
365//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
366//       setPredNodeMap(PredNodeMap& _pred_node) {
367//      if (own_pred_node_map) deletePredNodeMap();
368//      Parent::setPredNodeMap(_pred_node);
369//       }
370//       /// \e
371//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
372//       setDistMap(DistMap& _dist) {
373//      if (own_dist_map) deleteDistMap();
374//      Parent::setDistMap(_dist);
375//       }
376
377//       /// \e
378//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
379//       push(Node s) {
380//      if (!reached) makeReachedMap();
381//      if (!pred_map) makePMMap();
382//      if (!pred_node_map) makePredNodeMap();
383//      if (!dist_map) makeDistMap();
384//      push(s);
385//      return *this;
386//       }
387
388//       /// \e
389//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
390//       operator++() {
391//      if (!reached) makeRM();
392//      if (!pred_map) makePMMap();
393//      if (!pred_node_map) makePredNodeMap();
394//      if (!dist_map) makeDistMap();
395//      ++(*this);
396//      return *this;
397//       }
398
399//       /// \e
400//       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
401//       run(Node s) {
402//      if (!reached) makeRM();
403//      if (!pred_map) makePMMap();
404//      if (!pred_node_map) makePredNodeMap();
405//      if (!dist_map) makeDistMap();
406//      run(s);
407//      return *this;
408//       }
409     
410//     };
411
412
413  /// Dfs searches for the nodes wich are not marked in
414  /// \c reached_map
415  /// Reached have to be a read-write bool Node-map.
416  /// \ingroup galgs
417  template <typename Graph, /*typename OutEdgeIt,*/
418            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
419  class DfsIterator {
420  protected:
421    typedef typename Graph::Node Node;
422    typedef typename Graph::Edge Edge;
423    typedef typename Graph::OutEdgeIt OutEdgeIt;
424    const Graph* graph;
425    std::stack<OutEdgeIt> dfs_stack;
426    bool b_node_newly_reached;
427    Edge actual_edge;
428    Node actual_node;
429    ReachedMap& reached;
430    bool own_reached_map;
431  public:
432    /// In that constructor \c _reached have to be a reference
433    /// for a bool node-map. The algorithm will search in a dfs order for
434    /// the nodes which are \c false initially
435    DfsIterator(const Graph& _graph, ReachedMap& _reached) :
436      graph(&_graph), reached(_reached),
437      own_reached_map(false) { }
438    /// The same as above, but the map of reached nodes is
439    /// constructed dynamically
440    /// to everywhere false.
441    DfsIterator(const Graph& _graph) :
442      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
443      own_reached_map(true) { }
444    ~DfsIterator() { if (own_reached_map) delete &reached; }
445    /// This method markes s reached and first out-edge is processed.
446    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
447      actual_node=s;
448      reached.set(s, true);
449      OutEdgeIt e(*graph, s);
450      //graph->first(e, s);
451      dfs_stack.push(e);
452      return *this;
453    }
454    /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
455    /// its \c operator++() iterates on the edges in a dfs order.
456    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
457    operator++() {
458      actual_edge=dfs_stack.top();
459      if (actual_edge!=INVALID/*.valid()*/) {
460        Node w=graph->target(actual_edge);
461        actual_node=w;
462        if (!reached[w]) {
463          OutEdgeIt e(*graph, w);
464          //graph->first(e, w);
465          dfs_stack.push(e);
466          reached.set(w, true);
467          b_node_newly_reached=true;
468        } else {
469          actual_node=graph->source(actual_edge);
470          ++dfs_stack.top();
471          b_node_newly_reached=false;
472        }
473      } else {
474        //actual_node=G.aNode(dfs_stack.top());
475        dfs_stack.pop();
476      }
477      return *this;
478    }
479    /// Returns true iff the algorithm is finished.
480    bool finished() const { return dfs_stack.empty(); }
481    /// The conversion operator makes for converting the bfs-iterator
482    /// to an \c out-edge-iterator.
483    ///\bug Edge have to be in LEMON 0.2
484    operator Edge() const { return actual_edge; }
485    /// Returns if b-node has been reached just now.
486    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
487    /// Returns if a-node is examined.
488    bool isANodeExamined() const { return actual_edge==INVALID; }
489    /// Returns a-node of the actual edge, so does if the edge is invalid.
490    Node source() const { return actual_node; /*FIXME*/}
491    /// Returns b-node of the actual edge.
492    /// \pre The actual edge have to be valid.
493    Node target() const { return graph->target(actual_edge); }
494    /// Guess what?
495    /// \deprecated
496    const ReachedMap& getReachedMap() const { return reached; }
497    /// Guess what?
498    /// \deprecated
499    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
500  };
501
502  /// Dfs searches for the nodes wich are not marked in
503  /// \c reached_map
504  /// Reached is a read-write bool node-map,
505  /// Pred is a write node-map, have to be.
506  /// \ingroup galgs
507  template <typename Graph,
508            typename ReachedMap=typename Graph::template NodeMap<bool>,
509            typename PredMap
510            =typename Graph::template NodeMap<typename Graph::Edge> >
511  class Dfs : public DfsIterator<Graph, ReachedMap> {
512    typedef DfsIterator<Graph, ReachedMap> Parent;
513  protected:
514    typedef typename Parent::Node Node;
515    PredMap& pred;
516  public:
517    /// The algorithm will search in a dfs order for
518    /// the nodes which are \c false initially.
519    /// The constructor makes no initial changes on the maps.
520    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
521    /// \c s is marked to be reached and pushed in the bfs queue.
522    /// If the queue is empty, then the first out-edge is processed.
523    /// If \c s was not marked previously, then
524    /// in addition its pred is set to be \c INVALID.
525    /// if \c s was marked previuosly, then it is simply pushed.
526    Dfs<Graph, ReachedMap, PredMap>& push(Node s) {
527      if (this->reached[s]) {
528        Parent::pushAndSetReached(s);
529      } else {
530        Parent::pushAndSetReached(s);
531        pred.set(s, INVALID);
532      }
533      return *this;
534    }
535    /// A bfs is processed from \c s.
536    Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
537      push(s);
538      while (!this->finished()) this->operator++();
539      return *this;
540    }
541    /// Beside the dfs iteration, \c pred is saved in a
542    /// newly reached node.
543    Dfs<Graph, ReachedMap, PredMap>& operator++() {
544      Parent::operator++();
545      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
546      {
547        pred.set(this->target(), this->actual_edge);
548      }
549      return *this;
550    }
551    /// Guess what?
552    /// \deprecated
553    const PredMap& getPredMap() const { return pred; }
554  };
555
556  } // namespace marci
557} // namespace lemon
558
559#endif //LEMON_BFS_DFS_H
Note: See TracBrowser for help on using the repository browser.