contrib/brl/bbas/bgrl/bgrl_search

Go to the documentation of this file.
00001 // This is brl/bbas/bgrl/bgrl_search_func.cxx
00002 #include "bgrl_search_func.h"
00003 //:
00004 // \file
00005 
00006 #include "bgrl_vertex.h"
00007 #include "bgrl_edge.h"
00008 
00009 
00010 //: Breadth First Search
00011 bgrl_edge_sptr
00012 bgrl_breadth_search::next_vertex()
00013 {
00014   if (!curr_vertex_)
00015     return NULL;
00016 
00017   for ( bgrl_vertex::edge_iterator itr = curr_vertex_->begin();
00018         itr != curr_vertex_->end(); ++itr )
00019   {
00020     if ( visited_.find((*itr)->to()) == visited_.end() )
00021       eval_queue_.push_back(*itr);
00022   }
00023   while ( !eval_queue_.empty() && visited_.find(eval_queue_.front()->to()) != visited_.end() )
00024     eval_queue_.pop_front();
00025 
00026   if (eval_queue_.empty()){
00027     curr_vertex_ = NULL;
00028     return NULL;
00029   }
00030   else {
00031     bgrl_edge_sptr next = eval_queue_.front();
00032     curr_vertex_ = next->to();
00033     eval_queue_.pop_front();
00034     visited_.insert(curr_vertex_);
00035     return next;
00036   }
00037 }
00038 
00039 
00040 //=========================================================================
00041 
00042 //: Depth first search
00043 bgrl_edge_sptr
00044 bgrl_depth_search::next_vertex()
00045 {
00046   if (!curr_vertex_)
00047     return NULL;
00048 
00049   for ( bgrl_vertex::edge_iterator itr = curr_vertex_->begin();
00050         itr != curr_vertex_->end(); ++itr )
00051   {
00052     if ( visited_.find((*itr)->to()) == visited_.end() )
00053       eval_queue_.push_front(*itr);
00054   }
00055   while ( !eval_queue_.empty() && visited_.find(eval_queue_.front()->to()) != visited_.end() )
00056     eval_queue_.pop_front();
00057 
00058   if (eval_queue_.empty()){
00059     curr_vertex_ = NULL;
00060     return NULL;
00061   }
00062   else {
00063     bgrl_edge_sptr next = eval_queue_.front();
00064     curr_vertex_ = next->to();
00065     eval_queue_.pop_front();
00066     visited_.insert(curr_vertex_);
00067     return next;
00068   }
00069 }