COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bfs_iterator.h @ 433:d9fac1497298

Last change on this file since 433:d9fac1497298 was 415:679e64913c5e, checked in by marci, 20 years ago

for igcc-3.4.0

File size: 6.5 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(this->actual_edge) && this->b_node_newly_reached)
131      {
132        pred.set(this->bNode(), this->actual_edge);
133        dist.set(this->bNode(), dist[this->aNode()]);
134      }
135      return *this;
136    }
137    const PredMap& getPredMap() const { return pred; }
138    const DistMap& getDistMap() const { return dist; }
139  };
140
141  template <typename Graph, /*typename OutEdgeIt,*/
142            typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
143  class DfsIterator {
144  protected:
145    typedef typename Graph::Node Node;
146    typedef typename Graph::OutEdgeIt OutEdgeIt;
147    const Graph* graph;
148    std::stack<OutEdgeIt> dfs_stack;
149    bool b_node_newly_reached;
150    OutEdgeIt actual_edge;
151    Node actual_node;
152    ReachedMap& reached;
153    bool own_reached_map;
154  public:
155    DfsIterator(const Graph& _graph, ReachedMap& _reached) :
156      graph(&_graph), reached(_reached),
157      own_reached_map(false) { }
158    DfsIterator(const Graph& _graph) :
159      graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
160      own_reached_map(true) { }
161    ~DfsIterator() { if (own_reached_map) delete &reached; }
162    void pushAndSetReached(Node s) {
163      actual_node=s;
164      reached.set(s, true);
165      OutEdgeIt e;
166      graph->first(e, s);
167      dfs_stack.push(e);
168    }
169    DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
170    operator++() {
171      actual_edge=dfs_stack.top();
172      //actual_node=G.aNode(actual_edge);
173      if (graph->valid(actual_edge)/*.valid()*/) {
174        Node w=graph->bNode(actual_edge);
175        actual_node=w;
176        if (!reached[w]) {
177          OutEdgeIt e;
178          graph->first(e, w);
179          dfs_stack.push(e);
180          reached.set(w, true);
181          b_node_newly_reached=true;
182        } else {
183          actual_node=graph->aNode(actual_edge);
184          graph->next(dfs_stack.top());
185          b_node_newly_reached=false;
186        }
187      } else {
188        //actual_node=G.aNode(dfs_stack.top());
189        dfs_stack.pop();
190      }
191      return *this;
192    }
193    bool finished() const { return dfs_stack.empty(); }
194    operator OutEdgeIt() const { return actual_edge; }
195    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
196    bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
197    Node aNode() const { return actual_node; /*FIXME*/}
198    Node bNode() const { return graph->bNode(actual_edge); }
199    const ReachedMap& getReachedMap() const { return reached; }
200    const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
201  };
202
203} // namespace hugo
204
205#endif //HUGO_BFS_ITERATOR_H
Note: See TracBrowser for help on using the repository browser.