COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_iterator.h @ 409:7ab7f083760a

Last change on this file since 409:7ab7f083760a was 409:7ab7f083760a, checked in by marci, 17 years ago

stGraphWrapper is almost working

File size: 6.4 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_BFS_ITERATOR_H
3#define HUGO_BFS_ITERATOR_H
4
5#include <queue>
6#include <stack>
7#include <utility>
8
9namespace hugo {
10
11  template <typename Graph, /*typename OutEdgeIt,*/
12            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
13  class BfsIterator {
14  protected:
15    typedef typename Graph::Node Node;
16    typedef typename Graph::OutEdgeIt OutEdgeIt;
17    const Graph* graph;
18    std::queue<Node> bfs_queue;
19    ReachedMap& reached;
20    bool b_node_newly_reached;
21    OutEdgeIt actual_edge;
22    bool own_reached_map;
23  public:
24    BfsIterator(const Graph& _graph, ReachedMap& _reached) :
25      graph(&_graph), reached(_reached),
26      own_reached_map(false) { }
27    BfsIterator(const Graph& _graph) :
28      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
29      own_reached_map(true) { }
30    ~BfsIterator() { if (own_reached_map) delete &reached; }
31    //s is marcked reached.
32    //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe.
33    //is the queue is not empty, then is it pushed.
34    void pushAndSetReached(Node s) {
35      reached.set(s, true);
36      if (bfs_queue.empty()) {
37        bfs_queue.push(s);
38        graph->first(actual_edge, s);
39        if (graph->valid(actual_edge)) {
40          Node w=graph->bNode(actual_edge);
41          if (!reached[w]) {
42            bfs_queue.push(w);
43            reached.set(w, true);
44            b_node_newly_reached=true;
45          } else {
46            b_node_newly_reached=false;
47          }
48        }
49      } else {
50        bfs_queue.push(s);
51      }
52    }
53    BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
54    operator++() {
55      if (graph->valid(actual_edge)) {
56        graph->next(actual_edge);
57        if (graph->valid(actual_edge)) {
58          Node w=graph->bNode(actual_edge);
59          if (!reached[w]) {
60            bfs_queue.push(w);
61            reached.set(w, true);
62            b_node_newly_reached=true;
63          } else {
64            b_node_newly_reached=false;
65          }
66        }
67      } else {
68        bfs_queue.pop();
69        if (!bfs_queue.empty()) {
70          graph->first(actual_edge, bfs_queue.front());
71          if (graph->valid(actual_edge)) {
72            Node w=graph->bNode(actual_edge);
73            if (!reached[w]) {
74              bfs_queue.push(w);
75              reached.set(w, true);
76              b_node_newly_reached=true;
77            } else {
78              b_node_newly_reached=false;
79            }
80          }
81        }
82      }
83      return *this;
84    }
85    bool finished() const { return bfs_queue.empty(); }
86    operator OutEdgeIt() const { return actual_edge; }
87    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
88    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
89    Node aNode() const { return bfs_queue.front(); }
90    Node bNode() const { return graph->bNode(actual_edge); }
91    const ReachedMap& getReachedMap() const { return reached; }
92    const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
93  }; 
94
95  /// Bfs searches from s for the nodes wich are not marked in
96  /// reachedmap
97  template <typename Graph,
98            typename ReachedMap=typename Graph::template NodeMap<bool>,
99            typename PredMap
100            =typename Graph::template NodeMap<typename Graph::Edge>,
101            typename DistMap=typename Graph::template NodeMap<int> >
102  class Bfs : public BfsIterator<Graph, ReachedMap> {
103    typedef BfsIterator<Graph, ReachedMap> Parent;
104  protected:
105    typedef typename Parent::Node Node;
106    PredMap& pred;
107    DistMap& dist;
108  public:
109    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
110    //s is marked to be reached and pushed in the bfs queue.
111    //if the queue is empty, then the first out-edge is processed
112    //If s was not marked previously, then
113    //in addition its pred is set to be INVALID, and dist to 0.
114    //if s was marked previuosly, then it is simply pushed.
115    void push(Node s) {
116      if (this->reached[s]) {
117        Parent::pushAndSetReached(s);
118      } else {
119        Parent::pushAndSetReached(s);
120        pred.set(s, INVALID);
121        dist.set(s, 0);
122      }
123    }
124    void run(Node s) {
125      push(s);
126      while (!this->finished()) this->operator++();
127    }
128    Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
129      Parent::operator++();
130      if (this->graph->valid(actual_edge) && this->b_node_newly_reached) {
131        pred.set(s, actual_edge);
132        dist.set(s, dist[this->aNode()]);
133      }
134      return *this;
135    }
136    const PredMap& getPredMap() const { return pred; }
137    const DistMap& getDistMap() const { return dist; }
138  };
139
140  template <typename Graph, /*typename OutEdgeIt,*/
141            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
142  class DfsIterator {
143  protected:
144    typedef typename Graph::Node Node;
145    typedef typename Graph::OutEdgeIt OutEdgeIt;
146    const Graph* graph;
147    std::stack<OutEdgeIt> dfs_stack;
148    bool b_node_newly_reached;
149    OutEdgeIt actual_edge;
150    Node actual_node;
151    ReachedMap& reached;
152    bool own_reached_map;
153  public:
154    DfsIterator(const Graph& _graph, ReachedMap& _reached) :
155      graph(&_graph), reached(_reached),
156      own_reached_map(false) { }
157    DfsIterator(const Graph& _graph) :
158      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
159      own_reached_map(true) { }
160    ~DfsIterator() { if (own_reached_map) delete &reached; }
161    void pushAndSetReached(Node s) {
162      actual_node=s;
163      reached.set(s, true);
164      OutEdgeIt e;
165      graph->first(e, s);
166      dfs_stack.push(e);
167    }
168    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
169    operator++() {
170      actual_edge=dfs_stack.top();
171      //actual_node=G.aNode(actual_edge);
172      if (graph->valid(actual_edge)/*.valid()*/) {
173        Node w=graph->bNode(actual_edge);
174        actual_node=w;
175        if (!reached[w]) {
176          OutEdgeIt e;
177          graph->first(e, w);
178          dfs_stack.push(e);
179          reached.set(w, true);
180          b_node_newly_reached=true;
181        } else {
182          actual_node=graph->aNode(actual_edge);
183          graph->next(dfs_stack.top());
184          b_node_newly_reached=false;
185        }
186      } else {
187        //actual_node=G.aNode(dfs_stack.top());
188        dfs_stack.pop();
189      }
190      return *this;
191    }
192    bool finished() const { return dfs_stack.empty(); }
193    operator OutEdgeIt() const { return actual_edge; }
194    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
195    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
196    Node aNode() const { return actual_node; /*FIXME*/}
197    Node bNode() const { return graph->bNode(actual_edge); }
198    const ReachedMap& getReachedMap() const { return reached; }
199    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
200  };
201
202} // namespace hugo
203
204#endif //HUGO_BFS_ITERATOR_H
Note: See TracBrowser for help on using the repository browser.