Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <set>
       4             : #include <vector>
       5             : 
       6             : #include "Alg/ShortestPath/ShortestPathOneOne.hpp"
       7             : #include "ShortestPathOneMany.hpp"
       8             : 
       9             : namespace Alg::ShortestPath {
      10             : /**
      11             :  * @brief Breadth-First Search algorithm
      12             :  *
      13             :  */
      14       93778 : class BFS: public ShortestPathOneMany, public ShortestPathOneOne {
      15             :    private:
      16             :     typedef size_t Weight;
      17             : 
      18             :     static const Weight WEIGHT_INF;
      19             : 
      20             :     std::set<Graph::Node> sSet;
      21             : 
      22             :     std::vector<Weight>      dist;
      23             :     std::vector<Graph::Edge> prev;
      24             : 
      25             :     virtual bool isStart(Graph::Node u) const;
      26             : 
      27             :    public:
      28             :     virtual void                solveList(const Graph &G, const std::list<Graph::Node> &s);
      29             :     virtual Graph::Edge::Weight solveStartFinish(const Graph &G, Graph::Node s, Graph::Node t);
      30             : 
      31             :     Graph::Edge getPrev(Graph::Node d) const;
      32             : 
      33             :     Graph::Edge::Weight getPathWeight(Graph::Node d) const;
      34             : 
      35             :     bool hasVisited(Graph::Node u) const;
      36             : };
      37             : }  // namespace Alg::ShortestPath