Posted By

yesraaj on 07/02/10


Tagged

bfs


Versions (?)

Who likes this?

1 person have marked this snippet as a favorite

khouser


C++ BFS


 / Published in: C++
 

  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <queue>
  5.  
  6. using namespace std;
  7. std::vector<std::vector<long> >
  8. BreathFirstSearch(std::multimap<long,long> dimensionDetails,long start,long end )
  9. {
  10. std::vector<std::vector<long> > complete_path;
  11. std::queue<std::vector<long> > path_queue;
  12. std::vector<long> tmp_path;
  13. tmp_path.push_back(start);
  14. path_queue.push(tmp_path);
  15. /*
  16. while q.IsEmpty() == False:
  17.   tmp_path = q.dequeue()
  18.   last_node = tmp_path[len(tmp_path)-1]
  19.   print tmp_path
  20.   if last_node == end:
  21.   print "VALID_PATH : ",tmp_path
  22.   for link_node in graph[last_node]:
  23.   if link_node not in tmp_path:
  24.   #new_path = []
  25.   new_path = tmp_path + [link_node]
  26.   q.enqueue(new_path)
  27. */
  28. long last_node = -1;
  29. while (!path_queue.empty())
  30. {
  31. tmp_path = path_queue.front();
  32. path_queue.pop();
  33.  
  34. //get last node from temp path
  35. last_node = tmp_path[tmp_path.size()-1];
  36. if (last_node == end)
  37. {//add the path to return vector
  38. complete_path.push_back(tmp_path);
  39.  
  40. }
  41. //create path using following child node which is not in the tmp_path
  42. multimap<long,long>::iterator path_child_node;
  43. pair<multimap<long,long>::iterator,multimap<long,long >::iterator> connected_node_iterator;
  44. connected_node_iterator = dimensionDetails.equal_range(last_node);
  45.  
  46. for( path_child_node = connected_node_iterator.first;
  47. path_child_node!= connected_node_iterator.second;
  48. ++path_child_node )
  49. {
  50. //if path_child_node second should be added to path provided it is not in tmp_path already
  51. //followed by adding the child node to the queue
  52. vector<long>::iterator result;
  53. if(tmp_path.end() == find( tmp_path.begin(), tmp_path.end(), (*path_child_node).second))
  54. {
  55. //add the child to current path and add the same to queue
  56. std::vector<long> temp;
  57. //temp.erase(temp.begin(),temp.end());
  58. temp.resize (tmp_path.size());
  59. copy (tmp_path.begin(), tmp_path.end(), // source
  60. temp.begin()); // destination
  61.  
  62. temp.push_back((*path_child_node).second);
  63. path_queue.push(temp);
  64.  
  65. }
  66. }
  67. }
  68.  
  69. return complete_path;
  70. }
  71. int main()
  72. {
  73. vector<std::pair<long,long> > vecDimension;
  74. vecDimension.push_back(pair<long,long>(4,2));
  75. vecDimension.push_back(pair<long,long>(2,5));
  76. vecDimension.push_back(pair<long,long>(5,11));
  77. vecDimension.push_back(pair<long,long>(11,12));
  78. vecDimension.push_back(pair<long,long>(2,3));
  79. vecDimension.push_back(pair<long,long>(3,6));
  80. vecDimension.push_back(pair<long,long>(6,7));
  81.  
  82. //convert the vector to map
  83. multimap<long,long> dimensionDetails;
  84.  
  85. dimensionDetails.insert(pair<long,long>(4,2));
  86. dimensionDetails.insert(pair<long,long>(2,5));
  87. dimensionDetails.insert(pair<long,long>(5,11));
  88. dimensionDetails.insert(pair<long,long>(11,12));
  89. dimensionDetails.insert(pair<long,long>(2,3));
  90. dimensionDetails.insert(pair<long,long>(3,6));
  91. dimensionDetails.insert(pair<long,long>(6,7));
  92. dimensionDetails.insert(pair<long,long>(5,6));
  93. dimensionDetails.insert(pair<long,long>(6,8));
  94.  
  95. //reverse insert
  96.  
  97. dimensionDetails.insert(pair<long,long>(2,4));
  98. dimensionDetails.insert(pair<long,long>(5,2));
  99. dimensionDetails.insert(pair<long,long>(11,5));
  100. dimensionDetails.insert(pair<long,long>(12,11));
  101. dimensionDetails.insert(pair<long,long>(3,2));
  102. dimensionDetails.insert(pair<long,long>(6,3));
  103. dimensionDetails.insert(pair<long,long>(7,6));
  104. dimensionDetails.insert(pair<long,long>(6,5));
  105. dimensionDetails.insert(pair<long,long>(8,6));
  106. BreathFirstSearch(dimensionDetails,4,7);
  107. bool a = true;
  108. if(a == true)
  109.  
  110. }

Report this snippet  

You need to login to post a comment.