/ Published in: C++
Expand |
Embed | Plain Text
#include <iostream> #include <vector> #include <map> #include <queue> using namespace std; std::vector<std::vector<long> > BreathFirstSearch(std::multimap<long,long> dimensionDetails,long start,long end ) { std::vector<std::vector<long> > complete_path; std::queue<std::vector<long> > path_queue; std::vector<long> tmp_path; tmp_path.push_back(start); path_queue.push(tmp_path); /* while q.IsEmpty() == False: tmp_path = q.dequeue() last_node = tmp_path[len(tmp_path)-1] print tmp_path if last_node == end: print "VALID_PATH : ",tmp_path for link_node in graph[last_node]: if link_node not in tmp_path: #new_path = [] new_path = tmp_path + [link_node] q.enqueue(new_path) */ long last_node = -1; while (!path_queue.empty()) { tmp_path = path_queue.front(); path_queue.pop(); //get last node from temp path last_node = tmp_path[tmp_path.size()-1]; if (last_node == end) {//add the path to return vector complete_path.push_back(tmp_path); } //create path using following child node which is not in the tmp_path multimap<long,long>::iterator path_child_node; pair<multimap<long,long>::iterator,multimap<long,long >::iterator> connected_node_iterator; connected_node_iterator = dimensionDetails.equal_range(last_node); for( path_child_node = connected_node_iterator.first; path_child_node!= connected_node_iterator.second; ++path_child_node ) { //if path_child_node second should be added to path provided it is not in tmp_path already //followed by adding the child node to the queue vector<long>::iterator result; if(tmp_path.end() == find( tmp_path.begin(), tmp_path.end(), (*path_child_node).second)) { //add the child to current path and add the same to queue std::vector<long> temp; //temp.erase(temp.begin(),temp.end()); temp.resize (tmp_path.size()); copy (tmp_path.begin(), tmp_path.end(), // source temp.begin()); // destination temp.push_back((*path_child_node).second); path_queue.push(temp); } } } return complete_path; } int main() { vector<std::pair<long,long> > vecDimension; vecDimension.push_back(pair<long,long>(4,2)); vecDimension.push_back(pair<long,long>(2,5)); vecDimension.push_back(pair<long,long>(5,11)); vecDimension.push_back(pair<long,long>(11,12)); vecDimension.push_back(pair<long,long>(2,3)); vecDimension.push_back(pair<long,long>(3,6)); vecDimension.push_back(pair<long,long>(6,7)); //convert the vector to map multimap<long,long> dimensionDetails; dimensionDetails.insert(pair<long,long>(4,2)); dimensionDetails.insert(pair<long,long>(2,5)); dimensionDetails.insert(pair<long,long>(5,11)); dimensionDetails.insert(pair<long,long>(11,12)); dimensionDetails.insert(pair<long,long>(2,3)); dimensionDetails.insert(pair<long,long>(3,6)); dimensionDetails.insert(pair<long,long>(6,7)); dimensionDetails.insert(pair<long,long>(5,6)); dimensionDetails.insert(pair<long,long>(6,8)); //reverse insert dimensionDetails.insert(pair<long,long>(2,4)); dimensionDetails.insert(pair<long,long>(5,2)); dimensionDetails.insert(pair<long,long>(11,5)); dimensionDetails.insert(pair<long,long>(12,11)); dimensionDetails.insert(pair<long,long>(3,2)); dimensionDetails.insert(pair<long,long>(6,3)); dimensionDetails.insert(pair<long,long>(7,6)); dimensionDetails.insert(pair<long,long>(6,5)); dimensionDetails.insert(pair<long,long>(8,6)); BreathFirstSearch(dimensionDetails,4,7); bool a = true; if(a == true) }
You need to login to post a comment.
