BFS.hpp

Go to the documentation of this file.

#ifndef GL_BFS_HPP
#define GL_BFS_HPP

#include <limits>

#include "../structures/Graph.hpp"

namespace gl {
namespace algorithm {

//    Class declaration

template <class Graph>
class BFS {
  using idx_t = typename Graph::idx_t;                   
  using ordered_list_t = typename Graph::ordered_list_t; 
  using visit_list_t = typename Graph::visit_list_t;     
  using BFS_queue_t = std::deque<idx_t>;                 
  using distance_list_t = std::vector<idx_t>;            
  using idx_list_t = typename Graph::idx_list_t;         

public: 
  explicit BFS(const Graph&, const idx_t);

  BFS();                                 
  BFS(const BFS &) = default;            
  BFS(BFS &&) noexcept = default;        
  BFS &operator=(const BFS &) = default; 
  BFS &operator=(BFS &&) = default;      
  ~BFS() = default;                      

  void compute(const Graph& graph, const idx_t src);
  ordered_list_t getTraversalOrder () const;
  ordered_list_t getTraversalOrderMaxDistance (const idx_t& distance) const;

  idx_list_t getNodesExactDistance (const idx_t& distance) const;
  idx_t getNodeDistance (const idx_t& dest) const;
  idx_list_t getNodesMaxDistance (const idx_t& distance) const;
  ordered_list_t getPath (const idx_t& dest) const;

private:
  bool isInitialized_ = false; 
  idx_t src_;                  
  idx_list_t parents_;         
  ordered_list_t final_;       
  distance_list_t distances_;  
};

//    Member function implementations

template <class Graph>
BFS<Graph>::BFS() : isInitialized_(false) {}

template <class Graph>
BFS<Graph>::BFS(const Graph& graph, const idx_t src) : isInitialized_(false), src_(src) 
{
  compute(graph, src);
}

template <class Graph>
void BFS<Graph>::compute (const Graph& graph, const idx_t src) 
{
  graph.checkRange(src);
  idx_t INF = std::numeric_limits<idx_t>::max();

  BFS_queue_t queue;      // nodes to check the neighbours of
  ordered_list_t out;     // result node lists
  idx_list_t tempList;    // temporary node lists
  idx_list_t parents(graph.numNodes());  // parents on shortest path tree
  visit_list_t visited(graph.numNodes(),false);  // list of visited nodes
  distance_list_t distances(graph.numNodes(),INF);
  auto v = src;

  // traversal
  queue.push_back(v);
  visited[v] = true;
  distances[v] = 0;
  parents[v] = v;
  while(!queue.empty()) {
    v = queue.front();
    queue.pop_front();
    out.push_back(v);
    tempList = graph.getUnvisitedNeighbours(v,visited);
    for (auto elem : tempList) {
      visited[elem] = true;
      distances[elem] = distances[v] + 1;
      parents[elem] = v;
      queue.push_back(elem);
    }
  }
  parents_ = parents;
  final_ = out;
  distances_ = distances;
  isInitialized_ = true;
}

template <class Graph>
typename Graph::ordered_list_t BFS<Graph>::getTraversalOrder () const {
  GL_ASSERT(isInitialized_,"BFS::getTraversalOrder | BFS has not been initialized with a graph.")
  return final_;
}

template <class Graph>
typename Graph::ordered_list_t BFS<Graph>::getTraversalOrderMaxDistance (const idx_t& distance) const {
  GL_ASSERT(isInitialized_,"BFS::getTraversalOrderMaxDistance | BFS has not been initialized with a graph.")
  ordered_list_t result;
  for (auto x : final_) {
    if (distances_[x] > distance) continue;
    result.push_back(x);
  }
  return result;
}

template <class Graph>
typename Graph::idx_list_t BFS<Graph>::getNodesExactDistance (const idx_t& distance) const {
  GL_ASSERT(isInitialized_,"BFS::getNodesExactDistance | BFS has not been initialized with a graph.")
  idx_list_t result;
  for (auto elem : final_) {
    if (distances_[elem] == distance) result.push_back(elem);
  }
  return result;
}

template <class Graph>
typename Graph::idx_t BFS<Graph>::getNodeDistance (const idx_t& dest) const {
  GL_ASSERT(isInitialized_,"BFS::getNodeDistance | BFS has not been initialized with a graph.")
  GL_ASSERT((0 <= dest), (std::string("Negative index: ") + std::to_string(dest) + std::string(" < 0")))
  GL_ASSERT((dest < distances_.size()), ("Index " + std::to_string(dest) + " is larger than the max: " + std::to_string(distances_.size() - 1)))
  
  return distances_[dest];
}

template <class Graph>
typename Graph::idx_list_t BFS<Graph>::getNodesMaxDistance (const idx_t& distance) const {
  GL_ASSERT(isInitialized_,"BFS::getNodesMaxDistance | BFS has not been initialized with a graph.")
  idx_list_t result;
  for (auto elem : final_) {
    if (distances_[elem] <= distance) result.push_back(elem);
  }
  return result;
}

template <class Graph>
typename Graph::ordered_list_t BFS<Graph>::getPath (const idx_t& dest) const {
  GL_ASSERT(isInitialized_,"BFS::getPath | BFS has not been initialized with a graph.")
  GL_ASSERT((0 <= dest), (std::string("Negative index: ") + std::to_string(dest) + std::string(" < 0")))
  GL_ASSERT((dest < distances_.size()), ("Index " + std::to_string(dest) + " is larger than the max: " + std::to_string(distances_.size() - 1)))
  if (dest == src_) 
  {
    return {src_};
  }
  ordered_list_t result;
  idx_t parent = parents_[dest];
  result.push_front(dest);
  result.push_front(parent);
  while (parent != src_)
  {
    parent = parents_[parent];
    result.push_front(parent);
  }
  return result;
}

} // namespace algorithm
} // namespace gl

#endif // GL_BFS_HPP