fueanta

BFS [ Breadth First Search ]

Nov 29th, 2017
173
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class BFS
  2. {
  3.     Graph* _graph;
  4.     int _source;
  5.     int* _parent;
  6.     int* _level;
  7.     int* _color;
  8.     bool _bipartite;
  9.  
  10.     std::vector<int>* _bfsQueue;
  11.  
  12.     void init(int);
  13.     void path_rec(int);
  14. public:
  15.     BFS(Graph*, int);
  16.     ~BFS();
  17.  
  18.     void breadhFirstSearch();
  19.     void printPath(int);
  20.     void printDetails();
  21. };
  22.  
  23. BFS::BFS(Graph* graph, int source)
  24. {
  25.     this->_graph = graph;
  26.     this->init(source);
  27. }
  28.  
  29. BFS::~BFS()
  30. {
  31.     delete[] this->_parent;
  32.     delete[] this->_level;
  33.     delete _bfsQueue;
  34. }
  35.  
  36. void BFS::init(int source)
  37. {
  38.     this->_source = source;
  39.     this->_bipartite = true;
  40.     this->_parent = new int[this->_graph->getVertexCount()];
  41.     this->_level = new int[this->_graph->getVertexCount()];
  42.     this->_color = new int[this->_graph->getVertexCount()];
  43.     this->_bfsQueue = new std::vector<int>();
  44.  
  45.     for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  46.     {
  47.         _parent[i] = _level[i] = _color[i] = -1;
  48.     }
  49. }
  50.  
  51. void BFS::path_rec(int destination)
  52. {
  53.     if (this->_source == destination)
  54.         cout << this->_source << " ";
  55.     else if (this->_parent[destination] == -1)
  56.         cout << "no path";
  57.     else
  58.     {
  59.         path_rec(this->_parent[destination]);
  60.         cout << destination << " ";
  61.     }
  62. }
  63.  
  64. void BFS::breadhFirstSearch()
  65. {
  66.     std::queue<int> bfs_Q;
  67.     this->_level[this->_source] = 0;
  68.     this->_color[this->_source] = 0;
  69.     bfs_Q.push(this->_source);
  70.     // bfs_queue->push_back(this->_source);
  71.  
  72.     while (!bfs_Q.empty())
  73.     {
  74.         int node = bfs_Q.front();
  75.         bfs_Q.pop();
  76.  
  77.         for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  78.         {
  79.             if (this->_graph->hasEdgeBetween(node, i))
  80.             { // both discovered and undiscovered
  81.                 if (this->_bipartite)
  82.                 { // bi-coloring checks
  83.                     if (this->_color[i] == -1)
  84.                     { // needs to be colored
  85.                         if (this->_color[node] == 0)
  86.                             this->_color[i] = 1;
  87.                         else this->_color[i] = 0;
  88.                     }
  89.                     if (this->_color[node] == this->_color[i])
  90.                     { // color checking with adjacent node
  91.                         this->_bipartite = false;
  92.                     }
  93.                 }
  94.                 if (this->_level[i] == -1) // level by level bfs
  95.                 { // only for not discovered
  96.                     this->_level[i] = this->_level[node] + 1;
  97.                     this->_parent[i] = node;
  98.                     bfs_Q.push(i);
  99.                     _bfsQueue->push_back(i);
  100.                 }
  101.             }
  102.         }
  103.     }
  104. }
  105.  
  106. void BFS::printPath(int destination)
  107. {
  108.     cout << "\nCost from " << this->_source << " to " << destination
  109.         << ": " << this->_level[destination] << "\nPath: ";
  110.     this->path_rec(destination);
  111.     cout << endl;
  112. }
  113.  
  114. void BFS::printDetails()
  115. {
  116.     cout << "\nConnected vertices with [" << this->_source << "] : ";
  117.     for (int i = 0; i < this->_bfsQueue->size(); ++i)
  118.     {
  119.         cout << _bfsQueue->at(i) << " ";
  120.     }
  121.     cout << "\n-----------------------------\n";
  122.  
  123.     cout << "\nDetails:\n--------";
  124.     for (int i = 0; i < this->_graph->getVertexCount(); ++i)
  125.     {
  126.         cout << "\n==> Level / cost of node " << i << " is "
  127.             << this->_level[i] << endl;
  128.         cout << "==> Parent of node " << i << " is " << this->_parent[i]
  129.             << endl;
  130.         cout << "==> Path from " << this->_source << " to " << i << " : ";
  131.         this->path_rec(i);
  132.         cout << endl;
  133.     }
  134.  
  135.     cout << "\n# Bi-Coloring Type: "
  136.         << (_bipartite ? "Bipartite" : "Not-bipartite")
  137.         << "\n-------------------\n";
  138. }
RAW Paste Data