Dijkstra.h

/* Copyright Robin Schirrmeister and Simon Skilevic
 * Lecture Efficient Route Planning Summer Semester 2011
 * Uni Freiburg
 */

#ifndef ROUTEPLANNINGV2_DIJKSTRA_H_
#define ROUTEPLANNINGV2_DIJKSTRA_H_
#include <queue>
#include <utility>
#include <vector>
#include <string>
#include <functional>
#include "./RoadNetwork.h"
#include "./TransitNetworkExpanded.h"
#include "./TransitNetworkDependent.h"
#include "./Heuristics.h"
#include "./EdgeDependent.h"
#include "./Label.h"
using std::pair;
using std::vector;
using std::priority_queue;
// Abstract Dijkstra Shortest Path Computation class
// can be subclassed to make proper dijkstra
// for subclassing one has to override:
// doPrecomputation
// resetBeforeDijkstra - what should be reset before dijkstra starts
// resetNode - gets called when node is settled or when node is taken from queue
// and not allowed (see below)
// nodeAllowed - should the given node id be expanded?
// edgeAllowed - should the given edge be relaxed?
// reconstructShortestPath - how to reconstruct the shortest path after
//                           finishing the algorithm
class Dijkstra
{
 public:
  // Constructor.
  Dijkstra(Graph* roadNetwork,
              DistanceHeuristic* heuristic);
  virtual ~Dijkstra();
  // what to do before first query...
  virtual void doPrecomputation() = 0;
  // reset values before dijkstra starts...
  virtual void atStartOfDijkstra() = 0;
  // resets computed values like weights, times etc.
  void resetAll();
  // reset settled node...
  virtual void resetNode(int nodeId) = 0;
  void setHeuristic(DistanceHeuristic* heuristic);
  // computes shortest path, returns length..
  template<bool checkNodes, bool checkEdges, bool rememberEdges,
          bool forward, bool toAllNodes>
  double computeShortestPath(int startId, int endId);
  double computeShortestPath(int startId, int endId,
                             bool checkNodes, bool checkEdges,
                             bool rememberEdges, bool forward);

  // TODO(Robin): compute shortest path from set to all
  // double computeShortestPathFromSetToAll(vector<int> startIds,
  //                                  bool checkNodes, bool checkEdges,
  //                                  bool rememberEdges, bool forward);

  // compute shrotest path fom start id to all (reachable) nodes in graph
  double computeShortestPathToAll(int startId,
                                  bool checkNodes, bool checkEdges,
                                  bool rememberEdges, bool forward);
  virtual double computeShortestPath(int startId, int endId,
                                     bool reconstructPath) = 0;
  // check if this node is allowed in the dijkstra
  virtual bool nodeAllowed(int nodeId) = 0;
  // check if this edge is allowed in this dijkstra
  virtual bool edgeAllowed(bool outEdge, int nodeId, int edgeId) = 0;

  vector<NodeExpanded> shortestPath;

  size_t exploredNodes;  // TODO(Robin): make private again?
 protected:
  virtual void reconstructShortestPath(int startId, int endId) = 0;
  DistanceHeuristic* heuristic;
  vector<double> weights;
  vector<double> heuristicValues;
  vector<double> timesFromStart;
  // stores which nodeid (index of vector)
  // was expanded from which node id (first part of pair)
  // with which edge (second part of pair)
  vector<pair<int, int> > expandedFrom;
  vector<bool> expanded;
  // Every dijkstra variant needs a graph.
  Graph* _graph;
  priority_queue <pair<double, int>,
                    std::vector<pair<double, int> >,
                    std::greater<pair<double, int > > > _openNodeQueue;
  bool _stopDijkstra;
};

class SimpleDijkstra : public Dijkstra
{
 public:
  SimpleDijkstra(Graph* roadNetwork,
                   DistanceHeuristic* heuristic);
  SimpleDijkstra();
  // does nothing
  void doPrecomputation();
  // reset all values, if number of ndoes in graph cahnged,
  // else just reset expanded...
  void atStartOfDijkstra();

  // just reset heuristics-value and weights-value...
  void resetNode(int nodeId);

  // always returns true...
  bool edgeAllowed(bool outEdge, int nodeId, int edgeId);
  // always returns true...
  bool nodeAllowed(int nodeId);
  double computeShortestPath(int startId, int endId,
                             bool reconstructPath);
  double computeShortestPath(int startId, int endId,
                             bool reconstructPath, bool forward);

 private:
  void reconstructShortestPath(int startId, int endId);
};

/*TODO(ROBIN): delete class?
class TransitDijkstra : public SimpleDijkstra
{
 public:
  TransitDijkstra(TransitNetwork* roadNetwork,
                   DistanceHeuristic* heuristic);
  // returns false once endid was found...
  bool nodeAllowed(int nodeId);
  // convenience function, just calls the function below
  double computeShortestPath(string startStop, Time time,
                             string endStop, bool buildPath);
  // find shortest path...
  double computeShortestPath(int startStopId, Time time,
                             int endStopId, bool buildPath);
  // the shortest path: last Edge is a dummy edge...
  vector<pair<Node, Edge> > transitShortestPath;
 private:
  // reconstruct shortest path..
  void reconstructShortestPath(const unordered_set<int>& startIds);
  TransitNetwork* _tranGraph;
  bool _endStopFound;
  int _endStopId;
  int _endId;
};*/
// Label Object for puting in priority queue.
// it contains Node and conection(Stoptime) by wich Node will be reach
// with weight(from startNode to this node)

#endif  // ROUTEPLANNINGV2_DIJKSTRA_H_