Line data    Source code

       1             : #include "Alg/ShortestPath/DijkstraMany.hpp"
       2             : 
       3             : #include <stdexcept>
       4             : 
       5             : using namespace std;
       6             : using namespace Alg;
       7             : using namespace Alg::ShortestPath;
       8             : 
       9             : typedef Graph::Node         Node;
      10             : typedef Graph::Edge::Weight Weight;
      11             : typedef Graph::Edge         Edge;
      12             : 
      13           9 : DijkstraMany::DijkstraMany(int parallelism):
      14           9 :     pool(parallelism) {}
      15             : 
      16           9 : void DijkstraMany::solve(const Graph &G, const vector<Node> &s_) {
      17             :     // Initialize
      18          18 :     for(const Node &s: s_)
      19           9 :         dijkstras[s];
      20             : 
      21             :     // Run
      22           9 :     if(pool.size() <= 0) {
      23           0 :         for(auto &[s, dijkstra]: dijkstras) {
      24           0 :             dijkstra.solve(G, s);
      25             :         }
      26           0 :         return;
      27             :     }
      28             : 
      29          18 :     vector<future<void>> results;
      30          18 :     for(auto &p: dijkstras) {
      31           9 :         const Node &s        = p.first;
      32           9 :         Dijkstra   &dijkstra = p.second;
      33          18 :         results.emplace_back(pool.push([&dijkstra, &G, s](int) -> void {
      34             :             dijkstra.solve(G, s);
      35           9 :         }));
      36             :     }
      37          18 :     for(future<void> &r: results) r.get();
      38             : }
      39             : 
      40          13 : Edge DijkstraMany::getPrev(Node s, Node d) const {
      41          13 :     try {
      42          13 :         return dijkstras.at(s).getPrev(d);
      43           0 :     } catch(out_of_range &e) {
      44           0 :         throw out_of_range("DijkstraMany::getPrev: No path from " + to_string(s) + " to " + to_string(d));
      45             :     }
      46             : }
      47             : 
      48           0 : Weight DijkstraMany::getPathWeight(Node s, Node d) const {
      49           0 :     try {
      50           0 :         return dijkstras.at(s).getPathWeight(d);
      51           0 :     } catch(out_of_range &e) {
      52           0 :         throw out_of_range("DijkstraMany::getPathWeight: No path from " + to_string(s) + " to " + to_string(d));
      53             :     }
      54             : }
      55             : 
      56           0 : bool DijkstraMany::hasVisited(Node s, Node u) const {
      57           0 :     auto it = dijkstras.find(s);
      58           0 :     if(it == dijkstras.end()) return false;
      59           0 :     return it->second.hasVisited(u);
      60             : }