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 from one node to all other nodes.
      10             :  */
      11       93783 : class ShortestPathOneMany {
      12             :    private:
      13             :     virtual bool isStart(Graph::Node u) const = 0;
      14             : 
      15             :    public:
      16             :     virtual ~ShortestPathOneMany();
      17             : 
      18             :     /**
      19             :      * @brief Execute the algorithm
      20             :      *
      21             :      * @param G Graph
      22             :      * @param s Starting node
      23             :      */
      24             :     virtual void solve(const Graph &G, Graph::Node s) final;
      25             : 
      26             :     virtual void solveList(const Graph &G, const std::list<Graph::Node> &sList) = 0;
      27             : 
      28             :     /**
      29             :      * @brief Retrieves the edge that leads to d in the shortest path to d
      30             :      *
      31             :      * @param   d           Destination Node
      32             :      * @return  Graph::Edge Edge traversed before getting to d
      33             :      */
      34             :     virtual Graph::Edge getPrev(Graph::Node d) const = 0;
      35             : 
      36             :     /**
      37             :      * @brief Get shortest path (sequence of nodes) from starting node to d
      38             :      *
      39             :      * @param   d                       Destination node
      40             :      * @return  std::list<Graph::Node>  Shortest path to d
      41             :      */
      42             :     virtual Graph::Path getPath(Graph::Node d) const final;
      43             : 
      44             :     /**
      45             :      * @brief Get weight of shortest path from starting node to d
      46             :      *
      47             :      * @param   d                   Destination node
      48             :      * @return  Graph::Edge::Weight Weight of shortest path
      49             :      */
      50             :     virtual Graph::Edge::Weight getPathWeight(Graph::Node d) const = 0;
      51             : 
      52             :     /**
      53             :      * @brief Checks if a node was marked as visited
      54             :      *
      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 u) const = 0;
      60             : };
      61             : }  // namespace Alg::ShortestPath