Line data    Source code

       1             : #include "Alg/ShortestPath/BFS.hpp"
       2             : 
       3             : #include <chrono>
       4             : #include <iostream>
       5             : #include <queue>
       6             : #include <utility>
       7             : 
       8             : #include "Alg/BinaryHeap.hpp"
       9             : 
      10             : using namespace std;
      11             : using namespace Alg;
      12             : using namespace Alg::ShortestPath;
      13             : 
      14             : typedef Graph::Node Node;
      15             : typedef Graph::Edge Edge;
      16             : typedef queue<Node> Queue;
      17             : 
      18             : const BFS::Weight BFS::WEIGHT_INF = 1000000000;
      19             : 
      20      621926 : bool BFS::isStart(Graph::Node u) const {
      21      621926 :     return sSet.count(u);
      22             : }
      23             : 
      24      208323 : void BFS::solveList(const Graph &G, const list<Node> &sList) {
      25             :     // Initialize
      26      208323 :     sSet.clear();
      27      208323 :     sSet.insert(sList.begin(), sList.end());
      28             : 
      29      208323 :     Node maxNode = 0;
      30     1582680 :     for(const Node &u: G.getNodes()) {
      31     2224600 :         maxNode = max(maxNode, u);
      32             :     }
      33      322868 :     dist = vector<Weight>(maxNode + 1, BFS::WEIGHT_INF);
      34      322868 :     prev = vector<Edge>(maxNode + 1, Graph::EDGE_INVALID);
      35             : 
      36             :     // Run
      37      208323 :     Queue Q;
      38             : 
      39      416646 :     for(const Node &s: sList) {
      40      208323 :         dist[s] = 0;
      41      416646 :         Q.push(s);
      42             :     }
      43             : 
      44     1085880 :     while(!Q.empty()) {
      45      877555 :         Node u = Q.front();
      46      877555 :         Q.pop();
      47      877555 :         BFS::Weight du = dist[u];
      48     2471540 :         for(const Edge &e: G.getAdj(u)) {
      49     1593980 :             BFS::Weight  c_    = du + 1;
      50     1593980 :             BFS::Weight &distV = dist[e.v];
      51     1593980 :             if(e.w > 0 && c_ < distV) {
      52      669232 :                 Q.push(e.v);
      53      669232 :                 distV     = c_;
      54      669232 :                 prev[e.v] = e;
      55             :             }
      56             :         }
      57             :     }
      58      208323 : }
      59             : 
      60      208323 : Graph::Edge::Weight BFS::solveStartFinish(const Graph &G, Node s_, Node t_) {
      61      208323 :     solve(G, s_);
      62      208323 :     return getPathWeight(t_);
      63             : }
      64             : 
      65      507381 : Edge BFS::getPrev(Node d) const {
      66      507381 :     return prev.at(d);
      67             : }
      68             : 
      69      208323 : Graph::Edge::Weight BFS::getPathWeight(Node d) const {
      70      208323 :     return (Graph::Edge::Weight)dist.at(d);
      71             : }
      72             : 
      73             : // clang-format off
      74      208323 : bool BFS::hasVisited(Node u) const {
      75      208323 : #pragma GCC diagnostic push
      76      208323 : #pragma GCC diagnostic ignored "-Wfloat-equal"
      77      208323 :     return (dist.at(u) != BFS::WEIGHT_INF);
      78      208323 : #pragma GCC diagnostic pop
      79             : }
      80             : // clang-format on