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 @ 21:181b37336b29

Last change on this file since 21:181b37336b29 was 19:3151a1026db9, checked in by marci, 21 years ago

* empty log message *
File size: 6.0 KB
RevLine 
[9]1#ifndef MARCI_BFS_HH
2#define MARCI_BFS_HH
3
4#include <queue>
5
6#include <marci_property_vector.hh>
7
8namespace marci {
9
10  template <typename graph_type>
11  struct bfs {
[19]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;
[9]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);
[19]24      for(each_node_iterator i=G.first_node(); i.valid(); ++i)
[9]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();
[19]35        for( ; e.valid(); ++e) {
[9]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 {
[19]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;
[9]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 {
[19]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;
[9]76    graph_type& G;
77    std::queue<out_edge_iterator>& bfs_queue;
78    reached_type& reached;
79    visitor_type& visitor;
80    void process() {
[19]81      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
[9]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) {
[19]95      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
96      valid();
[9]97    }
98    bfs_iterator<graph_type, reached_type, visitor_type>& operator++() {
[19]99      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
[9]100      //if (bfs_queue.empty()) return *this;
[19]101      if (!valid()) return *this;
[9]102      ++(bfs_queue.front());
[19]103      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
104      valid();
[9]105      return *this;
106    }
107    //void next() {
[19]108    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
[9]109    //  if (bfs_queue.empty()) return;
110    //  ++(bfs_queue.front());
[19]111    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
[9]112    //}
[19]113    bool valid() {
114      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
[9]115      if (bfs_queue.empty()) return false; else return true;
116    }
117    //bool finished() {
[19]118    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
[9]119    //  if (bfs_queue.empty()) return true; else return false;
120    //}
121    operator edge_iterator () { return bfs_queue.front(); }
122
123  };
124
[11]125  template <typename graph_type, typename reached_type>
126  struct bfs_iterator1 {
[19]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;
[11]130    graph_type& G;
131    std::queue<out_edge_iterator>& bfs_queue;
132    reached_type& reached;
[19]133    bool _newly_reached;
[11]134    bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
[19]135      valid();
136      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
[11]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);
[19]142          _newly_reached=true;
[11]143        } else {
[19]144          _newly_reached=false;
[11]145        }
146      }
147    }
148    bfs_iterator1<graph_type, reached_type>& operator++() {
[19]149      if (!valid()) return *this;
[11]150      ++(bfs_queue.front());
[19]151      valid();
152      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
[11]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);
[19]158          _newly_reached=true;
[11]159        } else {
[19]160          _newly_reached=false;
[11]161        }
162      }
163      return *this;
164    }
[19]165    bool valid() {
166      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
[11]167      if (bfs_queue.empty()) return false; else return true;
168    }
169    operator edge_iterator () { return bfs_queue.front(); }
[19]170    bool newly_reached() { return _newly_reached; }
[11]171
172  };
[9]173
174} // namespace marci
175
176#endif //MARCI_BFS_HH
Note: See TracBrowser for help on using the repository browser.