Changeset 19:3151a1026db9 in lemon-0.x for src/work/marci_bfs.hh

Timestamp:

01/20/04 18:39:13 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@32

Message:

* empty log message *

File:

• src/work/marci_bfs.hh (modified) (11 diffs)

src/work/marci_bfs.hh

@@ -4 +4 @@
 #include <queue>
 
-#include <marci_graph_traits.hh>
 #include <marci_property_vector.hh>
 
@@ -11 +10 @@
   template <typename graph_type>
   struct bfs {
-    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
-    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
-    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
-    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
-
+    typedef typename graph_type::node_iterator node_iterator;
+    typedef typename graph_type::edge_iterator edge_iterator;
+    typedef typename graph_type::each_node_iterator each_node_iterator;
+    typedef typename graph_type::out_edge_iterator out_edge_iterator;
     graph_type& G;
     node_iterator s;
@@ -24 +22 @@
     bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 
       bfs_queue.push(s); 
-      for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) 
+      for(each_node_iterator i=G.first_node(); i.valid(); ++i) 
         reached.put(i, false);
       reached.put(s, true);
@@ -35 +33 @@
         out_edge_iterator e=G.first_out_edge(v);
         bfs_queue.pop();
-        for( ; e.is_valid(); ++e) {
+        for( ; e.valid(); ++e) {
           node_iterator w=G.head(e);
           std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
@@ -54 +52 @@
   template <typename graph_type> 
   struct bfs_visitor {
-    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
-    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
-    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
-    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
+    typedef typename graph_type::node_iterator node_iterator;
+    typedef typename graph_type::edge_iterator edge_iterator;
+    typedef typename graph_type::out_edge_iterator out_edge_iterator;
     graph_type& G;
     bfs_visitor(graph_type& _G) : G(_G) { }
@@ -74 +71 @@
   template <typename graph_type, typename reached_type, typename visitor_type>
   struct bfs_iterator {
-    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
-    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
-    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
-    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
-
+    typedef typename graph_type::node_iterator node_iterator;
+    typedef typename graph_type::edge_iterator edge_iterator;
+    typedef typename graph_type::out_edge_iterator out_edge_iterator;
     graph_type& G;
     std::queue<out_edge_iterator>& bfs_queue;
@@ -84 +79 @@
     visitor_type& visitor;
     void process() {
-      while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
       if (bfs_queue.empty()) return;
       out_edge_iterator e=bfs_queue.front();
@@ -98 +93 @@
     }
     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) { 
-      //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
-      is_valid();
+      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
+      valid();
     }
     bfs_iterator<graph_type, reached_type, visitor_type>& operator++() { 
-      //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
       //if (bfs_queue.empty()) return *this;
-      if (!is_valid()) return *this;
+      if (!valid()) return *this;
       ++(bfs_queue.front());
-      //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
-      is_valid();
+      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
+      valid();
       return *this;
     }
     //void next() { 
-    //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
     //  if (bfs_queue.empty()) return;
     //  ++(bfs_queue.front());
-    //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
     //}
-    bool is_valid() { 
-      while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+    bool valid() { 
+      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
       if (bfs_queue.empty()) return false; else return true;
     }
     //bool finished() { 
-    //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
     //  if (bfs_queue.empty()) return true; else return false;
     //}
@@ -130 +125 @@
   template <typename graph_type, typename reached_type>
   struct bfs_iterator1 {
-    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
-    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
-    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
-    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
-
+    typedef typename graph_type::node_iterator node_iterator;
+    typedef typename graph_type::edge_iterator edge_iterator;
+    typedef typename graph_type::out_edge_iterator out_edge_iterator;
     graph_type& G;
     std::queue<out_edge_iterator>& bfs_queue;
     reached_type& reached;
-    bool newly_reached;
+    bool _newly_reached;
     bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
-      is_valid();
-      if (!bfs_queue.empty() && bfs_queue.front().is_valid()) { 
+      valid();
+      if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
         out_edge_iterator e=bfs_queue.front();
         node_iterator w=G.head(e);
@@ -147 +140 @@
           bfs_queue.push(G.first_out_edge(w));
           reached.put(w, true);
-          newly_reached=true;
+          _newly_reached=true;
         } else {
-          newly_reached=false;
+          _newly_reached=false;
         }
       }
     }
     bfs_iterator1<graph_type, reached_type>& operator++() { 
-      if (!is_valid()) return *this;
+      if (!valid()) return *this;
       ++(bfs_queue.front());
-      is_valid();
-      if (!bfs_queue.empty() && bfs_queue.front().is_valid()) { 
+      valid();
+      if (!bfs_queue.empty() && bfs_queue.front().valid()) { 
         out_edge_iterator e=bfs_queue.front();
         node_iterator w=G.head(e);
@@ -163 +156 @@
           bfs_queue.push(G.first_out_edge(w));
           reached.put(w, true);
-          newly_reached=true;
+          _newly_reached=true;
         } else {
-          newly_reached=false;
+          _newly_reached=false;
         }
       }
       return *this;
     }
-    bool is_valid() { 
-      while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+    bool valid() { 
+      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
       if (bfs_queue.empty()) return false; else return true;
     }
     operator edge_iterator () { return bfs_queue.front(); }
-    bool is_newly_reached() { return newly_reached; }
+    bool newly_reached() { return _newly_reached; }
 
   };