src/work/marci/oldies/marci_bfs.hh
changeset 728 4c9e2f920458
equal deleted inserted replaced
-1:000000000000 0:21c657a8cca8
       
     1 #ifndef MARCI_BFS_HH
       
     2 #define MARCI_BFS_HH
       
     3 
       
     4 #include <queue>
       
     5 
       
     6 #include <marci_property_vector.hh>
       
     7 
       
     8 namespace hugo {
       
     9 
       
    10   template <typename graph_type>
       
    11   struct bfs {
       
    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;
       
    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); 
       
    24       for(each_node_iterator i=G.first_node(); i.valid(); ++i) 
       
    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();
       
    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;
       
    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 {
       
    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;
       
    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 {
       
    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;
       
    76     graph_type& G;
       
    77     std::queue<out_edge_iterator>& bfs_queue;
       
    78     reached_type& reached;
       
    79     visitor_type& visitor;
       
    80     void process() {
       
    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));
       
    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) { 
       
    95       //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
       
    96       valid();
       
    97     }
       
    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(); } 
       
   104       valid();
       
   105       return *this;
       
   106     }
       
   107     //void next() { 
       
   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(); } 
       
   112     //}
       
   113     bool valid() { 
       
   114       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
       
   115       if (bfs_queue.empty()) return false; else return true;
       
   116     }
       
   117     //bool finished() { 
       
   118     //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
       
   119     //  if (bfs_queue.empty()) return true; else return false;
       
   120     //}
       
   121     operator edge_iterator () { return bfs_queue.front(); }
       
   122 
       
   123   };
       
   124 
       
   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;
       
   130     graph_type& G;
       
   131     std::queue<out_edge_iterator>& bfs_queue;
       
   132     reached_type& reached;
       
   133     bool _newly_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) { 
       
   135       valid();
       
   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);
       
   142 	  _newly_reached=true;
       
   143 	} else {
       
   144 	  _newly_reached=false;
       
   145 	}
       
   146       }
       
   147     }
       
   148     bfs_iterator1<graph_type, reached_type>& operator++() { 
       
   149       if (!valid()) return *this;
       
   150       ++(bfs_queue.front());
       
   151       valid();
       
   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);
       
   158 	  _newly_reached=true;
       
   159 	} else {
       
   160 	  _newly_reached=false;
       
   161 	}
       
   162       }
       
   163       return *this;
       
   164     }
       
   165     bool valid() { 
       
   166       while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 
       
   167       if (bfs_queue.empty()) return false; else return true;
       
   168     }
       
   169     operator edge_iterator () { return bfs_queue.front(); }
       
   170     bool newly_reached() { return _newly_reached; }
       
   171 
       
   172   };
       
   173 
       
   174 } // namespace hugo
       
   175 
       
   176 #endif //MARCI_BFS_HH