Skip to content

Instantly share code, notes, and snippets.

@samitok

samitok/bfs.cc

Last active December 16, 2018 17:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save samitok/a53917fe19362154356f2843369c1265 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save samitok/a53917fe19362154356f2843369c1265 to your computer and use it in GitHub Desktop.
Download ZIP
Breadth First Search implementation for path finding
Raw
bfs.cc
#include <iostream>
#include <list>
#include <unordered_set>
struct Node {
int index;
Node* parent;
std::list<Node*> children;
Node(int index, Node* parent) {
this->index = index;
this->parent = parent;
}
Node* InsertChild (int index) {
Node* child = new Node(index, this);
children.push_back(child);
return child;
}
};
class Mapper
{
private:
int* graph;
int height, width;
void PrintMap(int source_index, int target_index);
void DestroyNodes(Node* root);
public:
Mapper(int* graph, int width, int height) { // Constructor
this->graph = graph;
this->width = width;
this->height = height;
}
void ShortestPath(int source_index, int target_index);
int GetIndex(int x_ind, int y_ind) {
//check out of map
if(x_ind < 0 || x_ind >= width || y_ind < 0 || y_ind >= height)
return -1;
return x_ind + y_ind*width;
}
};
void Mapper::DestroyNodes(Node* root) {
for (auto const& child : root->children) {
DestroyNodes(child);
}
delete root;
}
void Mapper::PrintMap(int source_index, int target_index) {
for (int x = 0; x <= width; ++x) {
std::cout << "---";
}
std::cout <<'\n';
for (int y = 0; y < height; ++y) {
std::cout << "|";
for (int x = 0; x < width; ++x) {
std::string value = " ";
if(graph[GetIndex(x, y)] == 1)
value = "███";
else if(GetIndex(x, y) == source_index)
value = " S ";
else if(GetIndex(x, y) == target_index)
value = " * ";
else if(graph[GetIndex(x, y)] == -1)
value = " · ";
std::cout << value;
}
std::cout << " |";
std::cout <<'\n';
}
for (int x = 0; x <= width; ++x) {
std::cout << "---";
}
std::cout <<'\n';
}
// Prints shortest paths from src to all other vertices
void Mapper::ShortestPath(int source_index, int target_index)
{
bool done = false;
Node* root = new Node(source_index, nullptr);
Node* target = nullptr;
std::unordered_set<int> visited;
std::list<Node*>* leaf_nodes = new std::list<Node*>();
visited.insert(source_index);
leaf_nodes->push_back(root);
while(!leaf_nodes->empty()) {
std::list<Node*>* new_leafs = new std::list<Node*>();
for (auto const& leaf : *leaf_nodes) {
int x_ind = leaf->index % width;
int y_ind = leaf->index / width;
std::list<int> neighbours;
neighbours.push_back(GetIndex(x_ind-1, y_ind)); //left
neighbours.push_back(GetIndex(x_ind+1, y_ind)); //right
neighbours.push_back(GetIndex(x_ind, y_ind-1)); //bottom
neighbours.push_back(GetIndex(x_ind, y_ind+1)); //top
for (auto const& neighbour : neighbours) {
if (neighbour != -1) {
if (graph[neighbour] == 0 &&
(visited.find(neighbour) == visited.end())) {
//newly reached node
visited.insert(neighbour);
leaf->InsertChild(neighbour);
Node* new_leaf = leaf->InsertChild(neighbour);
new_leafs->push_back(new_leaf);
if(neighbour == target_index) {
done = true;
target = new_leaf;
}
}
}
} //for (auto const& neighbour : neighbours)
} // for (auto const& leaf : leaf_nodes)
delete leaf_nodes;
leaf_nodes = new_leafs;
if(done) break;
}
delete leaf_nodes;
std::cout << "Map\n";
PrintMap(source_index, target_index);
if (done) {
Node* step = target;
while (step->parent != nullptr) {
graph[step->index] = -1;
step = step->parent;
}
std::cout << "Solution Map\n";
PrintMap(source_index, target_index);
}
else {
std::cout << "No paths found!!!" << std::endl;
}
DestroyNodes(root);
}
int main()
{
int width = 10;
int height = 12;
int map[height][width] = {
{1, 1, 0, 0, 0, 0, 1, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 1, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 1, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 1, 1, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0}
};
Mapper dfs(&map[0][0], width, height);
dfs.ShortestPath(54, 106);
return 0;
}
Raw
build.sh
g++ -Wall -Wextra -Werror bfs.cc -o prog
Raw
output
Map
---------------------------------
|██████ ███ |
|█████████ ███ |
| ███ |
| ███ ██████ |
| ███ ███ |
| ███ S ███ |
| █████████ ███ |
| ███ ███ |
| ██████ ███ |
| ███ █████████ |
| ███ * |
| ███ |
---------------------------------
Solution Map
---------------------------------
|██████ ███ |
|█████████ ███ |
| · · · · ███ |
| · ███ · ██████ |
| · ███ · ███ |
| · ███ S ███ · · · |
| · █████████ · ███ · |
| · ███ · ███ · |
| · ██████ · · · ███ · |
| · ███ · · █████████ · |
| · · · ███ * · · |
| ███ |
---------------------------------
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment