COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-0.x/src/work/marci_bfs.hh @ 18:7c88989ea45b

Last change on this file since 18:7c88989ea45b was 11:33a84426c221, checked in by marci, 20 years ago

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