Line data    Source code

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