Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <list>
       4             : 
       5             : #include "Alg/Graph.hpp"
       6             : 
       7             : namespace Alg::ShortestPath {
       8             : /**
       9             :  * @brief Shortest path between a set of start nodes to all other nodes
      10             :  */
      11           9 : class ShortestPathManyMany {
      12             :    public:
      13             :     virtual ~ShortestPathManyMany();
      14             : 
      15             :     /**
      16             :      * @brief Execute the algorithm
      17             :      *
      18             :      * @param G Graph
      19             :      * @param s Starting nodes
      20             :      */
      21             :     virtual void solve(const Graph &G, const std::vector<Graph::Node> &s) = 0;
      22             : 
      23             :     /**
      24             :      * @brief Retrieves the node that comes before d in the path from s to d
      25             :      *
      26             :      * @param   s           Start node
      27             :      * @param   d           Destination node
      28             :      * @return  Graph::Edge Edge traversed before getting to d
      29             :      */
      30             :     virtual Graph::Edge getPrev(Graph::Node s, Graph::Node d) const = 0;
      31             : 
      32             :     /**
      33             :      * @brief Get shortest path (sequence of nodes) from s to d
      34             :      *
      35             :      * @param   s                       Start node
      36             :      * @param   d                       Destination node
      37             :      * @return  std::list<Graph::Node>  Shortest path to d
      38             :      */
      39             :     virtual Graph::Path getPath(Graph::Node s, Graph::Node d) const final;
      40             : 
      41             :     /**
      42             :      * @brief Get weight of shortest path from s to d
      43             :      *
      44             :      * @param   s                   Start node
      45             :      * @param   d                   Destination node
      46             :      * @return  Graph::Edge::Weight Weight of shortest path
      47             :      */
      48             :     virtual Graph::Edge::Weight getPathWeight(Graph::Node s, Graph::Node d) const = 0;
      49             : 
      50             :     /**
      51             :      * @brief Checks if a specific node was marked as visited when starting the
      52             :      * search at s
      53             :      *
      54             :      * @param   s                   Start node
      55             :      * @param u         Node to be checked
      56             :      * @return true     If the node has been already visited
      57             :      * @return false    Otherwise
      58             :      */
      59             :     virtual bool hasVisited(Graph::Node s, Graph::Node u) const = 0;
      60             : };
      61             : }  // namespace Alg::ShortestPath