COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci_bfs.hh @ 107:8d62f0072ff0

Last change on this file since 107:8d62f0072ff0 was 107:8d62f0072ff0, checked in by Alpar Juttner, 16 years ago

marci -> hugo
resize -> update

File size: 6.0 KB
Line 
1#ifndef MARCI_BFS_HH
2#define MARCI_BFS_HH
3
4#include <queue>
5
6#include <marci_property_vector.hh>
7
8namespace hugo {
9
10  template <typename graph_type>
11  struct bfs {
12    typedef typename graph_type::node_iterator node_iterator;
13    typedef typename graph_type::edge_iterator edge_iterator;
14    typedef typename graph_type::each_node_iterator each_node_iterator;
15    typedef typename graph_type::out_edge_iterator out_edge_iterator;
16    graph_type& G;
17    node_iterator s;
18    node_property_vector<graph_type, bool> reached;
19    node_property_vector<graph_type, edge_iterator> pred;
20    node_property_vector<graph_type, int> dist;
21    std::queue<node_iterator> bfs_queue;
22    bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
23      bfs_queue.push(s);
24      for(each_node_iterator i=G.first_node(); i.valid(); ++i)
25        reached.put(i, false);
26      reached.put(s, true);
27      dist.put(s, 0);
28    }
29   
30    void run() {
31      while (!bfs_queue.empty()) {
32        node_iterator v=bfs_queue.front();
33        out_edge_iterator e=G.first_out_edge(v);
34        bfs_queue.pop();
35        for( ; e.valid(); ++e) {
36          node_iterator w=G.head(e);
37          std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
38          if (!reached.get(w)) {
39            std::cout << G.id(w) << " is newly reached :-)" << std::endl;
40            bfs_queue.push(w);
41            dist.put(w, dist.get(v)+1);
42            pred.put(w, e);
43            reached.put(w, true);
44          } else {
45            std::cout << G.id(w) << " is already reached" << std::endl;
46          }
47        }
48      }
49    }
50  };
51
52  template <typename graph_type>
53  struct bfs_visitor {
54    typedef typename graph_type::node_iterator node_iterator;
55    typedef typename graph_type::edge_iterator edge_iterator;
56    typedef typename graph_type::out_edge_iterator out_edge_iterator;
57    graph_type& G;
58    bfs_visitor(graph_type& _G) : G(_G) { }
59    void at_previously_reached(out_edge_iterator& e) {
60      //node_iterator v=G.tail(e);
61      node_iterator w=G.head(e);
62      std::cout << G.id(w) << " is already reached" << std::endl;
63   }
64    void at_newly_reached(out_edge_iterator& e) {
65      //node_iterator v=G.tail(e);
66      node_iterator w=G.head(e);
67      std::cout << G.id(w) << " is newly reached :-)" << std::endl;
68    }
69  };
70
71  template <typename graph_type, typename reached_type, typename visitor_type>
72  struct bfs_iterator {
73    typedef typename graph_type::node_iterator node_iterator;
74    typedef typename graph_type::edge_iterator edge_iterator;
75    typedef typename graph_type::out_edge_iterator out_edge_iterator;
76    graph_type& G;
77    std::queue<out_edge_iterator>& bfs_queue;
78    reached_type& reached;
79    visitor_type& visitor;
80    void process() {
81      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
82      if (bfs_queue.empty()) return;
83      out_edge_iterator e=bfs_queue.front();
84      //node_iterator v=G.tail(e);
85      node_iterator w=G.head(e);
86      if (!reached.get(w)) {
87        visitor.at_newly_reached(e);
88        bfs_queue.push(G.first_out_edge(w));
89        reached.put(w, true);
90      } else {
91        visitor.at_previously_reached(e);
92      }
93    }
94    bfs_iterator(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
95      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
96      valid();
97    }
98    bfs_iterator<graph_type, reached_type, visitor_type>& operator++() {
99      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
100      //if (bfs_queue.empty()) return *this;
101      if (!valid()) return *this;
102      ++(bfs_queue.front());
103      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
104      valid();
105      return *this;
106    }
107    //void next() {
108    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
109    //  if (bfs_queue.empty()) return;
110    //  ++(bfs_queue.front());
111    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
112    //}
113    bool valid() {
114      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
115      if (bfs_queue.empty()) return false; else return true;
116    }
117    //bool finished() {
118    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
119    //  if (bfs_queue.empty()) return true; else return false;
120    //}
121    operator edge_iterator () { return bfs_queue.front(); }
122
123  };
124
125  template <typename graph_type, typename reached_type>
126  struct bfs_iterator1 {
127    typedef typename graph_type::node_iterator node_iterator;
128    typedef typename graph_type::edge_iterator edge_iterator;
129    typedef typename graph_type::out_edge_iterator out_edge_iterator;
130    graph_type& G;
131    std::queue<out_edge_iterator>& bfs_queue;
132    reached_type& reached;
133    bool _newly_reached;
134    bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
135      valid();
136      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
137        out_edge_iterator e=bfs_queue.front();
138        node_iterator w=G.head(e);
139        if (!reached.get(w)) {
140          bfs_queue.push(G.first_out_edge(w));
141          reached.put(w, true);
142          _newly_reached=true;
143        } else {
144          _newly_reached=false;
145        }
146      }
147    }
148    bfs_iterator1<graph_type, reached_type>& operator++() {
149      if (!valid()) return *this;
150      ++(bfs_queue.front());
151      valid();
152      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
153        out_edge_iterator e=bfs_queue.front();
154        node_iterator w=G.head(e);
155        if (!reached.get(w)) {
156          bfs_queue.push(G.first_out_edge(w));
157          reached.put(w, true);
158          _newly_reached=true;
159        } else {
160          _newly_reached=false;
161        }
162      }
163      return *this;
164    }
165    bool valid() {
166      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
167      if (bfs_queue.empty()) return false; else return true;
168    }
169    operator edge_iterator () { return bfs_queue.front(); }
170    bool newly_reached() { return _newly_reached; }
171
172  };
173
174} // namespace hugo
175
176#endif //MARCI_BFS_HH
Note: See TracBrowser for help on using the repository browser.