6 #include <marci_property_vector.hh>
10 template <typename graph_type>
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;
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) {
24 for(each_node_iterator i=G.first_node(); i.valid(); ++i)
25 reached.put(i, false);
31 while (!bfs_queue.empty()) {
32 node_iterator v=bfs_queue.front();
33 out_edge_iterator e=G.first_out_edge(v);
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;
41 dist.put(w, dist.get(v)+1);
45 std::cout << G.id(w) << " is already reached" << std::endl;
52 template <typename graph_type>
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;
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;
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;
71 template <typename graph_type, typename reached_type, typename visitor_type>
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;
77 std::queue<out_edge_iterator>& bfs_queue;
78 reached_type& reached;
79 visitor_type& visitor;
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));
91 visitor.at_previously_reached(e);
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(); }
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(); }
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(); }
114 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
115 if (bfs_queue.empty()) return false; else return true;
118 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
119 // if (bfs_queue.empty()) return true; else return false;
121 operator edge_iterator () { return bfs_queue.front(); }
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;
131 std::queue<out_edge_iterator>& bfs_queue;
132 reached_type& 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) {
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);
144 _newly_reached=false;
148 bfs_iterator1<graph_type, reached_type>& operator++() {
149 if (!valid()) return *this;
150 ++(bfs_queue.front());
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);
160 _newly_reached=false;
166 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
167 if (bfs_queue.empty()) return false; else return true;
169 operator edge_iterator () { return bfs_queue.front(); }
170 bool newly_reached() { return _newly_reached; }
176 #endif //MARCI_BFS_HH