lemon-0.x: src/work/marci_bfs.hh@d33813af6e50

     1 #ifndef MARCI_BFS_HH

     2 #define MARCI_BFS_HH

     4 #include <queue>

     6 #include <marci_graph_traits.hh>

     7 #include <marci_property_vector.hh>

     9 namespace marci {

    11   template <typename graph_type>

    12   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;

    18     graph_type& G;

    19     node_iterator s;

    20     node_property_vector<graph_type, bool> reached;

    21     node_property_vector<graph_type, edge_iterator> pred;

    22     node_property_vector<graph_type, int> dist;

    23     std::queue<node_iterator> bfs_queue;

    24     bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {

    25       bfs_queue.push(s);

    26       for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)

    27 	reached.put(i, false);

    28       reached.put(s, true);

    29       dist.put(s, 0);

    30     }

    32     void run() {

    33       while (!bfs_queue.empty()) {

    34 	node_iterator v=bfs_queue.front();

    35 	out_edge_iterator e=G.first_out_edge(v);

    36 	bfs_queue.pop();

    37 	for( ; e.is_valid(); ++e) {

    38 	  node_iterator w=G.head(e);

    39 	  std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;

    40 	  if (!reached.get(w)) {

    41 	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;

    42 	    bfs_queue.push(w);

    43 	    dist.put(w, dist.get(v)+1);

    44 	    pred.put(w, e);

    45 	    reached.put(w, true);

    46 	  } else {

    47 	    std::cout << G.id(w) << " is already reached" << std::endl;

    48 	  }

    49 	}

    50       }

    51     }

    52   };

    54   template <typename graph_type>

    55   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;

    60     graph_type& G;

    61     bfs_visitor(graph_type& _G) : G(_G) { }

    62     void at_previously_reached(out_edge_iterator& e) {

    63       //node_iterator v=G.tail(e);

    64       node_iterator w=G.head(e);

    65       std::cout << G.id(w) << " is already reached" << std::endl;

    66    }

    67     void at_newly_reached(out_edge_iterator& e) {

    68       //node_iterator v=G.tail(e);

    69       node_iterator w=G.head(e);

    70       std::cout << G.id(w) << " is newly reached :-)" << std::endl;

    71     }

    72   };

    74   template <typename graph_type, typename reached_type, typename visitor_type>

    75   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;

    81     graph_type& G;

    82     std::queue<out_edge_iterator>& bfs_queue;

    83     reached_type& reached;

    84     visitor_type& visitor;

    85     void process() {

    86       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }

    87       if (bfs_queue.empty()) return;

    88       out_edge_iterator e=bfs_queue.front();

    89       //node_iterator v=G.tail(e);

    90       node_iterator w=G.head(e);

    91       if (!reached.get(w)) {

    92 	visitor.at_newly_reached(e);

    93 	bfs_queue.push(G.first_out_edge(w));

    94 	reached.put(w, true);

    95       } else {

    96 	visitor.at_previously_reached(e);

    97       }

    98     }

    99     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();

   102     }

   103     bfs_iterator<graph_type, reached_type, visitor_type>& operator++() {

   104       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }

   105       //if (bfs_queue.empty()) return *this;

   106       if (!is_valid()) return *this;

   107       ++(bfs_queue.front());

   108       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }

   109       is_valid();

   110       return *this;

   111     }

   112     //void next() {

   113     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }

   114     //  if (bfs_queue.empty()) return;

   115     //  ++(bfs_queue.front());

   116     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }

   117     //}

   118     bool is_valid() {

   119       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }

   120       if (bfs_queue.empty()) return false; else return true;

   121     }

   122     //bool finished() {

   123     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }

   124     //  if (bfs_queue.empty()) return true; else return false;

   125     //}

   126     operator edge_iterator () { return bfs_queue.front(); }

   128   };

   130   template <typename graph_type, typename reached_type>

   131   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;

   137     graph_type& G;

   138     std::queue<out_edge_iterator>& bfs_queue;

   139     reached_type& reached;

   140     bool newly_reached;

   141     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()) {

   144 	out_edge_iterator e=bfs_queue.front();

   145 	node_iterator w=G.head(e);

   146 	if (!reached.get(w)) {

   147 	  bfs_queue.push(G.first_out_edge(w));

   148 	  reached.put(w, true);

   149 	  newly_reached=true;

   150 	} else {

   151 	  newly_reached=false;

   152 	}

   153       }

   154     }

   155     bfs_iterator1<graph_type, reached_type>& operator++() {

   156       if (!is_valid()) return *this;

   157       ++(bfs_queue.front());

   158       is_valid();

   159       if (!bfs_queue.empty() && bfs_queue.front().is_valid()) {

   160 	out_edge_iterator e=bfs_queue.front();

   161 	node_iterator w=G.head(e);

   162 	if (!reached.get(w)) {

   163 	  bfs_queue.push(G.first_out_edge(w));

   164 	  reached.put(w, true);

   165 	  newly_reached=true;

   166 	} else {

   167 	  newly_reached=false;

   168 	}

   169       }

   170       return *this;

   171     }

   172     bool is_valid() {

   173       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }

   174       if (bfs_queue.empty()) return false; else return true;

   175     }

   176     operator edge_iterator () { return bfs_queue.front(); }

   177     bool is_newly_reached() { return newly_reached; }

   179   };

   181 } // namespace marci

   183 #endif //MARCI_BFS_HH

author	marci
	Mon, 12 Jan 2004 11:49:56 +0000
changeset 13	d33813af6e50
parent 9	a9ed3f1c2c63
child 19	3151a1026db9
permissions	-rw-r--r--