Changeset 19:3151a1026db9 in lemon0.x for src/work/marci_bfs.hh
 Timestamp:
 01/20/04 18:39:13 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@32
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci_bfs.hh
r11 r19 4 4 #include <queue> 5 5 6 #include <marci_graph_traits.hh>7 6 #include <marci_property_vector.hh> 8 7 … … 11 10 template <typename graph_type> 12 11 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 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 16 graph_type& G; 19 17 node_iterator s; … … 24 22 bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 25 23 bfs_queue.push(s); 26 for(each_node_iterator i=G.first_node(); i. is_valid(); ++i)24 for(each_node_iterator i=G.first_node(); i.valid(); ++i) 27 25 reached.put(i, false); 28 26 reached.put(s, true); … … 35 33 out_edge_iterator e=G.first_out_edge(v); 36 34 bfs_queue.pop(); 37 for( ; e. is_valid(); ++e) {35 for( ; e.valid(); ++e) { 38 36 node_iterator w=G.head(e); 39 37 std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; … … 54 52 template <typename graph_type> 55 53 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; 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; 60 57 graph_type& G; 61 58 bfs_visitor(graph_type& _G) : G(_G) { } … … 74 71 template <typename graph_type, typename reached_type, typename visitor_type> 75 72 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 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; 81 76 graph_type& G; 82 77 std::queue<out_edge_iterator>& bfs_queue; … … 84 79 visitor_type& visitor; 85 80 void process() { 86 while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }81 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 87 82 if (bfs_queue.empty()) return; 88 83 out_edge_iterator e=bfs_queue.front(); … … 98 93 } 99 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) { 100 //while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }101 is_valid();95 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 96 valid(); 102 97 } 103 98 bfs_iterator<graph_type, reached_type, visitor_type>& operator++() { 104 //while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }99 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 105 100 //if (bfs_queue.empty()) return *this; 106 if (! is_valid()) return *this;101 if (!valid()) return *this; 107 102 ++(bfs_queue.front()); 108 //while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }109 is_valid();103 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 104 valid(); 110 105 return *this; 111 106 } 112 107 //void next() { 113 // while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }108 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 114 109 // if (bfs_queue.empty()) return; 115 110 // ++(bfs_queue.front()); 116 // while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }111 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 117 112 //} 118 bool is_valid() {119 while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }113 bool valid() { 114 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 120 115 if (bfs_queue.empty()) return false; else return true; 121 116 } 122 117 //bool finished() { 123 // while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }118 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 124 119 // if (bfs_queue.empty()) return true; else return false; 125 120 //} … … 130 125 template <typename graph_type, typename reached_type> 131 126 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 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; 137 130 graph_type& G; 138 131 std::queue<out_edge_iterator>& bfs_queue; 139 132 reached_type& reached; 140 bool newly_reached;133 bool _newly_reached; 141 134 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()) {135 valid(); 136 if (!bfs_queue.empty() && bfs_queue.front().valid()) { 144 137 out_edge_iterator e=bfs_queue.front(); 145 138 node_iterator w=G.head(e); … … 147 140 bfs_queue.push(G.first_out_edge(w)); 148 141 reached.put(w, true); 149 newly_reached=true;142 _newly_reached=true; 150 143 } else { 151 newly_reached=false;144 _newly_reached=false; 152 145 } 153 146 } 154 147 } 155 148 bfs_iterator1<graph_type, reached_type>& operator++() { 156 if (! is_valid()) return *this;149 if (!valid()) return *this; 157 150 ++(bfs_queue.front()); 158 is_valid();159 if (!bfs_queue.empty() && bfs_queue.front(). is_valid()) {151 valid(); 152 if (!bfs_queue.empty() && bfs_queue.front().valid()) { 160 153 out_edge_iterator e=bfs_queue.front(); 161 154 node_iterator w=G.head(e); … … 163 156 bfs_queue.push(G.first_out_edge(w)); 164 157 reached.put(w, true); 165 newly_reached=true;158 _newly_reached=true; 166 159 } else { 167 newly_reached=false;160 _newly_reached=false; 168 161 } 169 162 } 170 163 return *this; 171 164 } 172 bool is_valid() {173 while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }165 bool valid() { 166 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 174 167 if (bfs_queue.empty()) return false; else return true; 175 168 } 176 169 operator edge_iterator () { return bfs_queue.front(); } 177 bool is_newly_reached() { returnnewly_reached; }170 bool newly_reached() { return _newly_reached; } 178 171 179 172 };
Note: See TracChangeset
for help on using the changeset viewer.